Редактирование: Автокорреляционный многочлен

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 16: Строка 16:
  
 
== Пример построения автокорреляционного многочлена ==
 
== Пример построения автокорреляционного многочлена ==
Пусть имеем алфавит <tex>\Sigma = \{0, 1\}</tex>, рассмотрим строку <tex>p=001100</tex>. Будем проверять факт совпадения суффикса и префикса строки <tex>p</tex>, используя следующую таблицу:
+
Пусть имеем алфавит <tex>\Sigma = \{0, 1\}</tex>, рассмотрим строку <tex>p=001100</tex>. Будем проверять факт совпадения суффикса и префикса строки <tex>p</tex>, используя следующую таблицу: '''Не очень понятная таблица. Ну, субъективно, не очень помогает понять. Может, переформатировать?'''
 
{| class="wikitable"
 
{| class="wikitable"
| style="font-weight:bold; background:#eaf2ff;" | 0
+
!0
| style="font-weight:bold; background:#eaf2ff;" | 0
+
!0
| style="font-weight:bold; background:#eaf2ff;" | 1
+
!1
| style="font-weight:bold; background:#eaf2ff;" | 1
+
!1
| style="font-weight:bold; background:#eaf2ff;" | 0
+
!0
| style="font-weight:bold; background:#eaf2ff;" | 0
+
!0
|
+
!
|
+
!
|
+
!
|
+
!
|
+
!
| rowspan="2" | c<sub>0</sub> = 1
+
!c<sub>i</sub>
 
|-  
 
|-  
| style="color: green; background:#eaf2ff;" | 0
+
|0
| style="color: green; background:#eaf2ff;" | 0
+
|0
| style="color: green; background:#eaf2ff;" | 1
+
|1
| style="color: green; background:#eaf2ff;" | 1
+
|1
| style="color: green; background:#eaf2ff;" | 0
+
|0
| style="color: green; background:#eaf2ff;" | 0
+
|0
 
|
 
|
 
|
 
|
 
|  
 
|  
 
|  
 
|  
|
 
|-
 
| colspan="12" |
 
|-
 
| style="font-weight:bold" | 0
 
| style="font-weight:bold; background:#eaf2ff;" | 0
 
| style="font-weight:bold; background:#eaf2ff;" | 1
 
| style="font-weight:bold; background:#eaf2ff;" | 1
 
| style="font-weight:bold; background:#eaf2ff;" | 0
 
| style="font-weight:bold; background:#eaf2ff;" | 0
 
 
|  
 
|  
|  
+
|1
|
 
|
 
|
 
| rowspan="2" | c<sub>1</sub> = 0
 
 
|-  
 
|-  
 
|  
 
|  
| style="color: green; background:#eaf2ff;" | 0
+
|0
| style="color: red; background:#eaf2ff;" | 0
+
|0
| style="color: green; background:#eaf2ff;" | 1
+
|1
| style="color: red; background:#eaf2ff;" | 1
+
|1
| style="color: green; background:#eaf2ff;" | 0
+
|0
 
|0
 
|0
 
|  
 
|  
Строка 69: Строка 55:
 
|  
 
|  
 
|  
 
|  
|-
+
|0
| colspan="12" |
+
|-  
|-
 
| style="font-weight:bold" | 0
 
| style="font-weight:bold" | 0
 
| style="font-weight:bold; background:#eaf2ff;" | 1
 
| style="font-weight:bold; background:#eaf2ff;" | 1
 
| style="font-weight:bold; background:#eaf2ff;" | 0
 
| style="font-weight:bold; background:#eaf2ff;" | 0
 
 
|  
 
|  
 
|  
 
|  
|
+
|0
|
+
|0
|
+
|1
| rowspan="2" | c<sub>2</sub> = 0
+
|1
|-
 
|
 
|
 
| style="color: red; background:#eaf2ff;" | 0
 
| style="color: red; background:#eaf2ff;" | 0
 
| style="color: red; background:#eaf2ff;" | 1
 
| style="color: red; background:#eaf2ff;" | 1
 
 
|0
 
|0
 
|0
 
|0
Строка 96: Строка 68:
 
|  
 
|  
 
|  
 
|  
|-
+
|0
| colspan="12" |
+
|-  
|-
 
| style="font-weight:bold" | 0
 
| style="font-weight:bold" | 0
 
| style="font-weight:bold" | 1
 
| style="font-weight:bold; background:#eaf2ff;" | 1
 
| style="font-weight:bold; background:#eaf2ff;" | 0
 
| style="font-weight:bold; background:#eaf2ff;" | 0
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|  
+
|0
|
+
|0
| rowspan="2" | c<sub>3</sub> = 0
+
|1
|- 
 
|
 
|
 
|
 
| style="color: red; background:#eaf2ff;" | 0
 
| style="color: green; background:#eaf2ff;" | 0
 
| style="color: red; background:#eaf2ff;" | 1
 
 
|1
 
|1
 
|0
 
|0
Строка 123: Строка 81:
 
|  
 
|  
 
|  
 
|  
|-
+
|0
| colspan="12" |
 
|-
 
| style="font-weight:bold" | 0
 
| style="font-weight:bold" | 0
 
| style="font-weight:bold" | 1
 
| style="font-weight:bold" | 1
 
| style="font-weight:bold; background:#eaf2ff;" | 0
 
| style="font-weight:bold; background:#eaf2ff;" | 0
 
|
 
|
 
|
 
|
 
|
 
| rowspan="2" | c<sub>4</sub> = 1
 
 
|-  
 
|-  
 
|  
 
|  
Строка 143: Строка 87:
 
|  
 
|  
 
|  
 
|  
| style="color: green; background:#eaf2ff;" | 0
+
|0
| style="color: green; background:#eaf2ff;" | 0
+
|0
 
|1
 
|1
 
|1
 
|1
Строка 150: Строка 94:
 
|0
 
|0
 
|  
 
|  
|-
+
|1
| colspan="12" |
 
|-
 
| style="font-weight:bold" | 0
 
| style="font-weight:bold" | 0
 
| style="font-weight:bold" | 1
 
| style="font-weight:bold" | 1
 
| style="font-weight:bold" | 0
 
| style="font-weight:bold; background:#eaf2ff;" | 0
 
|
 
|
 
|
 
|
 
|
 
| rowspan="2" | c<sub>5</sub> = 1
 
 
|-  
 
|-  
 
|  
 
|  
Строка 171: Строка 101:
 
|  
 
|  
 
|  
 
|  
| style="color: green; background:#eaf2ff;" | 0
+
|0
 
|0
 
|0
 
|1
 
|1
Строка 177: Строка 107:
 
|0
 
|0
 
|0
 
|0
 +
|1
 
|}
 
|}
 
