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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства периода)
(Свойства периода)
Строка 24: Строка 24:
 
   <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>,<br/>
 
   <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>,<br/>
 
а из <b>предположения</b> индукции, что<br/>
 
а из <b>предположения</b> индукции, что<br/>
   <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + mk]</tex><br/>
+
   <tex>\forall i = 1 \ldots n - km</tex>, <tex>\alpha [i] = \alpha[i + mk]</tex><br/>
 
Значит получаем, что<br/>
 
Значит получаем, что<br/>
   <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>,<br/>
+
   <tex>\forall i = 1 \ldots n - k(m + 1)</tex>, <tex>\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>,<br/>
 
следовательно<br/>
 
следовательно<br/>
       для <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + (m + 1)k]</tex>.<br/>
+
       для <tex>\forall i = 1 \ldots n - k(m + 1)</tex>, <tex>\alpha [i] = \alpha[i + (m + 1)k]</tex>.<br/>
 
Значит у строки есть <b>период длины</b> <tex>(m + 1)k</tex>.<br/></li>
 
Значит у строки есть <b>период длины</b> <tex>(m + 1)k</tex>.<br/></li>
 
</ol>
 
</ol>

Версия 16:04, 25 апреля 2012

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

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

Пусть дана строка [math]\alpha[/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]kx[/math], где [math] x \in N[/math].
Доказательство:
[math]\triangleright[/math]

Пусть длина строки равна [math]n[/math], сама строка[math]\alpha[/math].
Доказательство будем вести по индукции по числу [math]x[/math].

  1. Для [math] x = 1 [/math] утверждение очевидно.
  2. Пусть верно для [math]x \leqslant m[/math].
  3. Докажем, что верно для [math]x = m + 1[/math].
    Из определения периода имеем, что
    [math]\forall i = 1 \ldots n - k[/math], [math]\alpha [i] = \alpha[i + k][/math],
    а из предположения индукции, что
    [math]\forall i = 1 \ldots n - km[/math], [math]\alpha [i] = \alpha[i + mk][/math]
    Значит получаем, что
    [math]\forall i = 1 \ldots n - k(m + 1)[/math], [math]\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k][/math],
    следовательно
    для [math]\forall i = 1 \ldots n - k(m + 1)[/math], [math]\alpha [i] = \alpha[i + (m + 1)k][/math].
    Значит у строки есть период длины [math](m + 1)k[/math].
Утверждение доказано.
[math]\triangleleft[/math]
Теорема:
Если у строки есть периоды длины [math]p[/math] и [math]q[/math], то НОД[math](p, q)[/math] также является периодом этой строки.
Доказательство:
[math]\triangleright[/math]

Пусть строка равна [math] \alpha [/math].
Доказательство будем вести по индукции по парам [math](p, q)[/math], где [math] p \geqslant q [/math], а [math](p, q) + 1 = \begin{cases} (p, q + 1), & q \lt p;\\ (p + 1, 1), & q = p.\end{cases}[/math]

  1. Для [math] (1, 1) [/math] утверждение очевидно.
  2. Пусть верно для всех пар меньших [math](p, q)[/math].
  3. Докажем, что верно для [math](p, q)[/math].
    Из определения периода:
    [math]\forall i = 1 \ldots n - p[/math], [math]\alpha [i] = \alpha[i + p] = \alpha[i + q][/math].
    Значит [math]\forall i = q \ldots n - p[/math], [math]\alpha [i + q] = \alpha[i + p][/math]
    Сделаем замену [math]j = i + q[/math] и получим, что
    [math]\forall j = 1 \ldots n - (p - q)[/math], [math]\alpha [j] = \alpha[j + (p - q)][/math]
    Получили новый период длины [math]p - q[/math]. Из предположения известно, что НОД[math](p - q, q)[/math] — период строки, но НОД[math](p - q, q)[/math][math]=[/math]НОД[math](p, q)[/math].
Следовательно утверждение доказано.
[math]\triangleleft[/math]