Викиконспекты - Вклад участника [ru]

Основные определения, связанные со строками

2012-04-24T09:09:40Z

178.178.27.75: /* Отношения между строками */

== Базовые определения ==

{{Определение
|definition =
'''Алфавитом''' <tex>\sum</tex> называется конечное непустое множество элементов, называемых символами.
}}

{{Определение
|definition =
'''Цепочкой''' (словом, строкой) конечной длины обозначим <tex>\sum^* : \sum^* = \bigcup\limits_{n \in \mathbb N} \sum^n</tex>.
}}

{{Определение
|definition =
'''Конкатенацией''' строк <tex>\alpha = \sum^k</tex> и <tex>\beta = \sum^m</tex> является строка <tex>\alpha\beta = \sum^{k+m}</tex>. Конкатенация является ассоциативной операцией.
}}

{{Определение
|definition =
'''Нейтральным элементом''' (пустой строкой) <tex>\varepsilon \in \sum^{0}</tex> называется элемент, для которого верно <tex>\alpha\varepsilon=\varepsilon\alpha=\alpha</tex>.
}}

<tex>\Sigma^*</tex> с операцией конкатенации и нейтральным элементом <tex>\varepsilon</tex> образуют моноид. Данный моноид совпадает со свободным над <tex>\Sigma</tex>.

== Отношения между строками ==

{{Определение
|definition =
<tex>\alpha</tex> называется '''префиксом''' <tex>\beta</tex>, если <tex>\beta = \alpha \gamma</tex>. Аналогично определяется '''суффикс''' строки.
}}

Пусть <tex>\beta = abracadabra</tex>, тогда
*если <tex>\alpha = abrac</tex>, то <tex>\alpha</tex> является префиксом <tex>\beta</tex>
*если <tex>\alpha = adabra</tex>, то суффиксом.

{{Определение
|definition =
<tex>\alpha</tex> называется '''бордером''' <tex>\beta</tex>, если <tex>\alpha</tex> одновременно является и суффиксом и префиксом.
|id=border
}}

Пусть <tex>\beta = abracadabra</tex>, тогда <tex>\alpha = abra</tex> будет бордером <tex>\beta</tex>.

{{Определение
|definition =
<tex>p</tex> называется '''периодом''' <tex>\alpha</tex>, если <tex>\forall i = 1 \ldots n - p</tex> <tex>\alpha [i] = \alpha[i + p]</tex>.
|id=border
}}

{{Определение
|definition =
Пусть строка <tex>x = \sum^n</tex> имеет период <tex>p</tex>, <tex>r = n / p</tex> и <tex>u = \sum^p</tex>. Тогда декомпозиция <tex>x = u^p </tex> называется '''нормальной формой''' строковой последовательности <tex>x</tex>.
}}

{{Определение
|definition =
Строка <tex>x</tex> называется примитивной, если <tex>r = 1</tex>.
}}

{{Определение
|definition =
Если <tex>r \ge 2</tex>, то строка <tex>x</tex> называется '''сильнопериодической''', если <tex>1 < r < 2</tex>, то '''слабопериодической'''. Если <tex>r</tex> целое и <tex>r \ge 2</tex>, то строка <tex>x</tex> называется '''строгопериодической''' (или просто '''периодической''').
}}

Строка <tex>aaabaabab</tex> - примитивная <tex>(p = n)</tex>.

Строка <tex>abaababaabaab = (abaababa)(abaab)</tex> - слабопериодическая с периодом <tex>p = 8</tex>, порядком <tex>r = 13/8</tex>.

Строка <tex>abaabaab = (aba)^2(ab)</tex> - сильнопериодическая с периодом <tex>p = 3</tex>, порядком <tex>r = 8/3</tex>.

{{Определение
|definition =
Строка <tex>\alpha</tex> является '''подстрокой''' <tex>\beta</tex>, если <tex>\beta = \gamma \alpha \delta</tex>.
}}

Строка <tex>\alpha = aca</tex> является подстрокой <tex>\beta = abracadabra</tex>.

{{Определение
|definition =
Строка <tex>\alpha \le \beta</tex>, если:
* <tex>\alpha</tex> префикс <tex>\beta</tex>
* <tex>\gamma</tex> общий префикс <tex>\alpha</tex> и <tex>\beta</tex>, <tex>\alpha = \gamma c \delta</tex>, <tex>\beta = \gamma d \xi</tex> и <tex>c < d</tex>
}}

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Период и бордер, их связь

2012-04-24T09:07:30Z

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

