http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=91.122.187.31&*
Викиконспекты - Вклад участника [ru]
2026-04-06T10:17:27Z
Вклад участника
MediaWiki 1.30.0
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BB%D0%BE%D0%B2%D0%BE_%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8&diff=25475
Слово Фибоначчи
2012-06-16T18:25:20Z
<p>91.122.187.31: </p>
<hr />
<div>==Определение==<br />
{{Определение<br />
|definition='''Морфизмом''' называется отображение <tex>h : \Sigma^* \rightarrow \Sigma^*</tex>, которое каждой букве <tex>\lambda</tex> из алфавита <tex>\Sigma</tex> ставит в соответствие строку <tex>h(\lambda)</tex> из множества <tex>\Sigma^{+}</tex>,<br />
затем данное отображение распространяется на <tex>\Sigma^*</tex> следующим образом:<br />
<br />
<tex>h(s) = <br />
\left\{ \begin{array}{ll} <br />
h(s[1])h(s[2])...h(s[n]), & s \in \Sigma^+ \\<br />
\varepsilon, & s \in \Sigma^0 \\<br />
\end{array}<br />
\right. </tex><br />
<br />
}}<br />
<br />
Любой морфизм <tex>h</tex> можно применять к исходной строке <tex>s</tex> любое число раз, тем самым генерируя последовательность итераций <tex>h^{*}(s)</tex> по следующему правилу: <br><br />
<ul><tex>h^{*}(s) = \{h^0(s), h^1(s),...\}</tex>. </ul><br />
где <tex>h^0(s) = s</tex> и для любого целого <tex>k \geq 1 :</tex> <tex> h^k(s) = h(h^{k-1}(s))</tex>. <br />
<br />
'''Например''':<br />
<br />
*<tex>\Sigma = \{a,b\}, h(a) = a, h(b) = ab</tex>. <br />
<br />
*<tex>h^*(a) = \{a,a,...\}</tex> <br />
<br />
*<tex>h^*(b) = \{b, ab, a^2b,..., a^kb...\}</tex><br />
<br />
<br />
{{Определение<br />
|definition='''Строками Фибоначчи''' являются строки над алфавитом <tex>\Sigma = \{a, b\}</tex>, полученные последовательным применением морфизма <tex>h</tex>:<br />
* <tex>h(a) = ab</tex> <br />
* <tex>h(b) = a</tex><br />
к строке <tex>s = b</tex>, т.е. <tex>h^*(b)</tex>.<br />
<br />
}}<br />
<br />
Первые несколько строк Фибоначчи: <br />
<br />
* <tex>f_0 = b</tex><br />
* <tex>f_1 = a</tex><br />
* <tex>f_2 = ab</tex><br />
* <tex>f_3 = aba</tex><br />
* <tex>f_4 = abaab</tex><br />
* <tex>f_5 = abaababa</tex><br />
<br />
==Лемма==<br />
{{Лемма<br />
|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>f_n = f_{n-1}f_{n-2}, n \geq 2</tex>.<br />
|proof=<br />
Доказательство нетрудно получить методом математической индукции. <br />
<br />
'''База:''' При <tex>n = 2</tex> равенство очевидно.<br />
<br />
'''Переход:''' Пусть <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>), то можно продолжить равенство:<br />
<tex>f_{n+1} = h(f_{n-1})h(f_{n-2}) = f_{n}f_{n-1}</tex>.<br />
}}<br />
<br />
Также можно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.<br />
<br />
<!--<br />
==Теорема==<br />
===Вспомогательные леммы и опредления===<br />
Начнем обобщение идеи строк Фибоначчи следующим образом. Вместо отдельных символов <tex>a</tex> и <tex>b</tex> будем оперировать двумя произвольными строками <tex>x,y \in \Sigma^*</tex>:<br />
*<tex>h(x) = xy</tex><br />
*<tex>h(y) = x</tex><br />
Таким образом "старый" морфизм будет частным случаем "нового" морфизма при <tex>x = a</tex> и <tex>y = b</tex>.<br />
<br />
По аналогии можно вычислить <tex>h^*(y) = \{y, x, xy, xyx, \dots\}</tex>, и ,наконец, определить n-ую обобщенную строку Фибоначчи как:<br />
{{Определение<br />
|definition=Обобщенная строка Фибоначчи имеет вид <tex>f_n(x,y) = h^n(y)</tex><br />
}}<br />
<br />
Первые несколько обобщенных строк имеют вид:<br />
*<tex>f_0(x,y) = y</tex><br />
*<tex>f_1(x,y) = x</tex><br />
*<tex>f_2(x,y)= xy</tex><br />
*<tex>f_3(x,y)= xyx</tex><br />
*<tex>f_4(x,y) = xyxxy</tex><br />
А также в общем случае:<br />
*<tex>f_n(x,y) = f_{n-1}(x,y)f_{n-2}(x,y)</tex><br />
<br />
{{Определение<br />
|definition=Определим '''бесконечную обобщенную строку Фибоначчи <tex>f_{\infty}(x,y)</tex>''' как строку, содержащую все строки <tex>f_n(x,y), n \geq 0</tex> в качестве префиксов<br />
}}<br />
<br />
Поскольку <tex>h^n(y) = h^{n-k}(h^k(y))</tex>, то <tex>f_n(x,y) = h^k(f_{n-k}(x,y)) = f_{n-k}(h^k(x),h^k(y))</tex>, и, так как <tex>h^k(x) = h^{k+1}(y)</tex>, финально получаем:<br />
*<tex>f_n = f_{n-k}(f_{k+1},f_k)</tex>.<br />
'''Например''':<br />
<tex>f_7 = f_5(f_3, f_2) = (xyx)(xy)(xyx)(xyx)(xy)(xyx)(xy)(xyx)</tex><br />
<br />
Это равенство походит также и для <tex>f_{\infty}: f_{\infty} = f_{\infty}(f_{n+1},f_{n}) = f_{n+1}f_n f_{n+1} f_{n+1} f_n f_{n+1} f_n f_{n+1} \dots</tex><br />
<br />
<br />
Так же имеют место быть 2 простые леммы.<br />
{{Лемма<br />
|about = 1<br />
|statement=Для любого целого <tex>n \geq 2</tex> выполняется равенство <tex>f^2_n = f_{n+1}f_{n-2}</tex><br />
}}<br />
{{Лемма<br />
|about = 2<br />
|statement= Для любого целого <tex>n \geq 3</tex> строка <tex>f_n</tex> имеет грани <tex>f_i</tex> для <tex>i = n-2, n-4,\dots,2-(n\,\,mod \,\,2)</tex><br />
}}<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
{{Теорема<br />
|statement=Все строки Фибоначчи <tex>f_n</tex> при <tex>n \geq 7</tex> содержат кубы, но ни одна строка Фибоначчи не содержит кратных подстрок четвертого порядка<br />
|proof= <br />
}}<br />
<br />
--><br />
== См. также ==<br />
[[Слово Туэ-Морса]]<br />
<br />
== Источники ==<br />
* Билл Смит. Методы и алгоритмы вычислений на строках. Пер. с англ. — М.:ООО"И.Д.Вильямс", 2006. — 496 с.: ил. — Парал. тит. англ. ISBN 5-8459-1081-1 (рус.)<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Основные определения. Простые комбинаторные свойства слов]]</div>
91.122.187.31