Редактирование: Слово Туэ-Морса

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 5: Строка 5:
 
* <tex>t_i = b</tex>, иначе.
 
* <tex>t_i = b</tex>, иначе.
  
Строки этой последовательности называются '''строками Туэ-Морса''' (англ. ''Thue–Morse sequence'').
+
Строки этой последовательности называются '''строками Туэ-Морса'''.
 
}}
 
}}
  
Строка 18: Строка 18:
  
 
== Свойства и эквивалентные определения ==
 
== Свойства и эквивалентные определения ==
===Свойство о получении следующей строки===
+
 
 
Как видно из определения, символ на <tex>i</tex>-ой позиции не зависит от номера строки. Так как длина строк возрастает, каждая строка является собственным префиксом следующей, поэтому можно рассматривать получение следующей строки как приписывание к текущей строке некоторой другой строки.
 
Как видно из определения, символ на <tex>i</tex>-ой позиции не зависит от номера строки. Так как длина строк возрастает, каждая строка является собственным префиксом следующей, поэтому можно рассматривать получение следующей строки как приписывание к текущей строке некоторой другой строки.
  
Строка 31: Строка 31:
 
  тогда для строк Туэ-Морса верно следующее соотношение: <tex>T_{n + 1} = T_n \varphi(T_n)</tex>
 
  тогда для строк Туэ-Морса верно следующее соотношение: <tex>T_{n + 1} = T_n \varphi(T_n)</tex>
 
|proof=
 
|proof=
Заметим, что соответствующие индексы символов при приписывании новой строки к строке <tex>T_n</tex> получаются добавлением к индексам <tex>i = 0, 1, \dots, 2^n - 1</tex> числа <tex>2^n</tex>. Количество единиц в двоичной записи числа <tex>i + 2^n</tex> (<tex>i < 2^n</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 < 2^n</tex>) ровно на один больше, чем в двоичной записи числа <tex>i</tex>. Поэтому приписываемая строка есть ни что иное, как исходная строка с инвертированными символами.
 
}}
 
}}
  
Строка 38: Строка 38:
 
Часто рассматривают предельный случай — бесконечную строку Туэ-Морса, любой символ которой можно получить из обычной строки Туэ-Морса с достаточно большим номером. Бесконечную строку также можно задать с помощью правил ассоциативного исчисления, клеточного автомата, рекурсивных соотношений.
 
Часто рассматривают предельный случай — бесконечную строку Туэ-Морса, любой символ которой можно получить из обычной строки Туэ-Морса с достаточно большим номером. Бесконечную строку также можно задать с помощью правил ассоциативного исчисления, клеточного автомата, рекурсивных соотношений.
  
