3
правки
Изменения
Added article
{{Определение
|id=main
|definition=
'''Автокорреляционный многочлен''' (англ. ''autocorrelation polynomial'') для строки <tex>p</tex> длины <tex>k</tex> {{---}} это многочлен вида <tex>C(z)=\sum\limits_{i=0}^{k-1} c_i z^i</tex>, причем <tex>c_i = 1</tex>, если префикс строки <tex>p</tex> длины <tex>k-i</tex> совпадает с суффиксом строки <tex>p</tex> длины <tex>k-i</tex>, иначе <tex>c_i = 0</tex>:
<center>
<tex>c_i(x) =
\begin{cases}
1,\ \ p_0 \dots p_{k-i-1} = p_i \dots p_{k-1} \\
0,\ \ p_0 \dots p_{k-i-1} \ne p_i \dots p_{k-1} \\
\end{cases}
</tex>
</center>
}}
__TOC__
== Пример построения автокорреляционного многочлена ==
Пусть имеем алфавит <tex>\Sigma = \{0, 1\}</tex>, рассмотрим строку <tex>p=001100</tex>. Будем проверять факт совпадения суффикса и префикса строки <tex>p</tex>, используя следующую таблицу:
{| class="wikitable"
!0
!0
!1
!1
!0
!0
!
!
!
!
!
!c<sub>i</sub>
|-
|0
|0
|1
|1
|0
|0
|
|
|
|
|
|1
|-
|
|0
|0
|1
|1
|0
|0
|
|
|
|
|0
|-
|
|
|0
|0
|1
|1
|0
|0
|
|
|
|0
|-
|
|
|
|0
|0
|1
|1
|0
|0
|
|
|0
|-
|
|
|
|
|0
|0
|1
|1
|0
|0
|
|1
|-
|
|
|
|
|
|0
|0
|1
|1
|0
|0
|1
|}
В итоге автокорреляционный многочлен строки <tex>p=001100</tex> это <tex>C(z) = 1 + z^4 + z^5</tex>.
Несложно заметить, что <tex>c_0</tex> всегда равняется <tex>1</tex>, ибо префикс и суффикс длины <tex>n</tex> являются исходной строкой и, следовательно, всегда совпадают. <tex>c_{n-1}</tex> равняется <tex>1</tex> только в том случае, если первый и последний символы строки совпадают.
== Примеры решений задач с использованием автокорреляционного многочлена ==
{{Задача
| about =
| 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 = \Sigma + T</tex>, где <tex>\epsilon </tex> {{---}} комбинаторный объект веса 0, соответствующий пустой строке.
Рассмотрим теперь слова вида <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>.
В результате имеем 2 уравнения:
:<tex>
\begin{cases}
\{\epsilon\} + S \times \Sigma = \Sigma + T \\
S \times \{p\} = T \times C \\
\end{cases}
</tex>
В терминах производящих функций эти уравнения выглядят так:
:<tex>
\begin{cases}
1 + S(z) \cdot mz = S(z) + T(z) \\
S(z) \cdot z^k = T(z) \cdot C(z) \\
\end{cases}
</tex>
Решим полученную систему относительно <tex>S(z)</tex>:
:<tex>
\begin{cases}
T(z) = 1 + (mz-1)S(z) \\
S(z) \cdot z^k = (1 + (mz-1)S(z)) \cdot C(z) \\
\end{cases}
</tex>
:<tex>
S(z) \cdot (z^k - (mz-1)C(z)) = C(z) \\
</tex>
В итоге получаем искомую производящую функцию множества <tex>S</tex> слов, не содержащих данную непустую <tex>p</tex> как подстроку:
:<tex>
S(z) = \dfrac{C(z)}{z^k - (mz-1)C(z)} \\
</tex>, где <tex>C(z)</tex> {{---}} автокорреляционный многочлен <tex>p</tex>, <tex>m = |\Sigma|</tex>, <tex>k = |p|</tex>.
{{Задача
| about =
| definition = Пусть <tex>\Sigma</tex> {{---}} данный алфавит, <tex>p</tex> {{---}} данная непустая строка над алфавитом <tex>\Sigma</tex>. Найти производящую функцию множества слов, содержащих <tex>p</tex> как подстроку.
}}
Пусть <tex>m</tex> {{ --- }} мощность данного алфавита <tex>\Sigma</tex>. Ясно, что слов длины <tex>n</tex> над алфавитом мощности <tex>m</tex> будет <tex>m^n</tex> штук. Тогда производящей функцией множества всех слов над алфавитом мощности <tex>m</tex> будет <tex>\dfrac{1}{1-mz}</tex>. Вычтя из нее полученную ранее производящую функцию множества слов, не содержащих <tex>p</tex> как подстроку, получим искомую производящую функцию: <tex>\dfrac{1}{1-mz} - \dfrac{C(z)}{z^k - (mz-1)C(z)} = \dfrac{z^k - (mz-1)C(z) - (1-mz)C(z)}{(1-mz)(z^k - (mz-1)C(z))} = \dfrac{z^k}{(1-mz)(z^k + (1-mz)C(z))}</tex>, где <tex>C(z)</tex> {{---}} автокорреляционный многочлен <tex>p</tex>, <tex>k = |p|</tex>.
{{Задача
| about =
| definition = Пусть <tex>\Sigma</tex> {{---}} данный алфавит, <tex>p</tex> {{---}} данная непустая строка над алфавитом <tex>\Sigma</tex>. Найти производящую функцию множества слов, имеющих единственное вхождение <tex>p</tex> как подстроки в самом конце.
}}
Пусть <tex>T</tex> {{ --- }} множество слов, содержащих <tex>p</tex> как подстроку только в самом конце. Вернемся к системе уравнений, полученной при решении первой задачи, и воспользуемся найденным выражением <tex>S(z)</tex>:
:<tex>
\begin{cases}
T(z) = 1 + (mz-1)S(z) \\
S(z) = \dfrac{C(z)}{z^k - (mz-1)C(z)} \\
\end{cases}
</tex>
:<tex>
T(z) = 1 + (mz-1)\dfrac{C(z)}{z^k - (mz-1)C(z)} \\
</tex>
В результате получаем искомую производящую функцию <tex>T(z)</tex>:
:<tex>
T(z) = \dfrac{z^k}{z^k - (mz-1)C(z)} \\
</tex>, где <tex>C(z)</tex> {{---}} автокорреляционный многочлен <tex>p</tex>, <tex>m = |\Sigma|</tex>, <tex>k = |p|</tex>.
== См. также ==
* [[Производящая функция| Производящая функция]]
* [[Конструирование комбинаторных объектов и их подсчёт#Метод производящих функций| Метод производящих функций]]
== Источники информации ==
* Васильев А. Т. Лекции по дискретной математике // Связь ПФ с регулярными языками, автокорреляция и пентагональная теорема Эйлера, 2020. URL: https://youtu.be/EmhScUQwXT0?t=2034.
* [https://en.wikipedia.org/wiki/Autocorrelation_(words) Wikipedia {{---}} Autocorrelation (words)]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
|id=main
|definition=
'''Автокорреляционный многочлен''' (англ. ''autocorrelation polynomial'') для строки <tex>p</tex> длины <tex>k</tex> {{---}} это многочлен вида <tex>C(z)=\sum\limits_{i=0}^{k-1} c_i z^i</tex>, причем <tex>c_i = 1</tex>, если префикс строки <tex>p</tex> длины <tex>k-i</tex> совпадает с суффиксом строки <tex>p</tex> длины <tex>k-i</tex>, иначе <tex>c_i = 0</tex>:
<center>
<tex>c_i(x) =
\begin{cases}
1,\ \ p_0 \dots p_{k-i-1} = p_i \dots p_{k-1} \\
0,\ \ p_0 \dots p_{k-i-1} \ne p_i \dots p_{k-1} \\
\end{cases}
</tex>
</center>
}}
__TOC__
== Пример построения автокорреляционного многочлена ==
Пусть имеем алфавит <tex>\Sigma = \{0, 1\}</tex>, рассмотрим строку <tex>p=001100</tex>. Будем проверять факт совпадения суффикса и префикса строки <tex>p</tex>, используя следующую таблицу:
{| class="wikitable"
!0
!0
!1
!1
!0
!0
!
!
!
!
!
!c<sub>i</sub>
|-
|0
|0
|1
|1
|0
|0
|
|
|
|
|
|1
|-
|
|0
|0
|1
|1
|0
|0
|
|
|
|
|0
|-
|
|
|0
|0
|1
|1
|0
|0
|
|
|
|0
|-
|
|
|
|0
|0
|1
|1
|0
|0
|
|
|0
|-
|
|
|
|
|0
|0
|1
|1
|0
|0
|
|1
|-
|
|
|
|
|
|0
|0
|1
|1
|0
|0
|1
|}
В итоге автокорреляционный многочлен строки <tex>p=001100</tex> это <tex>C(z) = 1 + z^4 + z^5</tex>.
Несложно заметить, что <tex>c_0</tex> всегда равняется <tex>1</tex>, ибо префикс и суффикс длины <tex>n</tex> являются исходной строкой и, следовательно, всегда совпадают. <tex>c_{n-1}</tex> равняется <tex>1</tex> только в том случае, если первый и последний символы строки совпадают.
== Примеры решений задач с использованием автокорреляционного многочлена ==
{{Задача
| about =
| 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 = \Sigma + T</tex>, где <tex>\epsilon </tex> {{---}} комбинаторный объект веса 0, соответствующий пустой строке.
Рассмотрим теперь слова вида <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>.
В результате имеем 2 уравнения:
:<tex>
\begin{cases}
\{\epsilon\} + S \times \Sigma = \Sigma + T \\
S \times \{p\} = T \times C \\
\end{cases}
</tex>
В терминах производящих функций эти уравнения выглядят так:
:<tex>
\begin{cases}
1 + S(z) \cdot mz = S(z) + T(z) \\
S(z) \cdot z^k = T(z) \cdot C(z) \\
\end{cases}
</tex>
Решим полученную систему относительно <tex>S(z)</tex>:
:<tex>
\begin{cases}
T(z) = 1 + (mz-1)S(z) \\
S(z) \cdot z^k = (1 + (mz-1)S(z)) \cdot C(z) \\
\end{cases}
</tex>
:<tex>
S(z) \cdot (z^k - (mz-1)C(z)) = C(z) \\
</tex>
В итоге получаем искомую производящую функцию множества <tex>S</tex> слов, не содержащих данную непустую <tex>p</tex> как подстроку:
:<tex>
S(z) = \dfrac{C(z)}{z^k - (mz-1)C(z)} \\
</tex>, где <tex>C(z)</tex> {{---}} автокорреляционный многочлен <tex>p</tex>, <tex>m = |\Sigma|</tex>, <tex>k = |p|</tex>.
{{Задача
| about =
| definition = Пусть <tex>\Sigma</tex> {{---}} данный алфавит, <tex>p</tex> {{---}} данная непустая строка над алфавитом <tex>\Sigma</tex>. Найти производящую функцию множества слов, содержащих <tex>p</tex> как подстроку.
}}
Пусть <tex>m</tex> {{ --- }} мощность данного алфавита <tex>\Sigma</tex>. Ясно, что слов длины <tex>n</tex> над алфавитом мощности <tex>m</tex> будет <tex>m^n</tex> штук. Тогда производящей функцией множества всех слов над алфавитом мощности <tex>m</tex> будет <tex>\dfrac{1}{1-mz}</tex>. Вычтя из нее полученную ранее производящую функцию множества слов, не содержащих <tex>p</tex> как подстроку, получим искомую производящую функцию: <tex>\dfrac{1}{1-mz} - \dfrac{C(z)}{z^k - (mz-1)C(z)} = \dfrac{z^k - (mz-1)C(z) - (1-mz)C(z)}{(1-mz)(z^k - (mz-1)C(z))} = \dfrac{z^k}{(1-mz)(z^k + (1-mz)C(z))}</tex>, где <tex>C(z)</tex> {{---}} автокорреляционный многочлен <tex>p</tex>, <tex>k = |p|</tex>.
{{Задача
| about =
| definition = Пусть <tex>\Sigma</tex> {{---}} данный алфавит, <tex>p</tex> {{---}} данная непустая строка над алфавитом <tex>\Sigma</tex>. Найти производящую функцию множества слов, имеющих единственное вхождение <tex>p</tex> как подстроки в самом конце.
}}
Пусть <tex>T</tex> {{ --- }} множество слов, содержащих <tex>p</tex> как подстроку только в самом конце. Вернемся к системе уравнений, полученной при решении первой задачи, и воспользуемся найденным выражением <tex>S(z)</tex>:
:<tex>
\begin{cases}
T(z) = 1 + (mz-1)S(z) \\
S(z) = \dfrac{C(z)}{z^k - (mz-1)C(z)} \\
\end{cases}
</tex>
:<tex>
T(z) = 1 + (mz-1)\dfrac{C(z)}{z^k - (mz-1)C(z)} \\
</tex>
В результате получаем искомую производящую функцию <tex>T(z)</tex>:
:<tex>
T(z) = \dfrac{z^k}{z^k - (mz-1)C(z)} \\
</tex>, где <tex>C(z)</tex> {{---}} автокорреляционный многочлен <tex>p</tex>, <tex>m = |\Sigma|</tex>, <tex>k = |p|</tex>.
== См. также ==
* [[Производящая функция| Производящая функция]]
* [[Конструирование комбинаторных объектов и их подсчёт#Метод производящих функций| Метод производящих функций]]
== Источники информации ==
* Васильев А. Т. Лекции по дискретной математике // Связь ПФ с регулярными языками, автокорреляция и пентагональная теорема Эйлера, 2020. URL: https://youtu.be/EmhScUQwXT0?t=2034.
* [https://en.wikipedia.org/wiki/Autocorrelation_(words) Wikipedia {{---}} Autocorrelation (words)]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
