Слово Фибоначчи — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Лемма: fixup)
(Fixing bugs in definition. Some irrelevant renaming.)
Строка 1: Строка 1:
 
==Определение==
 
==Определение==
 
{{Определение
 
{{Определение
|definition='''Морфизмом''' называется отображение <tex>h</tex>, которое каждой букве <tex>\lambda</tex> из алфавита <tex>A</tex> ставит в соответствие строку <tex>h(\lambda)</tex> из множества <tex>A^{+}</tex>,  
+
|definition='''Морфизмом''' называется отображение <tex>h_0 : \Sigma^* \rightarrow \Sigma^*</tex>, которое каждой букве <tex>\lambda</tex> из алфавита <tex>\Sigma</tex> ставит в соответствие строку <tex>h(\lambda)</tex> из множества <tex>\Sigma^{+}</tex>,
а каждой строке <tex>x</tex> из <tex>A^+</tex> ставит в соответсвие строку из <tex>A^+</tex> по следующему правилу :
+
а затем данное отображение распространяется на <tex>\Sigma^*</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 : A \rightarrow A^+</tex>
+
<tex>h(s) =  
*<tex>h : A^+ \rightarrow A^+</tex>
+
\left\{ \begin{array}{ll}
 +
            h_0(s[1])h_0(s[2])...h_0(s[n]), & s \in \Sigma^+ \\
 +
            \varepsilon, & s \in \Sigma^0 \\
 +
        \end{array}
 +
\right. </tex>
 +
 
 
}}
 
}}
  
Любой морфизм <tex>h</tex> можно применять к исходной строке <tex>x_0</tex> любое число раз, тем самым генерируя последовательность итераций <tex>h^{*}(x_0)</tex> по следующему правилу: <br>
+
Любой морфизм <tex>h</tex> можно применять к исходной строке <tex>s</tex> любое число раз, тем самым генерируя последовательность итераций <tex>h^{*}(s)</tex> по следующему правилу: <br>
<ul><tex>h^{*}(x_0) = \{h^0(x_0), h^1(x_0),...\}</tex>. </ul>
+
<ul><tex>h^{*}(s) = \{h^0(s), h^1(s),...\}</tex>. </ul>
где <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>h^0(s) = s</tex> и для любого целого <tex>k \geq 1 :</tex> <tex> h^k(s) = h(h^{k-1}(s))</tex>.  
  
 
'''Например''':
 
'''Например''':
  
*<tex>A = \{a,b\}, h(a) = a, h(b) = ab</tex>.  
+
*<tex>\Sigma = \{a,b\}, h(a) = a, h(b) = ab</tex>.  
  
 
*<tex>h^*(a) = \{a,a,...\}</tex>  
 
*<tex>h^*(a) = \{a,a,...\}</tex>  
Строка 22: Строка 27:
  
 
{{Определение
 
{{Определение
|definition='''Строками Фибоначчи''' являются строки, полученные последовательным применением морфизма <tex>h</tex> к строке <tex>x_0 = b</tex>, т.е. <tex>h^*(b)</tex>.
+
|definition='''Строками Фибоначчи''' являются строки над алфавитом <tex>\Sigma = \{a, b\}</tex>, полученные последовательным применением морфизма <tex>h</tex>:
* <tex>A = \{a,b\}</tex>
 
 
* <tex>h(a) = ab</tex>  
 
* <tex>h(a) = ab</tex>  
 
* <tex>h(b) = a</tex>
 
* <tex>h(b) = a</tex>
 
+
к строке <tex>x_0 = b</tex>, т.е. <tex>h^*(b)</tex>.
  
 
}}
 
}}
Строка 53: Строка 57:
 
Также нетрудно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.
 
Также нетрудно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.
  
== Литература ==
+
== См. также ==
 +
[[Слово Туэ-Морса]]
 +
 
 +
== Источники ==
 
* Билл Смит.  Методы и алгоритмы вычислений на строках. Пер. с англ. — М.:ООО"И.Д.Вильямс", 2006. — 496 с.: ил. — Парал. тит. англ. ISBN 5-8459-1081-1 (рус.)
 
* Билл Смит.  Методы и алгоритмы вычислений на строках. Пер. с англ. — М.:ООО"И.Д.Вильямс", 2006. — 496 с.: ил. — Парал. тит. англ. ISBN 5-8459-1081-1 (рус.)
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Версия 22:32, 1 июня 2012

Определение

Определение:
Морфизмом называется отображение [math]h_0 : \Sigma^* \rightarrow \Sigma^*[/math], которое каждой букве [math]\lambda[/math] из алфавита [math]\Sigma[/math] ставит в соответствие строку [math]h(\lambda)[/math] из множества [math]\Sigma^{+}[/math],

а затем данное отображение распространяется на [math]\Sigma^*[/math] следующим образом:

[math]h(s) = \left\{ \begin{array}{ll} h_0(s[1])h_0(s[2])...h_0(s[n]), & s \in \Sigma^+ \\ \varepsilon, & s \in \Sigma^0 \\ \end{array} \right. [/math]


Любой морфизм [math]h[/math] можно применять к исходной строке [math]s[/math] любое число раз, тем самым генерируя последовательность итераций [math]h^{*}(s)[/math] по следующему правилу:

    [math]h^{*}(s) = \{h^0(s), h^1(s),...\}[/math].

где [math]h^0(s) = s[/math] и для любого целого [math]k \geq 1 :[/math] [math] h^k(s) = h(h^{k-1}(s))[/math].

Например:

  • [math]\Sigma = \{a,b\}, h(a) = a, h(b) = ab[/math].
  • [math]h^*(a) = \{a,a,...\}[/math]
  • [math]h^*(b) = \{b, ab, a^2b,..., a^kb...\}[/math]


Определение:
Строками Фибоначчи являются строки над алфавитом [math]\Sigma = \{a, b\}[/math], полученные последовательным применением морфизма [math]h[/math]:
  • [math]h(a) = ab[/math]
  • [math]h(b) = a[/math]
к строке [math]x_0 = b[/math], т.е. [math]h^*(b)[/math].


Первые несколько строк Фибоначчи:

  • [math]f_0 = b[/math]
  • [math]f_1 = a[/math]
  • [math]f_2 = ab[/math]
  • [math]f_3 = aba[/math]
  • [math]f_4 = abaab[/math]
  • [math]f_5 = abaababa[/math]

Лемма

Лемма:
Строки Фибоначчи удовлетворяют рекуррентному соотношению [math]f_n = f_{n-1}f_{n-2}, n \geq 2[/math].
Доказательство:
[math]\triangleright[/math]

Доказательство нетрудно получить методом математической индукции.

База: При [math]n = 2[/math] равенство очевидно.

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

[math]f_{n+1} = h(f_{n-1})h(f_{n-2}) = f_{n}f_{n-1}[/math].
[math]\triangleleft[/math]

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

См. также

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

Источники

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