==Связь периода и бордера==
{{Теорема
|statement= Если у строки длины <tex>n</tex> есть [[Основные определения, связанные со строками#Отношения между строками|бордер]] длины <tex>k</tex>, то у нее есть [[Основные определения, связанные со строками#Отношения между строками|период]] длины <tex>n - k</tex>.
|proof=
Пусть дана строка <tex>\alpha</tex>.
Напишем формально определения бордера длины <tex>|k|</tex> строки <tex>\alpha</tex>: 
<ul><tex>\forall i = 1 \ldots k</tex>, <tex>\alpha [i] = \alpha[i + (n - k)]</tex>. </ul>
Сделаем замену <tex>x = n - k</tex>: 
<ul><tex>\forall i = 1 \ldots n - x</tex>, <tex>\alpha [i] = \alpha[i + x]</tex>.</ul>
Получили определение периода длины <tex>x</tex>. Но <tex>x = n - k</tex>, значит у строки <tex>\alpha</tex> есть период длины <tex>|n - k|</tex>.
}}

==Свойства периода==
{{Теорема
|statement= Если у строки есть [[Основные определения, связанные со строками#Отношения между строками|период]] длины <tex>|k|</tex>, то у нее есть период длины <tex>|kx|</tex>, где <tex> x \in N</tex>.
|proof=
Пусть длина строки равна <tex>n</tex>, сама строка {{---}} <tex>\alpha</tex>. 
Доказательство будем вести по индукции по числу <tex>x</tex>. 
<ol>
<li>Для <tex> x = 1 </tex> утверждение очевидно.</li>
<li>Пусть верно для <tex>x = m</tex>.</li>
<li>Докажем, что верно для <tex>x = m + 1</tex>. 
Из определения периода имеем, что 
<tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>, 
а из предположения индукции, что 
<tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + mk]</tex> 
Значит получаем, что 
<tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>, 
следовательно 
для <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + (m + 1)k]</tex>. 
Значит у строки есть период длины <tex> |(m + 1)k|</tex>. </li>
</ol>
Утверждение доказано.
}}

{{Теорема
|statement= Если у строки есть периоды длины <tex>|p|</tex> и <tex>|q|</tex>, то НОД<tex>(p, q)</tex> также является периодом этой строки.
|proof=
Пусть строка равна <tex> \alpha </tex>. 
Доказательство будем вести по индукции по парам <tex>(p, q)</tex>, где <tex> p \geqslant q </tex>, а <tex>(p, q) + 1 = \begin{cases} (p, q + 1), & q < p;\\
(p + 1, 1), & q = p.\end{cases}</tex> 
<ol>
<li>Для <tex> (1, 1) </tex> утверждение очевидно.</li>
<li>Пусть верно для всех пар меньших <tex>(p, q)</tex>.</li>
<li>Докажем, что верно для <tex>(p, q)</tex>. 
Из определения периода: 
<tex>\forall i = 1 \ldots n - p</tex>, <tex>\alpha [i] = \alpha[i + p] = \alpha[i + q]</tex>. 
Значит <tex>\forall i = q \ldots n - p</tex>, <tex>\alpha [i + q] = \alpha[i + p]</tex> 
Сделаем замену <tex>j = i + q</tex> и получим, что 
<tex>\forall j = 1 \ldots n - (p - q)</tex>, <tex>\alpha [j] = \alpha[j + (p - q)]</tex> 
Получили новый период длины <tex>|p - q|</tex>. Из предположения известно, что НОД<tex>(p - q, q)</tex> {{---}} период строки, но НОД<tex>(p - q, q)</tex><tex>=</tex>НОД<tex>(p, q)</tex>.</li>
</ol>
Следовательно утверждение доказано.
}}

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Основные определения, связанные со строками

2012-04-22T13:20:47Z

178.178.27.75:

== Базовые определения ==

{{Определение
|definition =
'''Алфавитом''' <tex>\sum</tex> называется конечное непустое множество элементов, называемых символами.
}}

{{Определение
|definition =
'''Цепочкой''' (словом, строкой) конечной длины обозначим <tex>\sum^* : \sum^* = \bigcup\limits_{n \in \mathbb N} \sum^n</tex>.
}}

{{Определение
|definition =
'''Конкатенацией''' строк <tex>\alpha = \sum^k</tex> и <tex>\beta = \sum^m</tex> является строка <tex>\alpha\beta = \sum^{k+m}</tex>. Конкатенация является ассоциативной операцией.
}}

{{Определение
|definition =
'''Нейтральным элементом''' (пустой строкой) <tex>\varepsilon \in \sum^{0}</tex> называется элемент, для которого верно <tex>\alpha\varepsilon=\varepsilon\alpha=\alpha</tex>.
}}

<tex>\Sigma^*</tex> с операцией конкатенации и нейтральным элементом <tex>\varepsilon</tex> образуют моноид. Данный моноид совпадает со свободным над <tex>\Sigma</tex>.

== Отношения между строками ==

{{Определение
|definition =
<tex>\alpha</tex> называется '''префиксом''' <tex>\beta</tex>, если <tex>\beta = \alpha \gamma</tex>. Аналогично определяется '''суффикс''' строки.
}}

Пусть <tex>\beta = abracadabra</tex>, тогда
*если <tex>\alpha = abrac</tex>, то <tex>\alpha</tex> является префиксом <tex>\beta</tex>
*если <tex>\alpha = adabra</tex>, то суффиксом.

{{Определение
|definition =
<tex>\alpha</tex> называется '''бордером''' <tex>\beta</tex>, если <tex>\alpha</tex> одновременно является и суффиксом и префиксом.
}}

Пусть <tex>\beta = abracadabra</tex>, тогда <tex>\alpha = abra</tex> будет бордером <tex>\beta</tex>.

{{Определение
|definition =
<tex>p</tex> называется '''периодом''' <tex>\alpha</tex>, если <tex>\forall i = 1 \ldots n - p</tex> <tex>\alpha [i] = \alpha[i + p]</tex>.
}}

{{Определение
|definition =
Пусть строка <tex>x = \sum^n</tex> имеет период <tex>p</tex>, <tex>r = n / p</tex> и <tex>u = \sum^p</tex>. Тогда декомпозиция <tex>x = u^p </tex> называется '''нормальной формой''' строковой последовательности <tex>x</tex>.
}}

{{Определение
|definition =
Строка <tex>x</tex> называется примитивной, если <tex>r = 1</tex>.
}}

{{Определение
|definition =
Если <tex>r \ge 2</tex>, то строка <tex>x</tex> называется '''сильнопериодической''', если <tex>1 < r < 2</tex>, то '''слабопериодической'''. Если <tex>r</tex> целое и <tex>r \ge 2</tex>, то строка <tex>x</tex> называется '''строгопериодической''' (или просто '''периодической''').
}}

Строка <tex>aaabaabab</tex> - примитивная <tex>(p = n)</tex>.

Строка <tex>abaababaabaab = (abaababa)(abaab)</tex> - слабопериодическая с периодом <tex>p = 8</tex>, порядком <tex>r = 13/8</tex>.

Строка <tex>abaabaab = (aba)^2(ab)</tex> - сильнопериодическая с периодом <tex>p = 3</tex>, порядком <tex>r = 8/3</tex>.

{{Определение
|definition =
Строка <tex>\alpha</tex> является '''подстрокой''' <tex>\beta</tex>, если <tex>\beta = \gamma \alpha \delta</tex>.
}}

Строка <tex>\alpha = aca</tex> является подстрокой <tex>\beta = abracadabra</tex>.

{{Определение
|definition =
Строка <tex>\alpha \le \beta</tex>, если:
* <tex>\alpha</tex> префикс <tex>\beta</tex>
* <tex>\gamma</tex> общий префикс <tex>\alpha</tex> и <tex>\beta</tex>, <tex>\alpha = \gamma c \delta</tex>, <tex>\beta = \gamma d \xi</tex> и <tex>c < d</tex>
}}

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Обсуждение:Слово Туэ-Морса

2012-04-22T12:51:26Z

178.178.27.75:

# На паре определялась именно последовательность строк Туэ-Морса.
# Строки Туэ-Морса можно определить и через "морфизмы" (как в соседней статье), но в текущей версии дано другое определение (там символу соспоставляется строка, здесь же инвертируются символы и результат конкатенируется).
--[[Участник:Андрей Шулаев|Андрей Шулаев]] 20:44, 16 апреля 2012 (GST)

# Я не говорю о том, чтобы определять по-другому слова. Я про то, что phi — это морфизм. вида phi(a) = b, phi(b) = a; можно сказать, что не phi(S) -строка, а phi - это морфизм, задаваемый так-то и так-то.
# В одном месте алфавит стоит {0, 1}
# Насчет бесконечной последовательности: нужно просто сказать, что из определение слова туе морса можно получить последовательность туе-морса - как <tex>T_{\infty}</tex>