В итоге автокорреляционный многочлен строки <tex>p=001100</tex> равен <tex>C(z) = 1 + z^4 + z^5</tex>.
 
В итоге автокорреляционный многочлен строки <tex>p=001100</tex> равен <tex>C(z) = 1 + z^4 + z^5</tex>.
Строка 187: Строка 118:
 
| definition = Пусть <tex>\Sigma</tex> {{---}} данный алфавит, <tex>p</tex> {{---}} данная непустая строка над алфавитом <tex>\Sigma</tex>. Найти производящую функцию множества слов, не содержащих <tex>p</tex> как подстроку.
 
| definition = Пусть <tex>\Sigma</tex> {{---}} данный алфавит, <tex>p</tex> {{---}} данная непустая строка над алфавитом <tex>\Sigma</tex>. Найти производящую функцию множества слов, не содержащих <tex>p</tex> как подстроку.
 
}}
 
}}
Пусть <tex>|\Sigma| = m</tex> {{---}} мощность алфавита <tex>\Sigma</tex>, <tex>S</tex> {{---}} множество слов, не содержащих <tex>p</tex> как подстроку, <tex>\alpha \in S</tex> {{---}} произвольное слово из <tex>S</tex>, <tex>T</tex> {{---}} множество слов, содержащих <tex>p</tex> как подстроку только в самом конце. Рассмотрим все слова вида <tex>\alpha \sigma_1, \alpha \sigma_2, \dots, \alpha \sigma_m</tex>, где <tex>\sigma_1, \sigma_2, \dots, \sigma_m</tex> {{---}} все символы алфавита <tex>\Sigma</tex>. Так как слово <tex>\alpha</tex> не содержало подстроку <tex>p</tex>, то после добавления символа <tex>\sigma_i</tex> новая строка либо так же не содержит <tex>p</tex> как подстроку, и, следовательно, <tex>\alpha\sigma_i \in S</tex>, либо содержит, но только в самом конце, и тогда <tex>\alpha\sigma_i \in T</tex>. Очевидно также, что от удаления последнего символа  у слова из <tex>T</tex> всегда получается слово из <tex>S</tex>, то есть, путём добавления ко всем <tex>\alpha \in S</tex> символа <tex>\sigma_i \in \Sigma, i=\overline{1,m},</tex> мы получим все непустые слова из <tex>T</tex> и <tex>S</tex>. В контексте комбинаторных объектов это выражается в равенстве <tex> \{\epsilon\} + S \times \Sigma = S + T</tex>, где <tex>\epsilon </tex> {{---}} комбинаторный объект веса 0, соответствующий пустой строке.
+
Пусть <tex>|\Sigma| = m</tex> {{---}} мощность алфавита <tex>\Sigma</tex>, <tex>S</tex> {{---}} множество слов, не содержащих <tex>p</tex> как подстроку, <tex>\alpha \in S</tex> {{---}} произвольное слово из <tex>S</tex>, <tex>T</tex> {{---}} множество слов, содержащих <tex>p</tex> как подстроку только в самом конце. Рассмотрим все слова вида <tex>\alpha \sigma_1, \alpha \sigma_2, \dots, \alpha \sigma_m</tex>, где <tex>\sigma_1, \sigma_2, \dots, \sigma_m</tex> {{---}} все символы алфавита <tex>\Sigma</tex>. Так как слово <tex>\alpha</tex> не содержало подстроку <tex>p</tex>, то после добавления символа <tex>\sigma_i</tex> новая строка либо так же не содержит <tex>p</tex> как подстроку, и, следовательно, <tex>\alpha\sigma_i \in S</tex>, либо содержит, но только в самом конце, и тогда <tex>\alpha\sigma_i \in T</tex>. Очевидно также, что от удаления последнего символа  у слова из <tex>T</tex> всегда получается слово из <tex>S</tex>, то есть, путём добавления ко всем <tex>\alpha \in S</tex> символа <tex>\sigma_i \in \Sigma, i=\overline{1,m},</tex> мы получим все непустые слова из <tex>T</tex> и <tex>S</tex>. В контексте комбинаторных объектов это выражается в равенстве <tex> \{\epsilon\} + S \times \Sigma = \Sigma + T</tex>, где <tex>\epsilon </tex> {{---}} комбинаторный объект веса 0, соответствующий пустой строке. '''Тут справа не S + T?'''
  
 
Рассмотрим теперь слова вида <tex>\alpha p</tex>. После добавления к слову <tex>\alpha</tex> строки <tex>p</tex> мы точно получим все строки из <tex>T</tex>, но, кроме них, могут также получиться строки, имеющие первое вхождение <tex>p</tex> не в самом конце, следовательно, нельзя утверждать, что <tex>\alpha p</tex> всегда принадлежит <tex>T</tex>. Несложно заметить, что <tex> \alpha p \notin T </tex> тогда и только тогда, когда <tex> \alpha p </tex> имеет 2 перекрывающихся вхождения строки <tex>p</tex>. Для того чтобы <tex> \alpha p </tex> имело 2 перекрывающихся вхождения строки <tex>p</tex> необходимо, чтобы <tex>p</tex> имела какой-нибудь суффикс, совпадающий с каким-нибудь префиксом, иначе говоря, чтобы <tex>p</tex> имело автокорреляционный многочлен <tex>C(z) \ne 1</tex>. В результате выходит, что при добавлении ко всем <tex>\alpha \in S</tex> строки <tex>p</tex> получим все строки из <tex>T</tex>, а также все строки, имеющие 2 перекрывающиеся вхождения строки <tex>p</tex>, иными словами, все строки вида <tex>\gamma p_0p_1 \dots p_i \dots p_{k-1} p_{k-i} p_{k-i+1} \dots p_{k-1}</tex> (или, что то же, <tex>\gamma p_0p_1 \dots p_{i-1} p_1 p_2 \dots p_{k-1}</tex>), где <tex>\gamma</tex> {{---}} некоторый префикс <tex>\alpha</tex>, <tex>i \in \overline{1, k-1}</tex>, {{---}} номер некоторого ненулевого коэффициента автокорреляционного многочлена <tex>C(z)</tex> строки <tex>p</tex>. Нетрудно заметить, что <tex>\gamma p_0p_1 \dots p_i \dots p_{k-1} p_{k-i} p_{k-i+1} \dots p_{k-1}</tex> можно представить как некую строку <tex>t \in T</tex> с приписанным в конец суффиксом строки <tex>p</tex> длины <tex>i</tex>. В контексте комбинаторных объектов суффикс строки <tex>p</tex> длины <tex>i</tex> является комбинаторным объектом веса <tex>i</tex>, а его производящей функцией является <tex>z^i</tex>, то есть, по сути, это слагаемое автокорреляционного многочлена <tex>C(z)</tex>. Тогда получаем следующее равенство: <tex>S \times \{p\} = T + \dots + T \times \{p_{k-i} p_{k-i+1} \dots p_{k-1}\} + \dots = T \times C</tex>, где <tex>C</tex> {{---}} комбинаторный класс, соответствующий автокорреляционному многочлену <tex>C(z)</tex>.
 
