Том 21, номер 2, 2014 г., Стр. 59–75

УДК 519.714
Мерекин Ю. В.
Функция Шеннона быстрого вычисления сложности по Арнольду двоичных слов длины 2ⁿ для произвольных значений n

Аннотация:
Установлено точное значение функции Шеннона быстрого вычисления сложности по Арнольду двоичных слов длины 2ⁿ в случаях, когда n имеет вид n = m², n =m² + m и n = m² + 2m, m ≥ 2. Тем самым устанавливается точное значение функции Шеннона при любом n.
Библиогр. 6.

Ключевые слова: двоичное слово, сложность числа, сложность по Арнольду, функция Шеннона.

Мерекин Юрий Владимирович ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: merekin@math.nsc.ru

Статья поступила 11 февраля 2013 г.
Исправленный вариант — 25 декабря 2013 г.

Литература

[1] Арнольд В. И. Топология и статистика формул арифметики // Успехи мат. наук. - 2003. - Т. 58, №4. - C. 1–26.

[2] Евдокимов А. А., Пережогин А. Л. Структура функционирования дискретных динамических систем циркулянтного типа с линейными функциями в вершинах сети // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, №3. - С. 39–48.
Evdokimov A. A. Perezhogin A. L. Discrete dynamical systems of a circulant type with linear functions at the vertices of a network // J. Appl. Industr. Math. - 2012. - Vol. 6, N2. - P. 160–166.

[3] Мерекин Ю. В. Функция Шеннона вычисления сложности по Арнольду двоичных слов длины 2ⁿ // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, №6. - C. 49–55.
Merekin Yu. V. The Shannon function for calculating the Arnold complexity of length 2ⁿ binary words // J. Appl. Industr. Math. - 2013. - Vol. 7, N 2. - P. 229–233.

[4] Merekin Yu. V. On the computational complexity of the Arnold complexity of binary words // Asian-Eur. J. Math. - 2009. - Vol. 2, N4. - P. 641–648.

[5] Merekin Yu. V. On the computation of Arnold complexity of length 2ⁿ binary words // Asian-Eur. J. Math. - 2011. - Vol. 4, N2. - P. 295–300.

[6] Merekin Yu. V. Fast computation of the Arnold complexity of length 2ⁿ binary words // Southeast Asian Bull. Math. - 2012. - Vol. 36, N6. - P. 855–862.