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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
==Определение==
 
==Определение==
 
{{Определение
 
{{Определение
|definition='''Морфизмом''' называется отображение <tex>h</tex>, которое каждоый букве <tex>\lambda</tex> из алфавита <tex>A</tex> ставит в соответствие строку <tex>h(\lambda)</tex> из множества <tex>A^{+}</tex>.
+
|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</tex> из множества <tex>A^{+}</tex> путем использования следующего тождества:<br>
 
<tex>h(x) = h(x[1])h(x[2])...h(x[n])</tex>.<br>
 
Для полноты распространим отбражение на множество <tex>A^{*}</tex>, положив, что для любого морфизма <tex>h(\epsilon) = \epsilon</tex>.
 
  
 
Любой морфизм <tex>h</tex> можно применять к исходной строке <tex>x_0</tex> любое число раз, тем самым генерируя последовательность итераций <tex>h^{*}(x_0)</tex> по следующему правилу: <br>
 
Любой морфизм <tex>h</tex> можно применять к исходной строке <tex>x_0</tex> любое число раз, тем самым генерируя последовательность итераций <tex>h^{*}(x_0)</tex> по следующему правилу: <br>
Строка 33: Строка 33:
 
* <tex>f_5 = abaababa</tex>
 
* <tex>f_5 = abaababa</tex>
  
==Леммы==
+
==Лемма==
 
{{Лемма
 
{{Лемма
|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>f_n = f_{n-1} + f_{n-2}, n \geq 2</tex>.
+
|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>f_n = f_{n-1}f_{n-2}, n \geq 2</tex>.
 
|proof=
 
|proof=
 
Доказательство нетрудно получить методом математической индукции.  
 
Доказательство нетрудно получить методом математической индукции.  
Строка 41: Строка 41:
 
База. При <tex>n = 2</tex> равенство очевидно.
 
База. При <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(x+y) = h(x) + h(y)</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>   
+
<tex>f_{n+1} = h(f_{n-1})h(f_{n-2}) = f_{n}f_{n-1}</tex>   
 
}}
 
}}
  

Версия 17:03, 26 апреля 2012

Определение

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

а каждой строке [math]x[/math] из [math]A^+[/math] ставит в соответсвие строку из [math]A^+[/math] по следующему правилу :

[math]h(x) = h(x[1])h(x[2])...h(x[n])[/math] , где [math]x[1], x[2], \dots, x[n][/math] уже являются элементами [math]A[/math].


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