RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Заседания Московского математического общества
22 ноября 2005 г., г. Москва, ГЗ МГУ, аудитория 16-10
 


Сложности конечных последовательностей нулей и единиц

В. И. Арнольд
Материалы:
Adobe PDF 393.3 Kb

Количество просмотров:
Эта страница:443
Материалы:80

В. И. Арнольд
Фотогалерея

Аннотация: Последовательность 001001001001 проще, чем 010010111001. Будет рассказана формальная теория, придающая этому высказыванию точный смысл.
Пусть $x$ — замкнутая последовательность $n$ нулей и единиц (за $n$-ым элементом опять следует первый). Множество $M$ всех $2^n$ таких последовательностей есть множество вершин $n$-мерного куба (и $n$-мерное векторное пространство над $Z_2$). Определим операцию $A\colon M\to M$ как переход от $x$ к последовательности разностей ($\mod 2$) соседних элементов из $x$. Динамическая система $A$ задается направленным графом с $2^n$ вершинами. Из каждой вершины $x$ выходит ровно одно ребро (ведущее в $Ax$). Сложность последовательности $x$ определяется числом и периодами аттракторов динамической системы $A$, лесами притягиваемых ими деревьев и положением точки $x$ в этих лесах. При $n=11$ аттракторов 4, и 3 из них имеют период 341, а один — период 1. Каждое дерево леса имеет здесь 2 вершины: x—x, доставляя $2(3\cdot 341+1)=2^{11}$ вершин. При $n=12$ аттракторов 24. из них 20 имеют периодом 12, 2 аттрактора имеют период 6, один — период 1. Каждое дерево леса имеет здесь 16 вершин. Зависимость сложности динамики $A$ от числа $n$ представляется загадочной и никакие асимптотики неизвестны. Многочлены $x$ степени меньше $k$ выделяются по (Ньютону) условием $A^kx=0$. В графе системы $A$ эти вершины образуют дерево, притягиваемое аттрактором $x=0$. Многочленов мало. Большинство точек $x$ сложнее всех многочленов. Примером сложной функции кажется теоретико-числовой логарифм: соответствующая ему точка притягивается к самому длинному циклу и лежит далеко от корня притягивающегося дерева системы $A$.

Материалы: 2129.pdf (393.3 Kb)

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017