Период и бордер, их связь — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства периода)
Строка 12: Строка 12:
 
==Свойства периода==
 
==Свойства периода==
 
{{Теорема
 
{{Теорема
|statement= Если у строки есть [[Основные определения, связанные со строками|период]] длины <tex>k</tex>, то у нее есть период длины <tex>(k * x)</tex>, где <tex> x \in N</tex>.
+
|statement= Если у строки есть [[Основные определения, связанные со строками|период]] длины <tex>k</tex>, то у нее есть период длины <tex>(k \cdot x)</tex>, где <tex> x \in N</tex>.
 
|proof=
 
|proof=
 
Пусть Длина строки равна <tex>n</tex>. Тогда из определения периода имеем, что<br/>
 
Пусть Длина строки равна <tex>n</tex>. Тогда из определения периода имеем, что<br/>
Строка 18: Строка 18:
 
Это вернео для всех таких <tex>i</tex>, значит получаем <br/>
 
Это вернео для всех таких <tex>i</tex>, значит получаем <br/>
 
<tex>\alpha [i] = \alpha[i + k]</tex>.<br/>
 
<tex>\alpha [i] = \alpha[i + k]</tex>.<br/>
<tex>\alpha [i + k] = \alpha[i + 2* k]</tex>.<br/>
+
<tex>\alpha [i + k] = \alpha[i + 2k]</tex>.<br/>
<tex>\alpha [i + 2 * k] = \alpha[i + 3 * k]</tex>.<br/>
+
<tex>\alpha [i + 2k] = \alpha[i + 3k]</tex>.<br/>
 
<tex> \ldots </tex><br/>
 
<tex> \ldots </tex><br/>
<tex>\alpha [i + (x - 1) * k] = \alpha[i + x * k]</tex>.<br/>
+
<tex>\alpha [i + (x - 1) \cdot k] = \alpha[i + x \cdot k]</tex>.<br/>
Следовательно для <tex>\forall i = 1 \ldots n - x * k</tex>, <tex>\alpha [i] = \alpha[i + x *k]</tex>.<br/>
+
Следовательно для <tex>\forall i = 1 \ldots n - x \cdot k</tex>, <tex>\alpha [i] = \alpha[i + x \cdot k]</tex>.<br/>
Значит у строки есть период длины <tex>(k * x)</tex>.
+
Значит у строки есть период длины <tex>(k \cdot x)</tex>.
 
}}
 
}}
  

Версия 16:41, 7 апреля 2012

Связь периода и бордера

Теорема:
Если у строки длины [math]n[/math] есть бордер длины [math]k[/math], то у нее есть период длины [math](n - k)[/math].
Доказательство:
[math]\triangleright[/math]

Напишем формально определения бордера длины [math]k[/math] строки [math]\alpha[/math]:
[math]\forall i = 1 \ldots k[/math], [math]\alpha [i] = \alpha[i + (n - k)][/math].
Сделаем замену [math]x = n - k[/math]:
[math]\forall i = 1 \ldots n - x[/math], [math]\alpha [i] = \alpha[i + x][/math].

Получили определение периода длины [math]x[/math]. Но [math]x = n - k[/math], значит у строки [math]\alpha[/math] есть период длины [math](n - k)[/math].
[math]\triangleleft[/math]

Свойства периода

Теорема:
Если у строки есть период длины [math]k[/math], то у нее есть период длины [math](k \cdot x)[/math], где [math] x \in N[/math].
Доказательство:
[math]\triangleright[/math]

Пусть Длина строки равна [math]n[/math]. Тогда из определения периода имеем, что
[math]\forall i = 1 \ldots n - k[/math], [math]\alpha [i] = \alpha[i + k][/math].
Это вернео для всех таких [math]i[/math], значит получаем
[math]\alpha [i] = \alpha[i + k][/math].
[math]\alpha [i + k] = \alpha[i + 2k][/math].
[math]\alpha [i + 2k] = \alpha[i + 3k][/math].
[math] \ldots [/math]
[math]\alpha [i + (x - 1) \cdot k] = \alpha[i + x \cdot k][/math].
Следовательно для [math]\forall i = 1 \ldots n - x \cdot k[/math], [math]\alpha [i] = \alpha[i + x \cdot k][/math].

Значит у строки есть период длины [math](k \cdot x)[/math].
[math]\triangleleft[/math]
Теорема:
Если у строки есть периоды длины [math]p[/math] и [math]q[/math], то НОД[math](p, q)[/math] также является периодом этой строки.
Доказательство:
[math]\triangleright[/math]

Пусть [math] p \gt q [/math], тогда
для [math]\forall i = 1 \ldots n - q[/math], [math]\alpha [i] = \alpha[i + p] = \alpha[i + q][/math].
Значит для [math]\forall i = 1 \ldots n - (p - q)[/math], [math]\alpha [i] = \alpha[i + (p - q)][/math]
Теперь следуя алгоритму Евклида, если [math] q \gt = p - q [/math] получим [math]\alpha [i] = \alpha[i + (q - (p - q))][/math],
иначе [math]\alpha [i] = \alpha[i + (p - q) - q][/math].

Будем выполнять такие действия, пока не получим НОД[math](p, q)[/math]. Это будет выполнятся для [math]\forall i [/math]. Следовательно будет период длины НОД[math](p, q)[/math].
[math]\triangleleft[/math]