Викиконспекты - Вклад участника [ru]

Слово Туэ-Морса

2012-04-29T20:29:25Z

178.178.10.235:

{{Определение
|definition=
Определим последовательность строк <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>-ой позиции не зависит от номера строки. Так как длина строк возрастает, каждая строка является собственным префиксом следующей, поэтому можно рассматривать получение следующей строки как приписывание к текущей строке некоторой другой.

{{Теорема
|statement=
Пусть <tex>\varphi(S)</tex> — результат применения морфизма <tex>\varphi(a) = b, \varphi(b) = a</tex> к <tex>S \in \{a, b\}^*</tex>. Для строк Туэ-Морса верно следующее соотношение: <tex>T_{n + 1} = T_n \varphi(T_n)</tex>
|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</tex>. Поэтому приписываемая строка есть ни что иное, как исходная строка с инвертированными символами.
}}

Данная теорема позволяет определять последовательность строк Туэ-Морса следующим образом: <tex>T_0 = a</tex>, <tex>T_{n + 1} = T_n \varphi(T_n)</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]

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Слово Туэ-Морса

2012-04-29T20:18:00Z

178.178.10.235: /* Свойства и эквивалентные определения */

{{Определение
|definition=
Определим последовательность строк <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>-ой позиции не зависит от номера строки. Так как длина строк возрастает, каждая строка является собственным префиксом следующей, поэтому можно рассматривать получение следующей строки как приписывание к текущей строке некоторой другой.

{{Теорема
|statement=
Пусть <tex>\varphi(S)</tex> — результат применения морфизма <tex>\varphi(a) = b, \varphi(b) = a</tex> к <tex>S \in \{a, b\}^*</tex>. Для строк Туэ-Морса верно следующее соотношение: <tex>T_{n + 1} = T_n \varphi(T_n)</tex>
|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</tex>. Поэтому приписываемая строка есть ни что иное, как исходная строка с инвертированными символами.
}}

Данная теорема позволяет определять последовательность строк Туэ-Морса следующим образом: <tex>T_0 = a</tex>, <tex>T_{n + 1} = T_n \varphi(T_n)</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]

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Слово Фибоначчи

2012-04-29T20:07:50Z

178.178.10.235: /* Лемма */

==Определение==
{{Определение
|definition='''Морфизмом''' называется отображение <tex>h</tex>, которое каждой букве <tex>\lambda</tex> из алфавита <tex>A</tex> ставит в соответствие строку <tex>h(\lambda)</tex> из множества <tex>A^{+}</tex>,
а каждой строке <tex>x</tex> из <tex>A^+</tex> ставит в соответсвие строку из <tex>A^+</tex> по следующему правилу :
<tex>h(x) = h(x[1])h(x[2])...h(x[n])</tex> , где <tex>x[1], x[2], \dots, x[n]</tex> уже являются элементами <tex>A</tex>.

}}

Любой морфизм <tex>h</tex> можно применять к исходной строке <tex>x_0</tex> любое число раз, тем самым генерируя последовательность итераций <tex>h^{*}(x_0)</tex> по следующему правилу: 
<tex>h^{*}(x_0) = \{h^0(x_0), h^1(x_0),...\}</tex>. 
где <tex>h^0(x_0) = x_0</tex> и для любого целого <tex>k \geq 1</tex> <tex> h^k(x_0) = h(h^{k-1}(x_0))</tex>. 
Например: 
<tex>A = \{a,b\}, h(a) = a, h(b) = ab</tex>. 
<tex>h^*(a) = \{a,a,...\}</tex> 
<tex>h^*(b) = \{b, ab, a^2b,..., a^kb...\}</tex> 

{{Определение
|definition='''Строками Фибоначчи''' являются строки, полученные последовательным применением морфизма <tex>h</tex> к строке <tex>x_0 = b</tex>, т.е. <tex>h^*(b)</tex>.
* <tex>A = \{a,b\}</tex>
* <tex>h(a) = ab</tex>
* <tex>h(b) = a</tex>

}}

Первые несколько строк Фибоначчи: 
* <tex>f_0 = b</tex>
* <tex>f_1 = a</tex>
* <tex>f_2 = ab</tex>
* <tex>f_3 = aba</tex>
* <tex>f_4 = abaab</tex>
* <tex>f_5 = abaababa</tex>

==Лемма==
{{Лемма
|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>f_n = f_{n-1}f_{n-2}, n \geq 2</tex>.
|proof=
Доказательство нетрудно получить методом математической индукции.

'''База:''' При <tex>n = 2</tex> равенство очевидно.

'''Переход:''' Пусть <tex>f_n = f_{n-1}f_{n-2}</tex>. <tex>f_{n+1} = h(f_n) = h(f_{n-1}f_{n-2})</tex>. Т.к. h {{---}} линейна (т.е. <tex>h(xy) = h(x)h(y)</tex>), то можно продолжить равенство:
<tex>f_{n+1} = h(f_{n-1})h(f_{n-2}) = f_{n}f_{n-1}</tex>.
}}

Также нетрудно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.

== Литература ==
* Билл Смит. Методы и алгоритмы вычислений на строках. Пер. с англ. — М.:ООО"И.Д.Вильямс", 2006. — 496 с.: ил. — Парал. тит. англ. ISBN 5-8459-1081-1 (рус.)

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Период и бордер, их связь

2012-04-29T19:36:26Z

178.178.10.235: /* Свойства периода */

==Связь периода и бордера==
{{Теорема
|statement= Если у строки длины <tex>n</tex> есть [[Основные определения, связанные со строками#Отношения между строками|бордер]] длины <tex>k</tex>, то у нее есть [[Основные определения, связанные со строками#Отношения между строками|период]] длины <tex>n - k</tex>.
|proof=
Пусть дана строка <tex>\alpha</tex>. 
Напишем формально определения бордера длины <tex>k</tex> строки <tex>\alpha</tex>: 
<ul><tex>\forall i = 1 \ldots k</tex>, <tex>\alpha [i] = \alpha[i + (n - k)]</tex>. </ul>
Сделаем замену <tex>x = n - k</tex>: 
<ul><tex>\forall i = 1 \ldots n - x</tex>, <tex>\alpha [i] = \alpha[i + x]</tex>.</ul>
Получили определение периода длины <tex>x</tex>. Но <tex>x = n - k</tex>, значит у строки <tex>\alpha</tex> есть период длины <tex>n - k</tex>.
}}

==Свойства периода==
{{Теорема
|statement= Если у строки есть [[Основные определения, связанные со строками#Отношения между строками|период]] длины <tex>k</tex>, то у нее есть период длины <tex>kx</tex>, где <tex> x \in N</tex>.
|proof=
Пусть длина строки равна <tex>n</tex>, сама строка {{---}} <tex>\alpha</tex>. 
Доказательство будем вести по индукции по числу <tex>x</tex>. 
<ol>
<li>Для <tex> x = 1 </tex> утверждение очевидно.</li>
<li>Пусть верно для <tex>x \leqslant m</tex>.</li>
<li>Докажем, что верно для <tex>x = m + 1</tex>. 
Из определения периода имеем, что 
<ul><tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>,</ul>
а из предположения индукции, что 
<ul><tex>\forall i = 1 \ldots n - km</tex>, <tex>\alpha [i] = \alpha[i + mk]</tex></ul>
Значит получаем, что 
<ul><tex>\forall i = 1 \ldots n - km - k</tex>, <tex>\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>,</ul>
следовательно 
<ul>для <tex>\forall i = 1 \ldots n - k(m + 1)</tex>, <tex>\alpha [i] = \alpha[i + k(m + 1)]</tex>.</ul>
Значит у строки есть период длины <tex>k(m + 1)</tex>. </li>
</ol>
Утверждение доказано.
}}

{{Теорема
|statement= Если у строки есть периоды длины <tex>p</tex> и <tex>q</tex>, то НОД<tex>(p, q)</tex> также является периодом этой строки.
|proof=
Пусть строка равна <tex> \alpha </tex>. 
Доказательство будем вести по индукции по парам <tex>(p, q)</tex>, где <tex> p \geqslant q </tex>, а <tex>(p, q) + 1 = \begin{cases} (p, q + 1), & q < p;\\
(p + 1, 1), & q = p.\end{cases}</tex> 
<ol>
<li>Для <tex> (1, 1) </tex> утверждение очевидно.</li>
<li>Пусть верно для всех пар меньших <tex>(p, q)</tex>.</li>
<li>Докажем, что верно для <tex>(p, q)</tex>. 
Из определения периода: 
<ul><tex>\forall i = 1 \ldots n - p</tex>, <tex>\alpha [i] = \alpha[i + p] = \alpha[i + q]</tex>.</ul>
Значит <ul><tex>\forall i = q \ldots n - p</tex>, <tex>\alpha [i + q] = \alpha[i + p]</tex></ul>
Сделаем замену <tex>j = i + q</tex> и получим, что 
<ul><tex>\forall j = 1 \ldots n - (p - q)</tex>, <tex>\alpha [j] = \alpha[j + (p - q)]</tex></ul>
Получили новый период длины <tex>p - q</tex>. Из предположения известно, что НОД<tex>(p - q, q)</tex> {{---}} период строки, но НОД<tex>(p - q, q)</tex><tex>=</tex>НОД<tex>(p, q)</tex>.</li>
</ol>
Следовательно утверждение доказано.
}}

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]