Рассмотрим теперь слова вида <tex>\alpha p</tex>. После добавления к слову <tex>\alpha</tex> строки <tex>p</tex> мы точно получим все строки из <tex>T</tex>, но, кроме них, могут также получиться строки, имеющие первое вхождение <tex>p</tex> не в самом конце, следовательно, нельзя утверждать, что <tex>\alpha p</tex> всегда принадлежит <tex>T</tex>. Несложно заметить, что <tex> \alpha p \notin T </tex> тогда и только тогда, когда <tex> \alpha p </tex> имеет 2 перекрывающихся вхождения строки <tex>p</tex>. Для того чтобы <tex> \alpha p </tex> имело 2 перекрывающихся вхождения строки <tex>p</tex> необходимо, чтобы <tex>p</tex> имела какой-нибудь суффикс, совпадающий с каким-нибудь префиксом, иначе говоря, чтобы <tex>p</tex> имело автокорреляционный многочлен <tex>C(z) \ne 1</tex>. В результате выходит, что при добавлении ко всем <tex>\alpha \in S</tex> строки <tex>p</tex> получим все строки из <tex>T</tex>, а также все строки, имеющие 2 перекрывающиеся вхождения строки <tex>p</tex>, иными словами, все строки вида <tex>\gamma p_0p_1 \dots p_i \dots p_{k-1} p_{k-i} p_{k-i+1} \dots p_{k-1}</tex> (или, что то же, <tex>\gamma p_0p_1 \dots p_{i-1} p_1 p_2 \dots p_{k-1}</tex>), где <tex>\gamma</tex> {{---}} некоторый префикс <tex>\alpha</tex>, <tex>i \in \overline{1, k-1}</tex>, {{---}} номер некоторого ненулевого коэффициента автокорреляционного многочлена <tex>C(z)</tex> строки <tex>p</tex>. Нетрудно заметить, что <tex>\gamma p_0p_1 \dots p_i \dots p_{k-1} p_{k-i} p_{k-i+1} \dots p_{k-1}</tex> можно представить как некую строку <tex>t \in T</tex> с приписанным в конец суффиксом строки <tex>p</tex> длины <tex>i</tex>. В контексте комбинаторных объектов суффикс строки <tex>p</tex> длины <tex>i</tex> является комбинаторным объектом веса <tex>i</tex>, а его производящей функцией является <tex>z^i</tex>, то есть, по сути, это слагаемое автокорреляционного многочлена <tex>C(z)</tex>. Тогда получаем следующее равенство: <tex>S \times \{p\} = T + \dots + T \times \{p_{k-i} p_{k-i+1} \dots p_{k-1}\} + \dots = T \times C</tex>, где <tex>C</tex> {{---}} комбинаторный класс, соответствующий автокорреляционному многочлену <tex>C(z)</tex>.
Строка 194: Строка 125:
 
:<tex>
 
:<tex>
 
\begin{cases}
 
\begin{cases}
   \{\epsilon\} + S \times \Sigma = S + T \\
+
   \{\epsilon\} + S \times \Sigma = \Sigma + T '''и тут тоже S'''\\
 
   S \times \{p\} = T \times C \\
 
   S \times \{p\} = T \times C \\
 
\end{cases}
 
\end{cases}

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: