304
правки
Изменения
Новая страница: «== Определение == Определим последовательность строк <tex>T_n</tex> над двухбуквенным алфавито...»
== Определение ==
Определим последовательность строк <tex>T_n</tex> над двухбуквенным алфавитом <tex>\{a, b\}</tex> следующим образом: <tex>T_n = t_0 t_1 \dots t_{2^n-1}</tex>, где:
* <tex>t_i = a</tex>, если двоичная запись числа <tex>i</tex> содержит чётное число единиц
* <tex>t_i = b</tex> иначе
Строки этой последовательности называются строками Туэ-Морса.
== Примеры ==
Приведём первые пять строк Туэ-Морса:
* <tex>T_0 = a</tex>
* <tex>T_1 = ab</tex>
* <tex>T_2 = abba</tex>
* <tex>T_3 = abbabaab</tex>
* <tex>T_4 = abbabaabbaababba</tex>
== Свойства и эквивалентные определения ==
Как видно из определения, символ на <tex>i</tex>-ой позиции не зависит от номера строки. Так как длина строк возрастает, каждая строка является собственным префиксом следующей, поэтому можно рассматривать получение следующей строки как приписывание к текущей некоторого суффикса.
Заметим, что соответсвующие индексы символов при приписывании суффикса к строке <tex>T_n</tex> получаются добавлением к индексам <tex>i = 0, 1, \dots, 2^n - 1</tex> числа <tex>2^n</tex>. Количество единиц в двоичной записи числа <tex>i + 2^n</tex> ровно на один больше, чем в двоичной записи числа <tex>i</tex>. Поэтому приписываемый суффикс есть ни что иное, как исходная строка с инвертированными символами.
Часто рассматривают предельный случай — бесконечную строку Туэ-Морса. Бесконечную строку также можно задать с помощью правил ассоциативного исчисления, клеточного автомата, рекурсивных соотношений и так далее.
== Ссылки ==
* [http://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence Wikipedia — Thue-Morse sequence]
* [http://mathworld.wolfram.com/Thue-MorseSequence.html Wolfram Mathworld — Thue-Morse sequence]
Определим последовательность строк <tex>T_n</tex> над двухбуквенным алфавитом <tex>\{a, b\}</tex> следующим образом: <tex>T_n = t_0 t_1 \dots t_{2^n-1}</tex>, где:
* <tex>t_i = a</tex>, если двоичная запись числа <tex>i</tex> содержит чётное число единиц
* <tex>t_i = b</tex> иначе
Строки этой последовательности называются строками Туэ-Морса.
== Примеры ==
Приведём первые пять строк Туэ-Морса:
* <tex>T_0 = a</tex>
* <tex>T_1 = ab</tex>
* <tex>T_2 = abba</tex>
* <tex>T_3 = abbabaab</tex>
* <tex>T_4 = abbabaabbaababba</tex>
== Свойства и эквивалентные определения ==
Как видно из определения, символ на <tex>i</tex>-ой позиции не зависит от номера строки. Так как длина строк возрастает, каждая строка является собственным префиксом следующей, поэтому можно рассматривать получение следующей строки как приписывание к текущей некоторого суффикса.
Заметим, что соответсвующие индексы символов при приписывании суффикса к строке <tex>T_n</tex> получаются добавлением к индексам <tex>i = 0, 1, \dots, 2^n - 1</tex> числа <tex>2^n</tex>. Количество единиц в двоичной записи числа <tex>i + 2^n</tex> ровно на один больше, чем в двоичной записи числа <tex>i</tex>. Поэтому приписываемый суффикс есть ни что иное, как исходная строка с инвертированными символами.
Часто рассматривают предельный случай — бесконечную строку Туэ-Морса. Бесконечную строку также можно задать с помощью правил ассоциативного исчисления, клеточного автомата, рекурсивных соотношений и так далее.
== Ссылки ==
* [http://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence Wikipedia — Thue-Morse sequence]
* [http://mathworld.wolfram.com/Thue-MorseSequence.html Wolfram Mathworld — Thue-Morse sequence]
