Период и бордер, их связь - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:17:28Z

rollbackEdits.php mass rollback

185.86.148.90 в 05:39, 1 сентября 2022

2022-09-01T05:39:39Z

Shersh в 18:39, 15 февраля 2015

2015-02-15T18:39:45Z

88.201.136.78: /* Связь периода и бордера */

2014-06-09T21:06:23Z

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

Pasha26007 в 19:02, 9 июня 2014

2014-06-09T19:02:44Z

Martoon: /* Источники информации */

2014-06-07T12:40:37Z

‎Источники информации

Martoon: /* Литература */

2014-06-05T18:42:23Z

‎Литература

Martoon: /* Теорема о НОД периодов */

2014-06-04T19:26:45Z

‎Теорема о НОД периодов

Martoon: /* Теорема о НОД периодов */

2014-06-04T19:22:52Z

‎Теорема о НОД периодов

Martoon: /* Теорема о НОД периодов */

2014-05-25T16:16:37Z

‎Теорема о НОД периодов

← Предыдущая		Версия 16:17, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	==Связь периода и бордера==		==Связь периода и бордера==
	{{Теорема		{{Теорема

← Предыдущая		Версия 05:39, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	==Связь периода и бордера==		==Связь периода и бордера==
	{{Теорема		{{Теорема

@@ Строка 14: / Строка 14: @@
 ==Свойства периода==
 {{Теорема
 |statement= Если у строки есть период длины <tex>k</tex>, то у нее имеется также период длины <tex>kx</tex>, где <tex> x \in N</tex>.
 |proof=
@@ Строка 39: / Строка 39: @@
 }}
 Перед доказательством следующей теоремы проверим пару интуитивно понятных утверждений.

@@ Строка 1: / Строка 1: @@
 ==Связь периода и бордера==
 {{Теорема
-|statement= Если у строки длины <tex>n</tex> есть [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F,_%D1%81%D0%B2%D1%8F%D0%B7%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D1%81%D0%BE_%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B0%D0%BC%D0%B8#.D0.9E.D1.82.D0.BD.D0.BE.D1.88.D0.B5.D0.BD.D0.B8.D1.8F_.D0.BC.D0.B5.D0.B6.D0.B4.D1.83_.D1.81.D1.82.D1.80.D0.BE.D0.BA.D0.B0.D0.BC.D0.B8 бордер] длины <tex>k</tex>, то у нее также имеется [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F,_%D1%81%D0%B2%D1%8F%D0%B7%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D1%81%D0%BE_%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B0%D0%BC%D0%B8#.D0.9E.D1.82.D0.BD.D0.BE.D1.88.D0.B5.D0.BD.D0.B8.D1.8F_.D0.BC.D0.B5.D0.B6.D0.B4.D1.83_.D1.81.D1.82.D1.80.D0.BE.D0.BA.D0.B0.D0.BC.D0.B8 период] длины <tex>n - k</tex>.
+|statement= Если у строки длины <tex>n</tex> есть [[Основные определения, связанные со строками#border | бордер]] длины <tex>k</tex>, то у нее также имеется [[Основные определения, связанные со строками#period | период]] длины <tex>n - k</tex>.
 |proof=
 Пусть дана строка <tex>\alpha</tex>.

@@ Строка 1: / Строка 1: @@
 ==Связь периода и бордера==
 {{Теорема
-|statement= Если у строки длины <tex>n</tex> есть бордер длины <tex>k</tex>, то у нее также имеется период длины <tex>n - k</tex>.
+|statement= Если у строки длины <tex>n</tex> есть [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F,_%D1%81%D0%B2%D1%8F%D0%B7%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D1%81%D0%BE_%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B0%D0%BC%D0%B8#.D0.9E.D1.82.D0.BD.D0.BE.D1.88.D0.B5.D0.BD.D0.B8.D1.8F_.D0.BC.D0.B5.D0.B6.D0.B4.D1.83_.D1.81.D1.82.D1.80.D0.BE.D0.BA.D0.B0.D0.BC.D0.B8 бордер] длины <tex>k</tex>, то у нее также имеется [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F,_%D1%81%D0%B2%D1%8F%D0%B7%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D1%81%D0%BE_%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B0%D0%BC%D0%B8#.D0.9E.D1.82.D0.BD.D0.BE.D1.88.D0.B5.D0.BD.D0.B8.D1.8F_.D0.BC.D0.B5.D0.B6.D0.B4.D1.83_.D1.81.D1.82.D1.80.D0.BE.D0.BA.D0.B0.D0.BC.D0.B8 период] длины <tex>n - k</tex>.
 |proof=
 Пусть дана строка <tex>\alpha</tex>.

@@ Строка 111: / Строка 111: @@
 == Источники информации ==
 * [[wikipedia:en:Substring | Wikipedia {{---}} Substring ]]
-* Lothaire M. Algebraic Combinatorics on Words {{---}} Cambridge University Press, 2002. {{---}} с. 272. {{---}} ISBN 0-521-81220-8
+* ''Lothaire M.'' Algebraic Combinatorics on Words {{---}} Cambridge University Press, 2002. {{---}} с. 272. {{---}} ISBN 0-521-81220-8
 [[Категория:Алгоритмы и структуры данных]]
 [[Категория:Основные определения. Простые комбинаторные свойства слов]]

@@ Строка 91: / Строка 91: @@
 |proof=Обозначим <tex> r = \gcd(p, q) </tex>. Доказательство будем вести индукцией по <tex> n = (p + q) / r </tex>.
-В случае <tex> p = q </tex> видим что <tex> n = 2 </tex>, что соответствует базе, в то время как при <tex> p \ne q </tex> выполнено <tex> p, q > \gcd(p, q) </tex>, так что <tex> n > 2 </tex>.
+В случае <tex> p = q </tex> видим что <tex> n = 2 </tex>, что соответствует базе, в то время как при <tex> p \ne q </tex> выполнено <tex> \max(p, q) > \gcd(p, q) </tex>, так что <tex> n > 2 </tex>.
 * База
 *: Истинность утверждения следует из <tex> p = q = r </tex>.

@@ Строка 57: / Строка 57: @@
 {{Лемма
 |about=1
-|statement= Пусть строка <tex> s </tex> имеет периоды <tex> p </tex> и <tex> q </tex>, причём <tex> p < q \leqslant |s| </tex>. Тогда суффикс и префикс <tex> s </tex> длины <tex> |s| - q </tex> имеют период <tex> p - q </tex>.
+|statement= Пусть строка <tex> s </tex> имеет периоды <tex> p </tex> и <tex> q </tex>, причём <tex> q < p \leqslant |s| </tex>. Тогда суффикс и префикс <tex> s </tex> длины <tex> |s| - q </tex> имеют период <tex> p - q </tex>.
 |proof= Покажем истинность утверждения про префикс; с суффиксом доказательство аналогичное.
@@ Строка 73: / Строка 73: @@
 Требуется показать: <tex> s_i = s_j \ (j = i + r,\ 1 \leqslant i, j \leqslant n) </tex>.
-Заметим, что поскольку <tex> |v| \geqslant q </tex> отрезок <tex> [h, k] </tex> содержит по меньшей мере <tex> q </tex> целых чисел, так что найдутся <tex>  i',\ j' \in [h, k]: \ \ i \equiv i' \pmod q,\ j \equiv j' \pmod q </tex>.
+Зафиксируем <tex> i </tex> и <tex> j </tex>. Заметим, что поскольку <tex> |v| \geqslant q </tex>, отрезок <tex> [h, k] </tex> содержит по меньшей мере <tex> q </tex> целых чисел, так что найдутся <tex>  i',\ j' \in [h, k]: \ \ i \equiv i' \pmod q,\ j \equiv j' \pmod q,\ i \ne j </tex>.
 С учётом <tex> q </tex> <tex dpi=90>\,\vdots\, </tex> <tex> r </tex> можем написать <tex> i \equiv i' \pmod r,\ j \equiv j' \pmod r </tex> <ref>[[Сравнения,_система_вычетов,_решение_линейных_систем_по_модулю#Свойства сравнений | Свойство сравнений (№8)]]</ref>.
@@ Строка 90: / Строка 90: @@
 |author=Фин и Вильф
 |proof=Обозначим <tex> r = \gcd(p, q) </tex>. Доказательство будем вести индукцией по <tex> n = (p + q) / r </tex>.
 * База
-*: При <tex> n = 2 </tex> видно, что <tex> p = q = r </tex> и потому утверждение истинно.
+*: Истинность утверждения следует из <tex> p = q = r </tex>.
 * Переход
-*: Заметим что теперь <tex> q \ne p </tex> (так как <tex> n > 2 </tex>), потому без ограничения общности считаем <tex> q < p </tex>.
+*: В силу того, что <tex> p \ne q </tex>, без ограничения общности будем считать <tex> q < p </tex> (вообще говоря, исходя из свойств НОД можно дать более строгую оценку: <tex> p - q \geqslant r </tex>, чем мы позже воспользуемся).
 *: Пусть <tex> w = uv </tex>, где <tex> |u| = q </tex>.
 *: По '''лемме 1''' <tex> v </tex> имеет период <tex> p - q </tex>, также <tex> v </tex> имеет период <tex> q </tex> как подстрока <tex> w </tex>. Теперь рассмотрим длину <tex> v </tex>:
 *: <tex> |v| = |w| - q \geqslant (p + q - r) - q \geqslant (p - q) + q - r = (p - q) + q - \gcd(p - q, q) </tex>.
-*: Таким образом по предположению индукции получаем, что <tex> v </tex> также имеет период <tex> \gcd(p-q, q)</tex>. Учитывая <tex> \gcd(p-q, q) = \gcd(p, q) = r </tex>, можем сказать что <tex> v </tex> имеет период <tex> r </tex>.
+*: Ещё заметим, что для периодов <tex> p - q,\ q </tex> будет меньшее <tex> n </tex>, нежели чем для <tex> p,\ q </tex>, поскольку <tex> \gcd(p-q, q) = \gcd(p, q) </tex>. А тогда по предположению индукции заключаем: <tex> v </tex> имеет период <tex> \gcd(p-q, q)</tex>. Учитывая <tex> \gcd(p-q, q) = \gcd(p, q) = r </tex>, можем сказать что <tex> v </tex> имеет период <tex> r </tex>.
-*: Ещё одно наблюдение: <tex> p - q \geqslant r </tex> (<tex> p > q </tex> и по свойствам НОД), поэтому <tex> |v| \geqslant (p - q) + q - r \geqslant q </tex>, в следствие чего по '''лемме 2''' <tex> w </tex> имеет период <tex> r </tex>.
+*: Как уже упоминалось, <tex> p - q \geqslant r </tex>, поэтому <tex> |v| \geqslant (p - q) + q - r \geqslant q </tex>, в следствие чего по '''лемме 2''' <tex> w </tex> имеет период <tex> r </tex>.
 }}

@@ Строка 53: / Строка 53: @@
 ==Теорема о НОД периодов==
-Перед доказательством следующей теоремы докажем пару интуитивно паонятных утверждений.
+Перед доказательством следующей теоремы проверим пару интуитивно понятных утверждений.
 {{Лемма
@@ Строка 73: / Строка 73: @@
 Требуется показать: <tex> s_i = s_j \ (j = i + r,\ 1 \leqslant i, j \leqslant n) </tex>.
-Заметим, что поскольку <tex> |v| \geqslant q </tex>, то отрезок <tex> [h, k] </tex> содержит ровно <tex> q </tex> целых чисел, так что найдутся <tex>  i',\ j' \in [h, k]: \ \ i \equiv i' \pmod q,\ j \equiv j' \pmod q </tex>.
+Заметим, что поскольку <tex> |v| \geqslant q </tex> отрезок <tex> [h, k] </tex> содержит по меньшей мере <tex> q </tex> целых чисел, так что найдутся <tex>  i',\ j' \in [h, k]: \ \ i \equiv i' \pmod q,\ j \equiv j' \pmod q </tex>.
 С учётом <tex> q </tex> <tex dpi=90>\,\vdots\, </tex> <tex> r </tex> можем написать <tex> i \equiv i' \pmod r,\ j \equiv j' \pmod r </tex> <ref>[[Сравнения,_система_вычетов,_решение_линейных_систем_по_модулю#Свойства сравнений | Свойство сравнений (№8)]]</ref>.
@@ Строка 79: / Строка 79: @@
 Помимо того <tex> i \equiv j \pmod r </tex>, а в таком случае верно и <tex> i' \equiv j' \pmod r </tex>.
-Теперь воспользуемся следующим фактом: если строка <tex> s </tex> имеет период <tex> r </tex>, то <tex> i \equiv j \pmod r \ \Rightarrow\ s_i = s_j </tex>  (действительно, без ограничения общности можем сказать, что <tex> i \leqslant j </tex>, исходя из чего можем выстроить цепочку равенств <tex> s_i = s_{i + r},\ \ s_{i + r} = s_{i + 2r},\ \ \dots \ , \ s_{j - r} = s_j </tex>).
+Теперь воспользуемся следующим фактом: если строка <tex> s </tex> имеет период <tex> r </tex>, то <tex> i \equiv j \pmod r \ \Rightarrow\ s_i = s_j </tex>  (действительно, без ограничения общности можем сказать, что <tex> i \leqslant j </tex>, и исходя из этого выстроить цепочку равенств <tex> s_i = s_{i + r},\ \ s_{i + r} = s_{i + 2r},\ \ \dots \ , \ s_{j - r} = s_j </tex>).
 В виду того, что <tex> w </tex> имеет период <tex> q </tex>, имеют место равенства <tex> s_i = s_{i'}\ </tex> и <tex>\ s_j = s_{j'} </tex>. Кроме того <tex> v </tex> имеет период <tex> r </tex>, потому верно <tex> s_{i'} = s_{j'} </tex>. Тогда и <tex> s_i = s_j </tex>.