===Свойство о подстроках===
+
== Ссылки ==
 
 
{{Теорема
 
|statement=
 
Не существует двух равных как строки подстрок строки <tex>T_n</tex>, имеющих пересекающиеся вхождения в <tex>T_n</tex>
 
|proof=
 
Заметим, что <tex>t_{2n}=t_n</tex> для <tex>n \geqslant 0</tex>, так как количество единиц числа <tex>2n</tex> и <tex>n</tex> одинаково. Так же заметим, что <tex>t_{2n+1}=\varphi(t_n)</tex> для <tex>n \geqslant 0</tex>, потому что <tex>2n</tex> и <tex>2n+1</tex> одинаковы в двоичной системе, кроме последнего бита, а количество единиц числа <tex>2n</tex> и <tex>n</tex> одинаково.
 
 
 
Пусть существует две равные как строки подстрок строки <tex>T_n</tex>, имеющих пересекающиеся вхождения в <tex>T_n</tex>, тогда <tex>T_n=ucxcxcv</tex>, где <tex>u,c,x,v</tex> {{---}} подстроки строки <tex>T_n</tex>, а строка <tex>cxc</tex> {{---}} искомая подстрока.
 
 
 
Пусть <tex>m=|cx|</tex> и <tex>k=|u|</tex>, тогда <tex>t_{k+j}=t_{k+j+m}</tex> по предположению при <tex>0 \leqslant j \leqslant m</tex>.
 
 
 
Рассмотрим наименьшее <tex>m\geqslant 1</tex>. Тогда возможны два случая: <tex>m</tex> четно и нечетно:
 
# <tex>m</tex> четно.
 
#: Тогда пусть <tex>m=2m'</tex>. Рассмотрю два случая: <tex>k</tex> четно или нечетно:
 
#* <tex>k</tex> четно:
 
#*:Пусть <tex>k=2k'</tex>. Так как <tex>t_{k+j}=t_{k+j+m}</tex> при <tex>0 \leqslant j \leqslant m</tex>, тогда очевидно, что <tex>t_{2k'+2j'}=t_{2k'+2j'+2m'}</tex> для <tex> 0 \leqslant j' \leqslant m'</tex>. Так как <tex>t_{2k'+2j'}=t_{k'+j'}</tex> и <tex>t_{2k'+2j'+2m'}=t_{k'+j'+m'}</tex> очевидно, что <tex>t_{k'+j'}=t_{k'+j'+m'}</tex> для <tex>0 \leqslant j' \leqslant m'</tex>. Это противоречие, так как <tex>m</tex> минимально.
 
#* <tex>k</tex> нечетно:
 
#*: Пусть <tex>k=2k'+1</tex>. Тогда, как и в предыдущем случае <tex>t_{2k'+2j'+1}=t_{2k'+2j'+2m'+1}</tex> для <tex>0 \leqslant j' \leqslant m'</tex> и тогда <tex>t_{k'+j'}=t_{k'+j'+m'}</tex> для <tex>0 \leqslant j' \leqslant m'</tex>, что является опять противоречием из-за минимальности <tex>m</tex>
 
#<tex>m</tex> нечетно.
 
#:Тогда рассмотрю три случая: <tex>m \geqslant 5</tex>, <tex>m=3</tex> и <tex>m=1</tex>. Пусть <tex>b_n=\left\{ \begin{array}{rl}
 
a, & t_n=t_{n-1} \\
 
b, & t_n \ne t_{n-1} \\
 
\end{array} \right.</tex>, для <tex>n \geqslant 1</tex>. Заметим, что <tex>b_{4n+2}=a</tex>  так как <tex>4n+2</tex> и <tex>4n+1</tex> одинаково записываются в двоичной записи, кроме последних двух битов, которые равны <tex>10</tex> и <tex>01</tex> соответственно и значит <tex>t_{4n+2}=t_{4n+1}</tex>. Так же заметим, что <tex>b_{2n+1}=b</tex>, так как <tex>2n+1</tex> и <tex>2n</tex> одинаково записываются в двоичной системе, кроме последнего бита и значит, что <tex>t_{2n+1}=\varphi(t_{2n})</tex>
 
#* <tex>m</tex> нечетно и <tex>m \geqslant 5</tex>.
 
#*:Тогда <tex>b_{k+j}=b_{k+j+m}</tex> для <tex>1 \leqslant j \leqslant m</tex>. С <tex>m \geqslant 5</tex> существует <tex>j</tex>, такое что <tex>k+j=2</tex> по модулю <tex>4</tex>. Тогда для <tex>k+j</tex> точно известно, что <tex>b_{k+j}=0</tex>, но с другой стороны <tex>k+j+m</tex> {{---}} нечетно, значит <tex>b_{k+j+m}=1</tex>. Противоречие.
 
#* <tex>m=3</tex>.
 
#*:Аналогично: <tex>b_{k+j}=b_{k+j+3}</tex> для <tex>1 \leqslant j \leqslant 3</tex>. Найдем <tex>j</tex>, чтобы <tex>k+j=2</tex> или <tex>k+j=3</tex> по модулю <tex>4</tex>. Если <tex>k+j=2</tex> по модулю <tex>4</tex>, то противоречие получается так же, как в предыдущем пункте. Рассмотрим <tex>k+j=3</tex> по модулю <tex>4</tex>, тогда <tex>b_{k+j}=1</tex>, но <tex>b_{k+j+3}=0</tex>. Это опять противоречие.
 
#* <tex>m=1</tex>.
 
#*:Тогда <tex>t_k=t_{k+1}=t_{k+2}</tex> из чего следует, что <tex>t_{2n}=t_{2n+1}</tex> для <tex>n=\dfrac{k}{2}</tex>, но <tex>t_{2n}=\varphi(t_{2n+1}) \ne t_{2n+1}</tex>. Противоречие.
 
 
}}
 
 
 
== См. также ==
 
* [[Слово Фибоначчи]]
 
 
 
== Источники информации==
 
 
* [http://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence Wikipedia — Thue-Morse sequence]
 
* [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]
 
* [http://mathworld.wolfram.com/Thue-MorseSequence.html Wolfram Mathworld — Thue-Morse sequence]
* Jean-Paul Allouche,Jeffrey Shallit «Automatic Sequences: Theory, Applications, Generalizations» {{---}} 15 стр.
 
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: