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

Алгоритм Ландау-Вишкина (k несовпадений)

2022-09-01T04:04:55Z

185.220.101.2:

{| 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 Майкл Наки].
|}

'''Постановка задачи:''' дано число <tex>k > 0</tex> текст <tex>y[1...n]</tex> и образец <tex>x[1...m]</tex>, <tex>m < n</tex>. Требуется найти все подстроки текста длины <tex>m</tex>, с не более чем <tex>k</tex> несовпадающими символами с образцом. Эту задачу решает алгоритм Ландау-Вишкина (k несовпадений) (''англ.Landau-Vishkin Algorithm'')

==Алгоритм==

===Идея===

[[Файл:algLandauVishkin1.png|thumb|250px|right| Красным отмечены несовпадения. В таблицу <tex>tm</tex> по номеру несовпадения записывается соответстующий индекс образца, то есть <tex>tm[i][1] = a</tex>, <tex>tm[i][2] = b</tex>, <tex>tm[i][3] = c</tex> и т. д.]]

При анализе используется двумерный массив несовпадений текста <tex>tm[0...n-m][1...k+1]</tex>, содержащий информацию о несовпадениях текста с образцом. По завершении анализа в его <tex>i</tex>-й строке содержатся позиции в <tex>x</tex> первых <tex>k+1</tex> несовпадений между строками <tex>x[1...m]</tex> и <tex>y[i+1...i+m]</tex>. Таким образом, если <tex>tm[i][v] = s</tex>, то <tex>y[i+s] \neq x[s]</tex>, и это <tex>v</tex>-е несовпадение между <tex>x[1...m]</tex> и <tex>y[i+1...i+m]</tex>, считая слева направо. Если число <tex>d</tex> несовпадений <tex>x[1...m]</tex> с подстрокой <tex>y[i+1...i+m]</tex> меньше <tex>k+1</tex>, то, начиная с <tex>d+1</tex>, элементы <tex>i</tex>-й строки равны значению по умолчанию <tex>m+1</tex>. (См. [[Алгоритм Ландау-Вишкина (k несовпадений)#Пример|пример]]).

Заметим, если <tex>tm[i][k+1] = m+1</tex>, то подстрока <tex>y[i+1...i+m]</tex> отличается от образца <tex>x</tex> не более, чем на <tex>k</tex> символов, и, таким образом, является решением задачи.

Затем образец сканируется параллельно с текстом слева направо по одному символу за раз. На итерации <tex>i</tex> с образцом сравнивается подстрока <tex>y[i+1...i+m]</tex>. Пусть <tex>j</tex> {{---}} это самая правая позиция в тексте, достигнутая за предыдущие итерации, то есть <tex>j</tex> является максимальным из чисел <tex>r+tm[r][k + 1]</tex>, где <tex>0 \leqslant r < i</tex>. Если <tex>i < j</tex>, в <tex>b</tex> присваивается результат работы <tex>\mathrm{merge}</tex>, которая находит количество несовпадений между <tex>x[1...j-i]</tex> и <tex>y[i+1...j]</tex>. Если <tex>b</tex> не превышает <tex>k</tex>, вызывается процедура <tex>\mathrm{extend}</tex>, которая сравнивает подстроки <tex>y[j + 1...i + m]</tex> и <tex>x[j - i + 1...m]</tex>, где изменяется таблица текстовых несовпадений. Переменная <tex>r</tex> будет рассмотрена ниже.

{| border="0"
|align="left" colspan="4"|

'''int[][]''' algorithmLandauViskin(y : '''string''', x : '''string''')
n = y.length
m = x.length
tm[0...n - m][1...k + 1] = m + 1 // инициализация 
r = 0
j = 0
'''for''' i = 0 to n - m
b = 0
'''if''' i < j
b = merge(i, r, j)
'''if''' b < k + 1
r = i
extend(i, j, b)
'''return''' tm

|}

===Процедура extend===

[[Файл:algLandauVishkin2.png|thumb|380px|right| Синие подстроки сравниваются в процедуре <tex>\mathrm{extend}</tex>. <tex>w < k + 1</tex>]]

Рассмотрим процедуру <tex>\mathrm{extend}</tex> подробнее. Она сравнивает подстроки <tex>y[j + 1...i + m]</tex> и <tex>x[j - i + 1...m]</tex>, в случае несовпадения <tex>b</tex> увеличивается, и таблица текстовых несовпадений обновляется. Это происходит пока либо не будет найдено <tex>k + 1</tex> несовпадений (учитывая несовпадения, которые были найдены раньше на <tex>i</tex>-ой итерации), либо не будет достигнуто <tex>y[i+m]</tex> с не больше чем <tex>k</tex> несовпадениями, то есть найдено вхождение образца, начинающееся с <tex>y[i+1]</tex>.

{| border="0"
|align="left" colspan="4"|

'''void''' extend(i : '''int''', j : '''int''', b : '''int''')
'''while''' (b < k + 1) '''and''' (j - i < m)
j++
'''if''' y[j] <tex>\neq</tex> x[j-1]
b++
tm[i][b] = j - i

|}

===Процедура merge===

[[Файл:algLandauVishkin3.png|thumb|400px|right| Синие подстроки сравниваются в процедуре <tex>\mathrm{merge}</tex>.]]

Рассмотрим процедуру <tex>\mathrm{merge}</tex> подробнее. Она находит количество несовпадений между <tex>x[1... j-i]</tex> и <tex>y[i+1...j]</tex> и устанавливает <tex>b</tex> равным найденному числу, при этом используется полученная ранее информация. Введем <tex>r</tex> {{---}} это строка таблицы несовпадений, в которой есть информация о несовпадениях, полученных при совмещении начала образца и <tex>y[r+1]</tex>. Текущий номер самой правой из проверенных на настоящий момент позиции текста равен <tex>r+tm[r][k+1]</tex>. Поэтому при обработки подстроки начинающейся с <tex>y[i+1]</tex>, можно учитывать информацию в <tex>r</tex>-ой строке <tex>tm</tex>, которая содержит информацию о сопоставлении образца с <tex>y[i]</tex>. Подходящими значениями из таблицы несовпадений являются, таким образом, <tex>tm[r][q ... k+1]</tex>, где <tex>q</tex> {{---}} это наименьшее из целых чисел, для которых <tex>r+tm[r][q] > i</tex>. Однако, следует учитывать тот факт, что эти несовпадения соответствуют началу образца, который был выровнен с <tex>y[r+1]</tex>, в то время как текущая позиция образца выровнена с <tex>y[i+1]</tex> {{---}} разница в <tex>i - r</tex> мест.

[[Файл:algLandauVishkin4.png|thumb|250px|right| В таблицу <tex>pm</tex> по номеру несовпадения записывается соответствующий индекс верхнего образца, то есть <tex>pm[i][1] = a</tex>, <tex>pm[i][2] = b</tex>, <tex>pm[i][3] = c</tex> и т д.]]

Также в алгоритме используется двумерный массив несовпадений образца <tex>pm[1...m-1][1...2k+1]</tex>, генерируемой на стадии предварительной обработки образца. В нем содержатся позиции несовпадения образца с самим собой при различных сдвигах, аналогично <tex>tm</tex>, то ест{{---}}ь в <tex>i</tex>-ой строке содержатся позиции внутри <tex>x</tex> первых <tex>2k+1</tex> несовпадений между подстроками <tex>x[1...m-i]</tex> и <tex>x[i+1...m]</tex>. Таким образом, если <tex>pm[i][v] = s</tex>, то <tex>x[i+s] \neq x[s]</tex>, и это <tex>v</tex>-е несовпадение между <tex>x[1...m-i]</tex> и <tex>x[i+1...m]</tex> слева направо. Если число <tex>d</tex> несовпадений между этими строками меньше <tex>2k+1</tex>, то, начиная с <tex>d+1</tex>, элементы <tex>i</tex>-й строки равны <tex>m+1</tex>, значению по умолчанию. Построение <tex>tm</tex> будет подробнее рассмотрено позднее.

Таким образом, для <tex>\mathrm{merge}</tex> интерес представляет строка <tex>i - r</tex> таблицы несовпадений образца, причем используются значения <tex>pm[i-r][1...t]</tex>, где <tex>t</tex> {{---}} самое правое несовпадение в <tex>pm[i-r][1...2k+1]</tex>, такое, что <tex>pm[i-r][t] < j-i+1</tex>, так как требуются только несовпадения в подстроке <tex>x[1...j-i]</tex>.

Чтобы использовать упомянутую информацию в процедуре <tex>\mathrm{merge}</tex>, рассмотрим в тексте позицию <tex>p</tex>, находящуюся в диапазоне, <tex>i+1 . Рассмотрим следующие условия для позиции <tex>p</tex>:

'''Условие A''': когда символы <tex>x[1]</tex> и <tex>y[r+1]</tex> совмещены, позиция <tex>p</tex> в тексте соответствует предварительно выявленному несовпадению между образцом и текстом, то есть <tex>y[p] \neq x[p-r]</tex>, и это несовпадение номер <tex>v</tex>, где <tex>q < v < k+1</tex>, то есть <tex>p - r = tm[r][v]</tex>.

[[Файл:algLandauVishkin5.png|380px]]

'''Условие B''': для двух копий образца, со сдвигом относительно друг друга <tex>i - r</tex>, совмещенных с текстом так, что их начальные символы лежат, соответственно, над <tex>y[r+1]</tex> и <tex>y[i+1]</tex>, позиция <tex>p</tex> соответствует несовпадению между двумя образцам, то есть <tex>x[p-r] \neq x[p-i]</tex>. Это <tex>u</tex>-е несовпадение при этом сдвиге, где <tex>1 , то есть <tex>p-i = pm[i-r][u]</tex>.

[[Файл:algLandauVishkin6.png|450px]]

Вспомним, что нас интересует, совпадает ли символ текста в позиции <tex>p</tex> с соответствующими символом образца, когда <tex>x[1]</tex> совмещен с <tex>y[i+1]</tex>, то есть верно ли, что <tex>y[p] = x[p-i]</tex>. Рассмотрим этот вопрос при разных комбинациях указанных выше условий.

'''Случай 1: !A and !B:''' То есть, <tex>y[p] = x[p-r]</tex> и <tex>x[p-r] = x[p-i]</tex>, откуда <tex>y[p] = x[p-i]</tex>. Нет необходимости сравнивать символ текста с символом образца, так как ясно, что в этой позиции они совпадают.

'''Случай 2: (A and !B) or (!A and B):''' В любом случае <tex>y[p] \neq x[p-i]</tex> (если лишь ''условие A'' истинно, то <tex>y[p] \neq x[p-r]</tex> и <tex>x[p-r] = x[p-i]</tex>, откуда <tex>y[p] \neq x[p-i]</tex>, с другой стороны, если выполнено только ''условие B'', то <tex>y[p] = x[p-r]</tex> и <tex>x[p-r] \neq x[p-i]</tex>, и опять, <tex>y[p] \neq x[p-i]</tex>). Как и в предыдущем случае, нет необходимости сравнивать символ текста с символом образца, так как известно, что они не совпадают.

'''Случай 3: A and B:''' В этом случае мы ничего не можем сказать о том, совпадают ли символы <tex>y[p]</tex> и <tex>x[p-i]</tex>, поэтому их надо сравнить.

Возвращаемся к процедуре <tex>\mathrm{merge}</tex>. В ''случае 2'', или если в ''случае 3'' выявлено несовпадение символов, необходимо увеличить количество несовпадений символов <tex>b</tex> на единицу и обновить <tex>tm[i][b]</tex>. Соответствующими значениями таблицы для <tex>\mathrm{merge}</tex> являются <tex>tm[i-r][1...t]</tex> и <tex>tm[r][q...k+1]</tex>. Переменные <tex>u</tex> и <tex>v</tex> в начале устанавливаются равными индексам первых элементов этих двух массивов, соответственно, и последовательно увеличиваются.

Условия окончания работы процедуры следующие:

* Если <tex>b = k+1</tex>, то для случая, когда образец расположен относительно текста так, что <tex>x[1]</tex> совмещен с <tex>y[i+1]</tex>, обнаружено <tex>k+1</tex> несовпадение, поэтому из процедуры можно выйти.

* Bспомним, что самая правая из интересующих нас позиций в <tex>\mathrm{merge}</tex>, а именно, <tex>j</tex>, равна <tex>r+tm[r][k+1]</tex>, если <tex>v = k+2</tex>, поэтому <tex>tm[r][k+1]</tex> будет уже использовано для предыдущего значения <tex>v</tex>, а именно, <tex>v = k+1</tex>, и поэтому позиция <tex>j</tex> должна быть пропущена. Следовательно, в этом случае также можно выйти из процедуры.

* Процедуру можно прервать, если <tex>i+pm[i-r][u] > j</tex> и <tex>tm[r][v] = m+1</tex>. Если выполняется вторая часть этого условия, то <tex>r+tm[r][v]</tex> равняется <tex>j</tex>, и соответствует суммам для последующих значений <tex>v</tex> вплоть до <tex>k+1</tex>. В этом случае процедура может быть прервана, если выполняется также первая часть приведенного условия, так как она указывает, что позиция текста <tex>j</tex> фактически пропущена.

Остается показать, что число позиций несовпадений в таблице несовпадений образца достаточно для того, чтобы <tex>\mathrm{merge}</tex> нашла все, или, если их больше <tex>k+1</tex>, первые <tex>k+1</tex> несовпадений для <tex>y[i+1...j]</tex>. Это можно показать следующим образом. ''Условие A'' выполняется не больше чем для <tex>k+1</tex> позиции текста в диапазоне <tex>y[i+1...j]</tex>. ''Условие B'' выполняется для некоторого неизвестного числа позиций в этом же интервале. Строка <tex>i-r</tex> в таблице несовпадений образца, <tex>tm[i-r][1...2k+1]</tex>, содержит не больше чем <tex>2k+1</tex> позиций несовпадений между двумя копиями образца, с соответствующим сдвигом <tex>i-r</tex>. Если <tex>pm[i-r][2k+1] > j - i</tex>, то таблица содержит все позиции несовпадения образца самим с собой, у которых ''условие B'' выполняется для позиций текста в интервале <tex>y[i+1...j]</tex>. С другой стороны, если <tex>pm[i-r][2k+1] < j-i</tex>, то таблица может дать <tex>2k+1</tex> позиций текста в диапазоне <tex>y[i+1...j-1]</tex>, для которых выполняется ''условие B''. Поскольку <tex>j = r+tm[r][k+1]</tex>, в диапазоне <tex>y[i+1...j-1]</tex> имеется до <tex>k</tex> позиций текста, для которых выполняется ''условие A''. Таким образом, в худшем случае может быть <tex>k</tex> позиций, для которых имеет место ''случай 3'', и которые требуется сравнить напрямую. Остается по крайней мере <tex>k+1</tex> позиций, удовлетворяющих ''условию B'', но не ''условию A'' (''случай 2''), что является достаточным, чтобы заключить, что для данного положения образца относительно текста имеется не меньше <tex>k+1</tex> несовпадений между текстом и образцом.

{| border="0"
|align="left" colspan="4"|

'''int''' merge(i : '''int''', r : '''int''', j : '''int''')
u = 1
v = q
'''while''' (b < k + 1) '''and''' (v < k + 2) '''and''' (i + pm[i - r][u] < j '''or''' tm[r][v] <tex>\neq</tex> m + 1)
'''if''' i + pm[i - r][u] > r + tm[r][v] // Случай 2, условие A 
b++
tm[i][b] = tm[r][v] - (i - r)
v++
'''else''' '''if''' i + pm[i - r][u] < r + tm[r][v] // Случай 2, условие B 
b++
tm[i][b] = pm[i - r][u]
u++
'''else''' '''if''' i + pm[i - r][u] = r + tm[r][v] // Случай 3 
'''if''' x[pm[i - r][u]] <tex>\neq</tex> y[i + pm[i - r][u]]
b++
tm[i][b] = pm[i - r][u]
u++
v++
'''return''' b

|}

===Построение pm===

Теперь осталось только обратиться к вычислению таблицы несовпадений образца на стадии предварительных вычислений. Не теряя общности, можно предположить, что <tex>m</tex> является некоторой степенью <tex>2</tex>. В алгоритме предварительной обработки используется разбиение множества <tex>{1, 2, ... , m-1}</tex> из <tex>m-1</tex> строк <tex>pm</tex> на следующие <tex>\log m</tex> подмножеств:

<tex>\{1\}, \{2, 3\}, \{4, 5, 6, 7\}, ... , \{m/2, ... , m-1\}</tex>

Алгоритм состоит из <tex>\log m</tex> этапов. На этапе <tex>s</tex>, где <tex>1 \leqslant s < \log m</tex>, вычисляются строки <tex>pm</tex> в множестве <tex>s</tex>, где множество <tex>s</tex> {{---}} это <tex>\{2^{s-1}, ... , 2^{s}-1\}</tex>.

Метод, используемый для вычисления этой таблицы, основан на методе, используемом на стадии анализа текста. Рассмотрим алгоритм для этапа <tex>s</tex>. На стадии <tex>s</tex> входами для алгоритма анализа образца являются подстроки образца <tex>x[1...m-2^{s-1}]</tex> и <tex>x[2^{s-1}+1...m]</tex>, которые трактуются здесь, соответственно, как образец и текст, и массив <tex>pm[1...2^{s-1}-1][1...\min\{2^{\log(m)-s}4k+1, m-2^{s-1}\}]</tex>, содержащий выходы предыдущих <tex>s - 1</tex> стадий. Выходы стадии <tex>s</tex> вводятся в <tex>pm</tex>. За исключением стадии <tex>\log m</tex>, на которой находят до <tex>2k+1</tex> несовпадений, на стадии <tex>s</tex> для каждой строки <tex>pm</tex> требуется найти до <tex>\min\{2^{\log(m)-s}2k+1, m-2^{s}\}</tex> несовпадений, а не до <tex>k+1</tex>, как в алгоритме анализа текста.

{| border="0"
|align="left" colspan="4"|

'''void''' precalcPm()
pm[<tex>2^{s-1}</tex>...<tex>2^{s} - 1</tex>][1...min{<tex>2^{\log (m-1)}2k - 1</tex>, <tex>m - 2^{s}</tex>}] = m + 1
r = <tex>2^{s-1}</tex>
j = <tex>2^{s-1}</tex>
'''for''' i = <tex>2^{s-1}</tex> to <tex>2^{s} - 1</tex>
b = 0
'''if''' i < j
b = merge(i, r, j)
'''if''' b < min{<tex>2^{\log(m-1)}2k - 1, m - 2^{s} </tex>}
r = i
extend(i, j, b)

|}

===Оценка сложности===

Теперь исследуем затраты времени на анализ текста. Если исключить вызовы процедур <tex>\mathrm{merge}</tex> и <tex>\mathrm{extend}</tex>, каждая из <tex>n-m+1</tex> итераций цикла анализа текста выполняется за фиксированное время, что дает в общей сложности время <tex>O(n)</tex>. Общее число операций, выполняемых процедурой <tex>\mathrm{extend}</tex> во время вызовов равно <tex>O(n)</tex>, так как она проверяет каждый символ текста не больше одного раза. Процедура <tex>\mathrm{merge}</tex> при каждом вызове обрабатывает массив <tex>pm[i-r][1...2k+1]</tex> и <tex>tm[r][1...k+1]</tex>, которые в сумме имеют <tex>3k+2</tex> элементов. Время работы <tex>\mathrm{merge}</tex> можно рассчитать, соотнеся операции с фиксированным временем с каждым из этих входов, что дает время счета для каждого вызова, равное <tex>O(k)</tex>. Таким образом, можно видеть, что общее время анализа текста составляет <tex>O(nk)</tex>.

Рассмотрим построение <tex>pm</tex>. Используя аргументы, аналогичные применявшимся при проверке корректности процедуры <tex>\mathrm{merge}</tex>, можно показать, что для нахождения требуемого количества несовпадений на стадии <tex>s</tex> требуется <tex>\min\{2^{\log(m)-s}4k+1, m-2^{s}\}</tex> позиций, для которых выполняется ''условие B'', и в особом случае, а именно, на стадии <tex>\log m</tex>, требуется <tex>4k + 1</tex> таких позиций.

На каждой стадии <tex>s</tex> из <tex>\log m</tex> стадий анализа образца цикл <tex>\mathrm{for}</tex> производит <tex>2^{s-1}</tex> итераций <tex>(2^{s-1} \leqslant i \leqslant 2^{s}-1)</tex>. Если не считать время работы процедур <tex>\mathrm{merge}</tex> и <tex>\mathrm{extend}</tex>, каждая итерация требует фиксированного времени. Для всех итераций на шаге <tex>s</tex> процедуре <tex>\mathrm{extend}</tex> требуется время <tex>O(m)</tex>. Ранее было показано, что время работы <tex>\mathrm{merge}</tex> пропорционально числу искомых несовпадений. Таким образом, каждый вызов <tex>\mathrm{merge}</tex> занимает время <tex>O(\min\{2^{\log(m)-s}4k+1, m-2^{s}\})</tex>, что равно <tex>O(2k2^{\log (m)-s})</tex>. Таким образом, общее время для стадии <tex>s</tex> равно <tex>O(m+2^{s-1}(2k2^{\log (m) -s}))</tex> = <tex>O(km)</tex>. Проведя суммирование по всем стадиям, получаем общее время счета <tex>O</tex> <tex>\displaystyle \left(\sum_{i=1}^{\log m} km\right) = O(km \log m)</tex>. Таким образом, общие затраты времени, включающие предварительную обработку образца и анализ текста, равны <tex>O(k(n + m \log m))</tex>.

==Пример==
Пусть <tex>x = "tram"</tex>, <tex>y = "thetrippedtrap"</tex>, <tex>k = 2</tex>.
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse; text-align: center;"
|-
| tm || '''1''' || '''2''' || '''3''' || x[1 <tex>\ldots</tex> m] || y[i+1 <tex>\ldots</tex> i+m]
|-
| '''0''' || 2 || 3 || 4 || '''t'''ram || '''t'''het
|-
| '''1''' || 1 || 2 || 3 || tram || hetr
|-
| '''2''' || 1 || 2 || 3 || tram || etri
|-
| '''3''' || 3 || 4 || style="background:#b1b1ff"| 5 || '''tr'''am || '''tr'''ip
|-
| '''4''' || 1 || 2 || 3 || tram || ripp
|-
| '''5''' || 1 || 2 || 3 || tram || ippe
|-
| '''6''' || 1 || 2 || 3 || tram || pped
|-
| '''7''' || 1 || 2 || 3 || tram || pedt
|-
| '''8''' || 1 || 2 || 3 || tram || edtr
|-
| '''9''' || 1 || 2 || 3 || tram || dtra
|-
| '''10''' || 4 || style="background:#b1b1ff"| 5 || style="background:#b1b1ff"| 5 || '''tra'''m || '''tra'''p
|}
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse; text-align: center;"
|-
| pm || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || x[1 <tex>\ldots</tex> m-i] || x[i+1 <tex>\ldots</tex> m]
|-
| '''1''' || 1 || 2 || 3 || 5 || 5 || tra || ram
|-
| '''2''' || 1 || 2 || 5 || 5 || 5 || tr || am
|-
| '''3''' || 1 || 5 || 5 || 5 || 5 || t || m
|}

==См. также==
* [[Алгоритм Бойера-Мура]]
* [[Алгоритм Кнута-Морриса-Пратта]]

==Источники информации==
* [http://algolist.manual.ru/search/fsearch/k_nesovp.php Алгоритм Ландау-Вишкина {{---}} k несовпадений]

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

Автоматы в современном мире

2022-09-01T04:04:48Z

185.220.101.2:

Теоретический минимум по математическому анализу за 1 семестр

2022-09-01T04:04:29Z

185.220.101.2:

{| 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 Майкл Наки].
|}

1. Аксиома непрерывности в множестве вещественных чисел, точные грани числовых
множеств.

Пусть <tex>A </tex> и <tex>B </tex> — 2 произвольных подмножества из пополненного множества рациональных чисел, и <tex> A \le B </tex>, то в пополненном множестве <tex> \exists d: A \le d \le B </tex>

2. Принцип вложенных отрезков.

{{Определение
|definition=
Пусть дана система отрезков: <tex> a_n \le b_n, \Delta_n = [a_n, b_n] </tex>

<tex> \forall n \in \mathbb N: \Delta_{n+1} \subset \Delta_n </tex>

Тогда эта система отрезков называется '''вложенной'''.
}}

3. Определение предела последовательности.

{{Определение
|definition=
Число <tex> a \in \mathbb R </tex> называется '''пределом последовательности''' <tex> a_n </tex>, если:

<tex> \forall \varepsilon > 0, \exists n_0 \in \mathbb N: \forall n > n_0: |a_n - a| < \varepsilon </tex>

Записывают: <tex> a = \lim\limits_{n \rightarrow \infty} a_n </tex>
}}

4. Теорема Вейерштрасса о монотонных последовательностях.

{{Теорема
|id = thWeier
|author=Вейерштрасс
|statement=
Пусть <tex> a_n \uparrow </tex> и <tex> a_n </tex> ограничена сверху. Тогда она сходится. (Аналогично, если <tex> a_n \downarrow </tex>, <tex> a_n </tex> {{---}} ограничена снизу).}}

5. Число е.

<tex> \exists \lim\limits_{n \rightarrow \infty} (1 + \frac 1n)^n </tex>. Его обозначают числом <tex> e </tex>.

6. Теорема Больцано-Вейерштрасса.

{{Теорема
|id = thBolzano
|author=Больцано
|statement=Из любой ограниченной последовательности можно выделить сходящуюся подпоследовательность}}

7. Теорема Коши о сходящихся в себе последовательностях.

{{Теорема
|id = thCauchy
|author=Коши
|statement=Если числовая последовательность сходится в себе, то она сходится.}}

8. Определение МП, открытые и замкнутые множества в МП.

Если на <tex>X</tex> определена метрика, то пара <tex>(X, \rho)</tex> называется ''метрическим пространством'', аббревиатура {{---}} ''МП''.

{{Определение
|definition=
Пусть <tex> (X, \rho) </tex> {{---}} метрическое пространство, пусть <tex>\ \ r \in \mathbb{R},\ r > 0,\ a \in X </tex>, тогда открытый шар радиуса
<tex>\ r\ </tex> в точке <tex>\ a\ </tex> {{---}} это множество <tex> V_r(a) = \{x \in X| \rho(x, a) < r \} </tex>
}}

{{Определение
|definition=
Множество <tex> G \subset X </tex> называется открытым в метрическом пространстве, если его можно записать как некоторое объединение открытых шаров (в общем случае объединение может состоять из несчетного числа шаров).
: <tex> \tau </tex> — класс открытых множеств.
: <tex> \tau = \{ G </tex> {{---}} открытые в МП <tex>(X, \rho) \}</tex>
}}

{{Определение
|definition=
Множество <tex>F</tex> называется замкнутым в МП<tex>(X, \rho)</tex>, если <tex> \overline F = X \backslash F </tex> {{---}} открыто.
}}

9. Компакты в МП, теорема Хаусдорфа.

{{Определение
|definition=
Множество ''ограниченное'', если его можно поместить в шар.
}}

{{Определение
|definition=
Пусть <tex> (X, \rho) </tex> {{---}} МП. <tex> K \in X </tex> является '''компактом''' в X, если из любой последовательности точек принадлежащих K можно выделить сходящуюся подпоследовательность <tex> x_n: \lim x_n \in K </tex>.
}}

{{Утверждение
|statement = Легко видеть что если K {{---}} компакт, то оно ограниченное, замкнутое. Обратное в общем случае не верно.
}}

{{Теорема
|author=Хаусдорф
|statement=
Пусть <tex>X</tex>{{---}} полное метрическое пространство, <tex>K \subset X</tex>, <tex>K</tex> {{---}} замкнуто.
Тогда <tex>K</tex> {{---}} компакт <tex>\iff</tex> <tex>K</tex> {{---}} вполне ограниченно.
}}

10. Предел отображения в МП.

{{Определение
|definition=
<tex> x_n \rightarrow x </tex> в МП <tex>(X, \rho)</tex>, если:
# <tex>\ \lim\limits_{n \rightarrow \infty} \rho(x_n, x) = 0\ </tex> , или
# <tex>\forall \varepsilon > 0, \exists N \in \mathbb{N}, \forall n > N \Rightarrow \rho(x_n, x) < \varepsilon </tex>
: или
: <tex>\forall \varepsilon > 0, \exists N \in \mathbb{N}, \forall n > N: x_n \in V_\varepsilon(x)</tex>, где <tex> V_\varepsilon(x) = \{ y: \rho(y, x) < \varepsilon \} </tex>, то есть открытый шар радиуса <tex>\ \varepsilon</tex> с центром в точке <tex>\ x</tex>
}}

{{Определение
|definition =
Пусть даны два метрических пространства <tex> (X,\rho) </tex> и <tex> (Y, \tilde \rho) </tex>, <tex> A \subset X</tex> и <tex>\ a </tex> {{---}} предельная точка <tex>A</tex>. Пусть <tex> f: A \rightarrow Y </tex>.
* Тогда <tex> b = \lim\limits_{x \rightarrow a} f(x), b \in Y</tex> , если <tex>\forall \varepsilon > 0 \, \exists \delta > 0: 0 < \rho(x, a) < \delta \Rightarrow \tilde \rho(f(x), b) < \varepsilon </tex>.
}}

11. Теорема Кантора о равномерной непрерывности.

Равномерная непрерывность - <tex> \forall \varepsilon >0 \exists \delta > 0 \forall x_1, x_2 \in X: | x_1 - x_2| < \delta : |f(x_1) - f(x_2)| < \varepsilon </tex>

{{Теорема
|author=
Кантор
|statement=
Пусть даны МП <tex> (X, \rho), (Y, \rho)</tex>, <tex> K \subset X</tex> - компакт, <tex> f: K \rightarrow Y </tex> - непрерывное отображение. Тогда <tex> f </tex> также и равномерно непрерывное на <tex> K </tex>.
}}

12. Теорема Вейерштрасса об экстремумах.

{{Теорема
|author=
Вейерштрасс
|statement=
Пусть <tex> f: K \rightarrow \mathbb R </tex> {{---}} непрерывная функция на компакте <tex> K </tex>.
Тогда существуют такие <tex> x_1, x_2 </tex>, что <tex> f(x_1) = \inf\limits_{K}f, f(x_2) = \sup\limits_{K}f </tex>.
|proof=
}}

13. Теорема Коши о промежуточных значениях.

{{Теорема
|author=
Коши
|about=
о промежуточных значениях функции
|statement=
Пусть <tex> f: \mathbb R \rightarrow \mathbb R </tex> {{---}} непрерывная функция на <tex> [a; b], f(a) = A, f(b) = B</tex>, для определенности считаем, что <tex> A .
Тогда <tex> \forall D: A < D < B\ \exists d \in (a; b): f(d) = D </tex>.
|proof=
}}

14. Определение дифференциала и производной, критерий дифференцируемости.

{{Определение
|definition=
<tex>f</tex> {{---}} '''дифференцируема''' в точке <tex>x</tex>, если <tex>\Delta y = A(x) \Delta x + o(\Delta x)</tex>, где
<tex>o(\Delta x)</tex> {{---}} такая величина, что <tex>\frac{o(\Delta x)}{\Delta x} \to 0</tex> при <tex>\Delta x \to 0</tex>.
Тогда <tex>A(x)\Delta x</tex> называют '''дифференциалом''' в точке <tex>x</tex>.
Также обозначают <tex>A(x) \Delta x = df(x, \Delta x) = dy</tex>.
}}

{{Утверждение
|statement=
Функция дифференцируема <tex>\iff \, \exists \lim\limits_{\Delta x \to 0} \frac{\Delta y}{\Delta x} = A(x)</tex>.
|proof=
Если функция дифференцируема, то <tex>\frac{\Delta y}{\Delta x} = A(x) + \frac{o(\Delta x)}{\Delta x}</tex>,
где <tex>\frac{o(\Delta x)}{\Delta x}</tex> {{---}} бесконечно малая.
}}

{{Определение
|definition=
<tex>f'(x) = \lim\limits_{\Delta x \to 0} \frac{\Delta y}{\Delta x}</tex>
}}

15. Производная сложной функции.

{{Теорема
|about=
Дифференцирование сложной функции
|statement=
Пусть <tex>y = f(x)</tex> дифференцируема в точке <tex>x_0</tex>, <tex>y_0 = f(x_0)</tex>. Пусть <tex>z = g(y)</tex> дифференцируема в <tex>y_0</tex>. Тогда в некоторой окрестности <tex>x_0</tex> корректно определена сложная функция <tex>z = g(f(x))</tex> и её производная равна <tex>z' = g'(y_0)f'(x_0)</tex>.
}}

16. Теорема Ферма о значении производной в экстремальной точке.

{{Теорема
|author=
Ферма
|statement=
Пусть <tex> f(x) </tex> существует и дифференцируема в <tex> O(x_0) </tex>, и <tex> x_0 </tex> {{---}} точка локального экстремума. Тогда <tex> f'(x_0) = 0.</tex>
}}

17. Теорема Ролля о нулях производной.

{{Теорема
|author=
Ролль
|statement=
Пусть <tex> f(x) </tex> непрерывна на <tex> [a; b] </tex>, дифференцируема на <tex>(a, b)</tex> и <tex>f(a) = f(b)</tex>. Тогда существует точка <tex> c \in (a; b)</tex>, такая, что <tex> f'(c) = 0</tex>.
}}

18. Формула конечных приращений Лагранжа.

{{Теорема
|author=
Лагранж
|statement=
Пусть <tex> f </tex> непрерывна на <tex> [a; b] </tex> и дифференцируема на <tex> (a; b) </tex>. Тогда <tex> \exists c \in (a; b): </tex> <tex dpi = '150'> \frac{f(b) - f(a)}{b - a} </tex> <tex> = f'(c) </tex>
}}

19. Правило Лопиталя раскрытия неопределенностей.

{{Теорема
|author=
правило Лопиталя
|statement=
Если при <tex>x \rightarrow a</tex> <tex dpi = '150'>\frac{f(x)}{g(x)} = \frac{0}{0} </tex>, то <tex dpi = '150'> \lim\limits_{x \rightarrow a} \frac{f(x)}{g(x)} = \lim\limits_{x \rightarrow a} \frac{f'(x)}{g'(x)} </tex>
}}

20. Формула Тейлора с остатком Лагранжа.

{{Теорема
|about=
Лагранж
|statement=
Пусть <tex>f</tex> <tex>n + 1</tex> раз дифференцируема в окрестности точки <tex>x_0</tex>.
Тогда <tex dpi=140>\forall x \in V(x_0)\ \exists c_x \in (x_0; x) \cup (x; x_0) \ : f(x)</tex> <tex dpi=140>= \sum\limits_{k = 0}^{n} \frac{f^{(k)}(x_0)}{k!}(x - x_0)^k +
\frac{f^{(n + 1)}(c_x)}{(n + 1)!} (x - x_0)^{n + 1}
</tex>

<tex>c_x = x_0 + \Theta(x - x_0), \quad \Theta \in (0; 1)</tex>

<tex>f(x)</tex> {{---}} формула Тейлора с остатком по Лагранжу.
}}

21. Интерполяционная формула Лагранжа и ее остаток.

{{Определение
|definition=
Фундаментальные полиномы <tex>\Phi_j(x)</tex> степени не выше <tex>n</tex> — полиномы, отвечающие заданной
системе узлов <tex>x_0 < x_1 < x_2 <\ldots < x_n</tex> такие, что
<tex>
\Phi_j(x_k) = \left\{
\begin{aligned}
1 & ,\quad k = j\\
0 & ,\quad k \ne j\\
\end{aligned}\right.
</tex>.
}}

Для его построения обозначим за <tex>\omega_n(x) = \prod\limits_{j = 0}^n (x - x_j)</tex>. Это полином степени <tex>n + 1</tex>.

Обозначим <tex>L_n(x) = \sum\limits_{j = 0}^n y_j \Phi_j(x)</tex>.

<tex>L_n(x_k) = \sum\limits_{j = 0}^n y_j \Phi_j(x_k) = y_k \Phi_k(x_k) = y_k</tex>.

{{Теорема
|about=
Лагранжа
|statement=
Пусть <tex>f</tex> <tex>n + 1</tex> раз дифференцируема на <tex>\langle a; b\rangle</tex>. На этом промежутке задана система узлов.
Тогда для соответственного интерполяционного полинома Лагранжа выполняется равенство
<tex>f(x) = L_n(x) + \frac{f^{(n + 1)}(c_x)}{(n+1)!} \cdot \omega_n(x)</tex>, где <tex>c_x</tex> — некоторая точка из <tex>\langle a; b \rangle</tex>, зависящая от <tex>x</tex>.
}}

22. Определение выпуклой функции, неравенство Иенсена.

{{Определение
|definition=
Пусть [[Отображения|функция]] <tex>f(x)</tex> задана на <tex>[a; b]</tex>. Тогда она выпукла вверх на этом отрезке, если
<tex>\forall x_1, x_2 \in [a; b] \forall \alpha \in [0; 1] \quad \alpha f(x_1) + (1 - \alpha) f(x_2) \leq f(\alpha x_1 + (1 - \alpha)x_2)</tex>.
Если же всё время неравенство противоположно, то функция называется выпуклой вниз.
}}

В силу того, что было сказано о выпуклой комбинации, определение корректно: <tex>\alpha x_1 + (1 - \alpha)x_2 \in [a; b]</tex>.
Геометрической смысл этого факта состоит в том, что для выпуклой вверх функции её график будет лежать выше хорды.

{{Теорема
|about=
Неравенство Йенсена
|statement=
Пусть <tex>f(x)</tex> выпукла вверх на <tex>[a; b]</tex>. Тогда <tex>\forall x_1, x_2 \ldots x_n \in [a; b]</tex> и их выпуклой комбинации выполнено неравенство
<tex>\sum\limits_{k = 1}^n \alpha_k f(x_k) \leq f\left(\sum\limits_{k = 1}^n \alpha_k x_k\right)</tex>.
}}

23. Неравенство Гельдера для сумм.

{{Теорема
|about=
Гёльдера
|statement=
Пусть <tex>a_1, a_2 \ldots a_n, b_1, b_2 \ldots b_n > 0</tex>, <tex>p > 1</tex>, <tex dpi = "150">\frac1p + \frac1q = 1</tex>
Тогда
<tex>
\sum\limits_{k=1}^n a_k b_k \leq
\left(\sum\limits_{k = 1}^n a_k^p \right)^{1/p}
\left(\sum\limits_{k = 1}^n b_k^q \right)^{1/q}
</tex>
}}

24. Неравенство Минковского для сумм.

{{Теорема
|about=
Минковского
|statement=
Пусть снова <tex>a_1; a_2 \ldots a_n > 0</tex>, <tex>b_1; b_2 \ldots b_n > 0</tex>, <tex>p \ge 1</tex>.

Тогда
<tex>
\left(\sum\limits_{k = 1}^n (a_k + b_k)^p \right)^{1/p} \leq
\left(\sum\limits_{k = 1}^n a_k^p\right)^{1/p} + \left(\sum\limits_{k = 1}^n b_k^p\right)^{1/p}
</tex>
}}

25. Теорема о выпуклом модуле непрерывности.

Класс модулей непрерывности обозначим <tex>\Omega</tex>. Класс выпуклых вверх модулей непрерывности обозначим <tex>\Omega^*</tex>.

{{Утверждение
|statement=
Пусть имеется семейство выпуклых функций <tex>F_\alpha(t), \alpha \in A</tex>. Тогда <tex>f(t) = \inf\limits_{\alpha \in A} f_{\alpha} (t)</tex> — также выпуклая функция.
}}

{{Теорема
|about=
о выпуклом модуле непрерывности
|statement=
Пусть <tex>\omega \in \Omega</tex>. Тогда существует <tex>\omega^* \in \Omega^*</tex> такая, что <tex>\forall \lambda, t \ge 0</tex>
:<tex>\omega(\lambda t) \le \omega^* (\lambda t) \le (1 + \lambda) \cdot \omega(t)</tex>
}}

26. Полиномы и теорема Бернштейна.

Существует ли <tex>\forall \varepsilon > 0</tex> некоторый полином <tex>P</tex> (неважно, какой степени) такой, что <tex>\forall x \in [a; b]: \ |f(x) - P(x)| < \varepsilon</tex>?

{{Теорема
|author=
Бернштейн
|statement=
Пусть функция <tex>f</tex> - непрерывна на <tex>[0; 1]</tex>. Тогда <tex>\forall \varepsilon > 0 \ \exists P(x)</tex> - полином, такой, что <tex>\forall x \in [0; 1] \Rightarrow |f(x) - P(x)| < \varepsilon</tex>
}}

{{Теорема
|author=
Вейерштрасс
|statement=
Пусть функция <tex>f</tex> непрерывна на отрезке <tex>[a; b]</tex>.
Тогда <tex>\forall \varepsilon > 0\ \exists P \forall x \in [0; 1]: |f(x) - P(f, x)| \le \varepsilon</tex>
}}

27. Неопределенный интеграл: линейность, замена переменной интегрирования,
формула интегрирования по частям.

Линейность - интеграл суммы функций, произведения на число.

Пусть имеется [[Отображения|функция]] <tex>y = f(x)</tex>, заданная на <tex>[a; b]</tex>. Требуется найти функцию <tex>F(x)</tex>, такую, что <tex>F'(x) = f(x) \forall x \in [a; b]</tex>. Любая такая функция называется первообразной <tex>f</tex>.

{{Утверждение
|statement=
Если <tex>F_1' = f, F_2' = f</tex>, то <tex>F_2 = F_1 + \mathrm{const}</tex>
|proof=
Пусть <tex>g(x) = F_2(x) - F_1(x)</tex>. <tex>F_1, F_2</tex> непрерывны, следовательно, непрерывна и <tex>g</tex>, и можно применить теорему Лагранжа:
:<tex>g(x_2) - g(x_1) = g'(c)(x_2 - x_1)</tex>, но <tex>g' = F_2' - F_1' = 0</tex>.

Таким образом, <tex>g(x_2) = g(x_1) \forall x_1, x_2 \in [a; b]</tex>.
}}

Пусть <tex>f</tex> задана на <tex>[a; b]</tex>. Тогда совокупность всех её первообразных называется неопределённым интегралом и записывается:
:<tex>\int f(x)dx = \{F(x) + C, F' = f, c \in \mathbb R\}</tex>

Интегрирование по частям - <tex>\int udv = uv - \int vdu</tex>

Формула подстановки
: <tex> F(x) = \int f(x)dx </tex>
: <tex> x = \varphi(t) </tex>
: <tex> F(x) = \int f(\varphi(t)) \varphi'(t) dt </tex>

28. Интегральные суммы Римана, необходимое условие интегрируемости.

{{Определение
|definition=
Пусть <tex>\overline{x_k}</tex> {{---}} произвольное <tex>x</tex> из <tex>\left [ x_k,x_{k+1} \right ]</tex>, <tex>f</tex> {{---}} функция, заданная на отрезке <tex>[a; b]</tex>, <tex>\tau</tex> {{---}} разбиение отрезка <tex>[a; b]</tex>.

Тогда <tex>\sigma \left ( f, \tau, \left \{ \overline{x_k} \right \} \right )</tex>
(также обозначается как <tex>\sigma \left ( f, \tau \right )</tex> или <tex>\sigma \left ( \tau \right )</tex>)
<tex>~= \sum\limits_{k=0}^{n-1}</tex> <tex>f \left ( \overline{x_k} \right )\cdot\Delta_{k}</tex>
называется '''интегральной суммой Римана''' по разбиению <tex>\tau</tex>.
}}

Необхомдимое условие интегрируемости - функция является ограниченной.

29. Критерий интегрируемости по Риману.

Пусть <tex>\omega(f, \tau) = \overline{s}(\tau) - \underline{s}(\tau) = \sum\limits_{k = 0}^{n - 1} (M_k - m_k)\Delta x_k \ge 0</tex>

<tex>\lim\limits_{\operatorname{rang} \tau \to 0} \omega(f, \tau) \to 0 \Rightarrow</tex>
<tex>\forall \varepsilon > 0\ \exists \delta > 0 : \ \operatorname{rang} \tau < \delta \Rightarrow \omega(f, \tau) < \varepsilon</tex>

Определим <tex>\underline{I} = \sup\limits_{\{\tau\}} \underline{s}(\tau)</tex>,
<tex>\overline{I} = \inf\limits_{\{\tau\}} \overline{s}(\tau)</tex>

<tex>I = \lim\limits_{\operatorname{rang} \tau \to 0} \sigma(\tau)</tex>

{{Теорема
|about=
Критерий интегрируемости
|statement=
<tex>f \in \mathcal{R}(a; b) \iff \lim\limits_{\operatorname{rang} \tau \to 0} \omega(f, \tau) = 0</tex>
}}

30. Теорема Барроу.

{{Определение
|definition=
Объектом исследования этого параграфа является <tex>F(x) = \int\limits_a^x f(t) dt</tex>, <tex>f \in \mathcal{R}(a, b)</tex>, <tex>x \in [a, b]</tex>.
Такая функция называется ''интегралом с переменным верхним пределом'

{{Теорема
|author=Барроу
|statement=
Пусть <tex>f \in \mathcal{R}(a, b)</tex> и непрерывна в <tex>x_0 \in (a; b)</tex>.

Тогда <tex>F</tex> дифференцируема в этой точке и её производная равна <tex>F'(x_0) = f(x_0)</tex>.
}}

31. Формула Ньютона-Лейбница.

{{Теорема
|about=формула Ньютона-Лейбница
|statement=
Пусть <tex>F</tex> дифференцируема на <tex>[a; b]</tex>, её производная <tex>f</tex> интегрируема на этом же отрезке. Тогда
<tex>F(b) - F(a) = \int\limits_a^b f(x) dx</tex>
}}

32. Критерий сходимости несобственных интегралов.

Пусть <tex>F(A) = \int\limits_a^A f(x) dx</tex>. Применяя критерий Коши существования предела функции, приходим к критерию Коши сходимости несобственного интеграла:
<tex>\int\limits_a^{+\infty}</tex> сходится <tex>\iff \lim\limits_{A, B \to +\infty} \int\limits_A^B f(x)dx = 0</tex>.

33. Остаток формулы Тейлора в интегральной форме.

{{Утверждение
|statement=
Пусть в окрестности точки <tex>x_0</tex> функция <tex>f</tex> <tex>n + 1</tex> раз дифференцируема и её <tex>(n + 1)</tex>-я производная интегрируема. Тогда в окрестности точки <tex>x_0</tex> <tex>f(x) = \sum\limits_{k = 0}^n \frac{f^{(k)} (x_0)}{k!}(x - x_0)^k + \frac1{n!} \int\limits_{x_0}^x f^{(n + 1)}(t) (x-t)^n dt</tex>.
}}

34. Определение суммы числового ряда. Необходимый признак и критерий Коши сходимости ряда.

Классический способ суммирования:
<tex>S_n = \sum\limits_{k = 1}^n a_k</tex> {{---}} частичные суммы ряда.

{{Определение
|definition=
<tex>\lim\limits_{n\to\infty} S_n</tex> {{---}} сумма числового ряда. Если этот предел существует и конечен, то ряд называют сходящимся, иначе {{---}} расходящийся.
}}

{{Утверждение
|statement=
Если ряд сходится, то его слагаемые необходимо стремятся к нулю. Однако, это требование лишь необходимое
|proof=
Переписывая на языке частичных сумм критерий Коши существования предела последовательности, приходим к критерию Коши сходимости ряда:

<tex>\sum\limits_{k = 1}^\infty a_k</tex> {{---}} сходится <tex>\iff</tex> <tex>\sum\limits_{k = n}^{n + p} a_k \xrightarrow[n,p\to \infty]{} 0</tex>.

35. Интегральный признак Коши сходимости рядов.

{{Утверждение
|statement=
Пусть при <tex>x \geq 1</tex> определена функция <tex>y = f(x)</tex>, <tex>y</tex> убывает, <tex>y \geq 0</tex>. Тогда <tex>\int\limits_1^{+\infty} f(x) dx \equiv \sum\limits_{k = 1}^\infty f(k)</tex>.
}}

36. Ряды и теорема Лейбница.

{{Определение
|definition=
Знакочередующийся ряд, в котором <tex>a_n</tex> убывает и <tex>a_n</tex> стремится к нулю {{---}} ряд Лейбница
}}

{{Теорема
|author=Лейбниц
|statement=
1. Любой ряд Лейбница сходится.
2. Для остатка такого ряда справедлива оценка <tex>|R_n| \leq |a_{n + 1}|</tex>.
}}

37. Теорема Мертенса о произведении рядов по Коши.

{{Теорема
|about=
Мертенс
|statement=
Пусть ряд из <tex>a_n</tex> — абсолютно сходящийся, а ряд из <tex>b_n</tex> — условно сходящийся. Тогда эти два ряда можно перемножить по способу Коши.
}}

[[Категория:Математический анализ 1 курс]]

Двумерная разреженная таблица

2022-09-01T04:04:14Z

185.220.101.2:

Ортогональность

2022-09-01T04:04:08Z

185.220.101.2:

Пороговая функция

2022-09-01T04:03:56Z

185.220.101.2:

Теоретический минимум(2 семестр)

2022-09-01T04:03:40Z

185.220.101.2:

Комплексное евклидово пространство

2022-09-01T04:03:33Z

185.220.101.2:

Игра «Жизнь»

2022-09-01T04:03:17Z

185.220.101.2:

Методы трансляции

2022-09-01T04:03:03Z

185.220.101.2:

Задача о наибольшей общей палиндромной подпоследовательности

2022-09-01T04:02:56Z

185.220.101.2:

Класс 'P\poly'

2022-09-01T04:02:30Z

185.220.101.2:

Определение суммы числового ряда

2022-09-01T04:02:16Z

185.220.101.2:

Регулярные выражения с обратными ссылками

2022-09-01T04:01:56Z

185.220.101.2:

Распределённые вычислительные системы

2022-09-01T04:01:38Z

185.220.101.2:

Хеширование кукушки

2022-09-01T04:01:22Z

185.220.101.2:

Дерево, эквивалентные определения

2022-09-01T04:01:13Z

185.220.101.2:

Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи

2022-09-01T04:00:52Z

185.220.101.2:

Сведение задачи RMQ к задаче LCA

2022-09-01T04:00:45Z

185.220.101.2:

Busy beaver

2022-09-01T04:00:37Z

185.220.101.2:

Мастер-теорема

2022-09-01T04:00:28Z

185.220.101.2:

Спектральный анализ линейного оператора скалярного типа

2022-09-01T04:00:23Z

185.220.101.2:

Классы Sharp P, Sharp P-Complete

2022-09-01T04:00:14Z

185.220.101.2:

Rake-Compress деревья

2022-09-01T03:59:58Z

185.220.101.2:

{| 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 Майкл Наки].
|}

Задача, которая решается с помощью [[Link-Cut Tree|динамических деревьев]], формулируется следующим образом. Необходимо поддерживать лес деревьев и выполнять на нем следующие операции:
* <tex>\mathrm{link(u, v)}</tex> {{---}} добавить ребро <tex>(u, v)</tex>. Вершина <tex>u</tex> должна быть корнем некоторого дерева. Вершины <tex>u</tex> и <tex>v</tex> должны находиться в разных деревьях,
* <tex>\mathrm{cut(u, v)}</tex> {{---}} удалить ребро <tex>(u, v)</tex>. Ребро <tex>(u, v)</tex> должно присутствовать в графе,
* <tex>\mathrm{query()}</tex> {{---}} некоторый запрос относительно структуры дерева.

__TOC__
==Идея==
===Описание===
Пусть дано некоторое дерево <tex>T</tex>, для которого мы хотим выполнять описанные выше операции. Рассмотрим алгоритм '''сжатия дерева''' (англ. ''tree-contraction algorithm''), предложенный Миллером и Райфом. Алгоритм сжимает <tex>T</tex> в одну вершину путем применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> в несколько раундов:
* <tex>\mathrm{Rake}</tex> {{---}} все листья дерева сжимаются к своим родителям,
* <tex>\mathrm{Compress}</tex> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
<table align="center"><tr>
<td>[[Файл:Rctree-rake.png|x180px|thumb|Операция <tex>\mathrm{Rake}</tex>]]</td>
<td>[[Файл:Rctree-compress.png|x180px|thumb|Операция <tex>\mathrm{Compress}</tex>]]</td>
</tr></table>

Сжатие дерева требует линейного времени и логарифмическое число раундов. 
Для выбора вершин, которые будут удалены во время операции <tex>\mathrm{Compress}</tex>, применяется следующий метод: для каждой вершины генерируется рандомный бит и вершина добавляется в множество удаляемых только в том случае, когда она имеет одного ребёнка, бит для неё равен <tex>0</tex>, а для родителя и ребёнка равен <tex>1</tex>. 
Рассмотрим, как изменяется количество вершин в дереве после применения к нему операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>. Разобьём все вершины дерева на три группы:
* <tex>T_0</tex> {{---}} входящая степень равна нулю,
* <tex>T_1</tex> {{---}} входящая степень равна одному,
* <tex>T_2</tex> {{---}} входящая степень больше одного.

{{Лемма
|about=1
|statement=<tex>T_2 \leqslant T_0 - 1</tex>.
|proof=
Докажем по индукции по высоте дерева. 
* '''База
*: Для дерева из одной вершины утверждение верно.
* '''Переход
*: Пусть утверждение доказано для деревьев высоты меньше <tex>h</tex>. Докажем для дерева высоты ровно <tex>h</tex>. Рассмотрим степень корня: 
*:: Если корень имеет ровно одного ребенка, то переходим к случаю дерева высоты <tex>h - 1</tex>. Если у дерева несколько поддеревьев, то имеем: <tex>T_2 = 1 + \sum\limits_{u \in *: children(root)}T_2(u) \leqslant 1 + \sum\limits_{u \in children(root)}(T_0(u) - 1)</tex>  <tex> \leqslant -1 + \sum\limits_{u \in children}T_0(u) \leqslant -1 + T_0 = T_0 - 1</tex>.
}}
Заметим, что для леса деревьев лемма также справедлива.

{{Лемма
|about=2
|statement=После применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> к лесу, математическое ожидание количества вершин в нём не превосходит <tex>\dfrac{7}{8}</tex> от их исходного числа.
|proof=Все листья будут удалены после операции <tex>\mathrm{Rake}</tex>, а каждая вершина, у которой ровно один сын, будет удалена с вероятностью <tex>\dfrac{1}{8}</tex> после операции <tex>\mathrm{Compress}</tex> (так как мы рассматриваем три бита при выборе вершин и добавляем вершину в множество удаляемых только когда эти биты для родителя, вершины и ребёнка соответственно равны <tex>1</tex>, <tex>0</tex> и <tex>1</tex>). 
Таким образом математическое ожидание количества удаленных вершин <tex>\mathrm{deleted} = T_0 + \dfrac{T_1}{8}</tex>. Из предыдущей леммы получаем: 
<tex>\mathrm{deleted} = \dfrac{1}{2} (T_0 + T_2) + \dfrac{1}{8} T_1 \geqslant \dfrac{1}{8} (T_0 + T_1 + T_2)</tex>.
}}

{{Теорема
|statement=Математическое ожидание количества операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>, которые будут выполнены до полного сжатия дерева, равно <tex>O(\log{n})</tex>, где <tex>n</tex> {{---}} общее количество вершин.
|proof=Из леммы 2 известно, что после каждой итерации применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> число вершин в среднем уменьшается в константное число раз. Значит, количество итераций в среднем ограничено <tex>O(\log{n})</tex>.
}}

Для конкретного применения можно предположить, что рёбра дерева имеют вес, а вершины имеют метки.

===Пример операций===
В качестве примера сжатия дерева рассмотрим следующее взвешенное дерево:
[[Файл:RC_graph_example.png|400px|center|thumb|Исходное дерево <tex>T</tex>.]]

[[Файл:RC_graph_contraction.png|350px|right|thumb|Алгоритм сжатия дерева <tex>T</tex>.]]
На каждом раунде сжатия (перечислены сверху вниз) удаляется множество вершин с использованием операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>:
* Операция <tex>\mathrm{Rake}</tex> удаляет лист и ребро, смежное с ним, сохраняя в соседях данные: метку удалённой вершины, вес удалённого ребра и данные о сжатых на предыдущих раундах вершинах.
* Операция <tex>\mathrm{Compress}</tex> удаляет вершины, имеющие ровно одного сына, и смежные им рёбра. Например, для вершины <tex>v</tex> c сыном <tex>w</tex> и родителем <tex>u</tex> будут удалены рёбра <tex>(u, v)</tex> и <tex>(v, w)</tex>. После этого добавляется ребро <tex>(u, w)</tex>, а данные вершины <tex>v</tex> и удалённых рёбер (метка удалённой вершины, сохранённые данные и веса удалённых рёбер) сохраняются в соседние вершины.

Например, для приведённого дерева на первом раунде сжатия применяется операция <tex>\mathrm{Rake}</tex> для вершин <tex>a</tex>, <tex>d</tex>, <tex>n</tex>, <tex>k</tex> и операция <tex>\mathrm{Compress}</tex> для <tex>g</tex> и <tex>i</tex>. 
Сжатие может быть рассмотрено как рекурсивная кластеризация дерева в один '''кластер''' (англ. ''cluster''). Изначально вершины и рёбра составляют базовый кластер. Операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> формируют большие кластеры из нескольких меньших кластеров. На иллюстрации примера все кластеры (кроме базового) обозначены зелёными лепестками. Каждый кластер помечен заглавной буквой метки вершины, входящей в него. Например, кластер <tex>A</tex>, полученный после сжатия вершины <tex>a</tex> содержит вершины <tex>a</tex>, <tex>b</tex> и ребро <tex>(a, b)</tex>; сжатая вершина <tex>g</tex> создает кластер <tex>G</tex>, содержащий эту вершину и рёбра <tex>(f, g)</tex> и <tex>(g, h)</tex>. Во втором раунде, после сжатия вершины <tex>b</tex> создается кластер <tex>B</tex>, содержащий кластер <tex>A</tex> и ребро <tex>(b, c)</tex>. Представление сжатого дерева в виде кластеров:
[[Файл:RC_graph_clusters.png|400px|left|thumb|Кластеризованное дерево <tex>T</tex>.]]

Определим кластер как поддерево исходного дерева, порожденное множеством вершин.

Для кластера <tex>C</tex> скажем, что вершина <tex>v</tex> из <tex>C</tex> называется '''граничной вершиной''', если <tex>v</tex> смежная с вершинами не из <tex>C</tex>. '''Граница кластера''' {{---}} множество граничных вершин кластера, а '''степень кластера''' {{---}} количество граничных вершин кластера.

Например, для рассматриваемого дерева кластер <tex>A</tex> имеет границу <tex>\{b\}</tex> и степень <tex>1</tex>, а кластер <tex>G</tex> имеет границу <tex>\{f, g\}</tex> и степень <tex>2</tex>. При сжатии дерева все кластеры, кроме последнего, имеют степени <tex>1</tex> и <tex>2</tex>. Свойством алгоритмом сжатия является то, что:
* операции <tex>\mathrm{Rake}</tex> создают кластеры со степенью <tex>1</tex>,
* операции <tex>\mathrm{Compress}</tex> создают кластеры со степенью <tex>2</tex>,
* финальный кластер имеет степень <tex>0</tex>.

Процесс сжатия исходного дерева может быть представлен в виде нового дерева, называемого <tex>\mathrm{RC-tree}</tex>. Пример такого дерева для рассматриваемого исходного дерева:
[[Файл:RC_graph_tree.png|500px|center|thumb|RC-tree для дерева <tex>T</tex>.]]

Поскольку матожидание количества раундов {{---}} логарифм, то такое дерево будет сбалансированным. 
<tex>\mathrm{RC}</tex> дерево можно использовать для ответа на динамические запросы для статического дерева. Для этого в <tex>\mathrm{RC}</tex> дереве сохраним требуемую информацию (необходимо модифицировать для пересчёта информации операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>) и используем обход для ответа на запросы. Поскольку дерево с большой вероятностью является сбалансированным, обход дерева также можно осуществить за логарифм. 
Для динамических деревьев, например, если доступны операции добавления/удаления ребра (операции <tex>\mathrm{link}</tex> и <tex>\mathrm{cut}</tex>), нужно эффективно перестраивать отдельные кластеры, пересчитывая данные. Для этого можно обновлять данные начиная с листа дерева, соответствующего обновляемой вершине в исходном дереве, и подниматься вверх.

==Реализация==
===Хранение===
Для того, чтобы отвечать на запросы относительно структуры леса необходимо сохранить информацию о том, как происходил процесс сжатия леса. Для этого будем хранить таблицу, в каждой строке которой записана информация о структуре леса после выполнения операций. Каждая клетка таблицы будет хранить информацию о вершине после выполнения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>. Из информации будем сохранять родителя вершины, множество детей и метку, сжата ли вершина. 
Пример таблицы для следующей последовательности операций:
[[Файл:RC_tree_example.png|x200px|thumb|Пример выполнения операций.]]
{| class="wikitable"
|-
! Шаг
! align="center" | Операция
! <tex>1</tex>
! <tex>2</tex>
! <tex>3</tex>
! <tex>4</tex>
|-
| align="center" | 4
| align="center" | <tex>\mathrm{Rake}</tex>
| Родитель: {{---}} Дети: <tex>\emptyset</tex>
| align="center" | {{---}}
| align="center" | {{---}}
| align="center" | {{---}}
|-
| align="center" | 3
| align="center" | <tex>\mathrm{Compress}</tex>
| Родитель: {{---}} Дети: <tex>\{3\}</tex>
| align="center" | {{---}}
| Родитель: <tex>1</tex> Дети: <tex>\emptyset</tex>
| align="center" | {{---}}
|-
| align="center" | 2
| align="center" | <tex>\mathrm{Rake}</tex>
| Родитель: {{---}} Дети: <tex>\{2\}</tex>
| Родитель: <tex>1</tex> Дети: <tex>\{3\}</tex>
| Родитель: <tex>2</tex> Дети: <tex>\emptyset</tex>
| align="center" | {{---}}
|-
| align="center" | 1
|
| Родитель: {{---}} Дети: <tex>\{2\}</tex>
| Родитель: <tex>1</tex> Дети: <tex>\{3\}</tex>
| Родитель: <tex>2</tex> Дети: <tex>\{4\}</tex>
| Родитель: <tex>3</tex> Дети: <tex>\emptyset</tex>
|}
 
Для того, чтобы выбирать множество вершин для применения операции <tex>\mathrm{Compress}</tex> будем использовать следующий метод: для каждой вершины с помощью генератора псевдослучайных чисел выберем случайный бит. Вершина добавляется в множество, если у нее ровно один ребенок, она не является корнем и биты, которые были сгенерированы для нее, ребенка и родителя равны <tex>0</tex>, <tex>1</tex> и <tex>1</tex> соответственно.

Рассмотрим более подробно, как необходимо хранить клетки таблицы <tex>\mathrm{Rake-Compress}</tex> дерева. Для вершины необходимо сохранить ее родителя, а также множество детей. Для того, чтобы обрабатывать каждую клетку таблицы за <tex>O(\log{n})</tex>, нужно производить операции с множеством детей за <tex>O(1)</tex>. Рассмотрим, в каких случаях можно сжать вершину:
* если детей у вершины больше одного, то ее точно нельзя сжать,
* если у неё нет детей, то ее можно сжать только во время операции <tex>\mathrm{Rake}</tex>
* если у вершины один ребёнок, то её возможно сжать во время операции <tex>\mathrm{Compress}</tex>.
Чтобы определить, можно ли применить операцию <tex>\mathrm{Compress}</tex> к вершине, в том случае, когда у нее один ребёнок, нужно узнать, какой бит был сгенерирован на текущей итерации для ребёнка (один из трёх битов, генерируемых при операции <tex>\mathrm{Compress}</tex>). Для этого необходимо знать номер вершины-ребёнка. Значит, нам нужно определять, какие элементы находятся в множестве детей только в том случае, когда размер множества равен <tex>1</tex>. Поэтому, всю информацию о множестве можно хранить с помощью двух величин {{---}} хранить количество элементов в множестве и сумму их номеров. Поддерживая сумму номеров детей и их количество, можно эффективно узнавать номер вершины-ребёнка, когда это необходимо. Данная оптимизация позволяет за <tex>O(1)</tex> получать номер ребёнка и за <tex>O(1)</tex> обновлять множество детей. 
Если вершина является корнем, то в качестве ее родителя будем хранить ее номер. Кроме того необходимо хранить изменения, которые произойдут с клеткой при переходе к следующему слою: будем хранить, кто должен стать новым родителем, на сколько изменится количество детей, а также как изменится сумма их номеров. Все это необходимо для того, чтобы обрабатывать каждую изменившуюся клетку за <tex>O(1)</tex>. 

Псевдокод хранения клетки таблицы:
* <tex>\mathrm{id}</tex> {{---}} номер вершины,
* <tex>\mathrm{parent}</tex> {{---}} родитель вершины,
* <tex>\mathrm{cntChild}</tex> {{---}} количество детей вершины,
* <tex>\mathrm{sumChild}</tex> {{---}} сумма номеров детей,
* <tex>\mathrm{newParent}</tex> {{---}} новый родитель вершины после изменений,
* <tex>\mathrm{diffCntChild}</tex> и <tex>\mathrm{diffSumChild}</tex> {{---}} изменения, произведенные с полями <tex>\mathrm{cntChild}</tex> и <tex>\mathrm{sumChild}</tex> соответственно.

'''struct''' Cell''':'''
'''int''' id, parent, cntChild, sumChild
'''int''' newParent, diffCntChild, diffSumChild

'''func''' applyChanges()''':'''
parent = newParent
sumChild += diffSumChild
cntChild += diffCntChild
diffCntChild = diffSumChild = 0

'''func''' addChild(v: '''int''')''':'''
diffCntChild++
diffSumChild += v

'''func''' removeChild(v: '''int''')''':'''
diffCntChild--
diffSumChild -= v

Для хранения <tex>\mathrm{Rake-Compress}</tex> дерева будем использовать следующие данные:
* <tex>\mathrm{cells[]}</tex> {{---}} список клеток, которые ей соответствуют, для каждой вершины,
* <tex>\mathrm{rand}</tex> {{---}} генератор псевдослучайных чисел,
* <tex>\mathrm{time}</tex> {{---}} счётчик количества примененных операций по изменению структуры леса,
* <tex>\mathrm{lastUpdateTime[]}</tex> {{---}} массив, в котором для каждой вершины запишем номер последней операции, при обработки которой была изменена хотя бы одна клетка, которая соответствуют вершине: это позволит эффективно узнавать, была ли вершина уже помечена как поменявшаяся или нет.

'''struct''' RCTree(n: '''int''')''':'''
'''RndGen''' rand = RandBitsGenerator()
'''int''' time = 0
'''for''' i = 0 '''to''' n
lastUpdateTime[i] = 0
cells[i] = []

Кроме запросов о структуре леса, <tex>\mathrm{Rake-Compress}</tex> деревья можно использовать для подсчета значений некоторых функций. Например, каждой вершине можно сопоставить некоторое значение и узнавать, чему равна сумма значений всех вершин, которые находятся в поддереве.
Для этого в клетках таблицы <tex>\mathrm{Rake-Compress}</tex> дерева необходимо хранить не только состояние вершины, но и значение функции, посчитанной на части дерева, которое уже было сжато в вершину. Если функция является аддитивной, то ее пересчет аналогичен пересчету множества детей вершины. Так, если некоторая вершина сжимается к родителю, то в соответствующей родителю клетке необходимо обновить значение функции. При добавлении и удалении ребер необходимо в изменившихся клетках пересчитывать значение функции.

===Построение===
Рассмотрим, как работает алгоритм построения <tex>\mathrm{Rake-Compress}</tex> дерева. Будем строить таблицу по строкам. В каждый момент будем хранить множество вершин, которые еще не были сжаты, и перестраивать следующий слой. Также будем делать операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> одновременно. Чтобы определить, нужно ли сжимать вершину, воспользуемся следующим алгоритмом:
'''bool''' shouldRemoveVertex(c: '''Cell''', rand, layer: '''int''')''':'''
'''if''' c.cntChild == 0
'''return''' ''true''
'''if''' c.cntChild > 1 '''or''' c.parent == c.id
'''return''' ''false''
'''if''' getCellForVertex(c.sumChild).cntChild == 0
'''return''' ''false''
'''if''' rand.getBit(c.id, layer) == 0 '''and''' rand.getBit(c.sumChild, layer) == 1 '''and''' rand.getBit(c.parent, layer) == 1:
'''return''' ''true''
'''return''' ''false''

Таким образом, алгоритм построения дерева выглядит следующим образом:
'''func''' build(parent: '''int[n]''')''':'''
alive = <tex>\{0 \dots n - 1\}</tex>
'''int''' layer = 0
'''for''' i = 0 '''to''' n // заполним таблицу вершинами изначального дерева
cells[i].add(Cell(parent[i]))
'''while''' <tex>\mathrm{alive} \neq \emptyset</tex>
nextAlive = <tex>\emptyset</tex>
'''for''' <tex>v \in \mathrm{alive}</tex>
'''Cell''' c = getCellForVertex(v) // получить клетку таблицы, соответствующую вершине
'''if''' shouldRemoveVertex(c, rand, layer)
'''if''' c.cntChild == 1
getCellForVertex(c.sumChild).newParent = c.parent
getCellForVertex(c.parent).addChild(c.sumChild)
'''if''' c.parent <tex>\neq</tex> v
getCellForVertex(c.parent).remove(v)
'''else'''
nextAlive.add(v)
alive = nextAlive
'''for''' <tex>v \in \mathrm{alive}</tex>
'''Cell''' newCell = getCellForVertex(v).clone().applyChanges()
cells[v].add(newCell)
layer++
===Операции удаления и добавления ребра===
Как только некоторая вершина помечается как изменившаяся, отменим её действие на таблицу:
# Найдем момент времени, когда вершина сжимается к родителю.
# Рассмотрим, какие вершины поменяются при сжатии данной: это ее родитель (если он есть), а также сын (если он есть). Для каждой из этих вершин поменяем значения изменений, которые необходимо применить к состоянию.
# Пометим, что эти вершины поменялись на этом слое. Для этого на каждом слое будем хранить список вершин, которые на нем поменялись. А перед тем как обрабатывать очередной слой будем добавлять в множество изменившихся вершин вершины из соответствующего списка.
# Кроме удаления эффекта от изменившихся вершин также необходимо и добавить правильный эффект. Для этого будем для каждой из изменившихся вершин определять, как ее состояние меняется при переходе к следующему слою. Если вершина сжимается к ее родителю, то пометим родителя и ребенка (если он есть) и поменяем изменение, которое хранится в соответствующих клетках. А для пересчета состояния клеток воспользуемся значениями изменений, которые сохранены в клетках. 
Рассмотрим, что происходит с таблицей при изменении одного ребра. Основная идея заключается в том, чтобы научится пересчитывать все изменения таблицы за время пропорциональное их количеству. Для этого будем эффективно поддерживать множество изменившихся клеток. В момент, когда вершина помечается, как изменившаяся, найдем, как она влияет на таблицу и отменим это влияние. Для начала необходимо найти момент времени, когда вершина сжимается. В этот момент она влияет на не более чем две вершины. Изменим значения <tex>\mathrm{cntChild}</tex>, <tex>\mathrm{sumChild}</tex> и <tex>\mathrm{newParent}</tex> нужным образом. Также необходимо добавить эти вершины в множество изменившихся (в момент, когда будет обработан соответствующий слой). Поэтому, для каждого слоя еще будем хранить список вершин, которые должны быть помечены перед обработкой слоя. Алгоритм обновления дерева:
'''func''' changeTree(<tex>(u, v)</tex>: '''Edge''')''':'''
time = time + 1
affected = <tex>\emptyset</tex>
markAffected(u) // пусть из дерева было удалено ребро <tex>(u, v)</tex>
markAffected(v)
cells[u].parent = u
cells[v].cntChild--
cells[v].sumChild -= u
'''int''' layer = 0
'''while''' <tex>\mathrm{affected} \neq \emptyset</tex>
'''for''' <tex>v \in \mathrm{affectedOnLayer}</tex>
markAffected(v)
'''for''' <tex>v \in \mathrm{affected}</tex>
'''Cell''' c = getCellForVertex(v)
'''if''' shouldRemoveVertex(v)
cells[v].size = layer + 1
'''if''' c.cntChild == 1
getCellForVertex(c.sumChild).newParent = c.parent
getCellForVertex(c.parent).addChild(c.sumChild)
markAffected(c.sumChild)
'''if''' c.parent <tex>\neq</tex> v
getCellForVertex(c.parent).removeChild(v)
markAffected(c.parent)
affected.remove(v)
'''for''' <tex>v \in \mathrm{affected}</tex>
'''Cell''' newCell = getCellForVertex(v).clone().applyChanges()
cells[v][layer + 1] = newCell
layer++

'''func''' markAffected(v: '''int''')''':''' // пометить вершину как изменившуюся
'''if''' lastUpdateTime[v] == time
'''return''' // вершина уже помечена
lastUpdateTime[v] = time
affected.add(v)
removeEffectOfVertex(v)

'''func''' removeEffectOfVertex(v: '''int''')''':''' // удалить отметку о том, что вершина была помечена изменившийся
'''int''' layer = cells[v].size
'''Cell''' c = cells[v][layer]
'''if''' c.parent == v
'''return'''
cells[c].parent.removeChild(v)
'''if''' c.cntChild == 1
cells[c.parent].addChild(c.sumChild)
cells[c.sumChild].newParent = v

==Сравнение с Link-Cut Tree==
Для Link-Cut деревьев (основанных на [[Splay-дерево|splay-деревьях]]), как и для <tex>\mathrm{Rake-Compress}</tex> деревьев, время работы операций <tex>\mathrm{link}</tex> и <tex>\mathrm{cut}</tex> {{---}} <tex>O(\log{n})</tex>. В реальности <tex>\mathrm{RC}</tex> деревья оказываются медленнее, чем <tex>\mathrm{LC}</tex> деревья. 
Отличительной особенностью <tex>\mathrm{RC}</tex> деревьев является возможность параллельного построения: операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> можно выполнять параллельно для всех вершин. Если предположить, что множество детей можно пересчитывать за <tex>O(1)</tex>, то <tex>\mathrm{Rake-Compress}</tex> дерево можно построить за <tex>O(\log{n})</tex> в модели PRAM<ref>[https://en.wikipedia.org/wiki/Parallel_random-access_machine Wikipedia {{---}} Parallel random-access machine]</ref> в случае наличия <tex>\Omega(n)</tex> процессоров. 
Кроме этого, <tex>\mathrm{Rake-Compress}</tex> деревья могут оказаться полезными, если необходимо пересчитывать значения не на путях, а на поддеревьях.

==См. также==
* [[Link-Cut Tree]]

==Примечания==
<references/>

==Источники информации==
* [https://en.wikipedia.org/wiki/Parallel_Tree_Contraction Wikipedia {{---}} Parallel Tree Contraction]
* [https://github.com/BorysMinaiev/bachelor/blob/master/thesis_v2.pdf Б. Ю. Минаев {{---}} Реализация динамических Rake-Compress деревьев в случае отсутствия ограничения на степени вершин]
* [http://www.cs.cmu.edu/~jvittes/rc-trees Acar, Blelloch, and Vittes {{---}} RC-Tree implementation]
* [http://www.cs.princeton.edu/~rwerneck/papers/Wer06-dissertation.pdf R. Werneck {{---}} Design and Analysis of Data Structures for Dynamic Trees]
* G. L. Miller, J. H. Reif {{---}} Parallel Tree Contraction, Journal of Advances in Computer Research Volume 5, 1989
* Umit A. Acar, Guy E. Blelloch, Jorge L. Vittes {{---}} An Experimental Analysis of Change Propagation in Dynamic Trees, 1-2005

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

Теорема Самнера — Лас Вергнаса

2022-09-01T03:59:51Z

185.220.101.2:

Числа Каталана

2022-09-01T03:59:43Z

185.220.101.2:

{| 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 Майкл Наки].
|}

==Числа Каталана==

{{Определение
|id = def1
|definition ='''Числа Каталана''' {{---}} последовательность чисел, выражающих:
*количество [[Дерево_поиска,_наивная_реализация|не изоморфных упорядоченных бинарных деревьев]] с корнем и <tex dpi = 120> n + 1 </tex> листьями
*количество способов соединения <tex dpi = 120> 2n </tex> точек на окружности <tex dpi = 120> n </tex> не пересекающимися хордами
*количество [[Триангуляция_полигонов_(ушная_%2B_монотонная)|триангуляций выпуклого <tex dpi = 120> n </tex>-угольника]]
*количество способов полностью разделить скобками <tex dpi = 120> n + 1 </tex> множитель
*количество [[Правильные_скобочные_последовательности|корректных скобочных последовательностей, состоящих из <tex dpi = 120> n </tex> открывающих и <tex dpi = 120> n </tex> закрывающих скобок]]
*количество таблиц Юнга размером <tex dpi = 120>2n</tex>
*количество монотонных путей в квадрате размером <tex dpi = 120>n \times n</tex>, не пересекающих диагональ
*количество способов расставить скобки в произведении <tex dpi = 120>n</tex> множителей
*количество способов заполнить лестницу ширины и высоты <tex dpi = 120>n</tex> прямоугольниками
и так далее}}

Первые несколько чисел Каталана:

<tex dpi = 120> 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, \ldots </tex>

==Формулы вычисления чисел Каталана==

===Рекуррентная формула===
<tex dpi = 150>C_n = \sum\limits_{i = 0}^{n - 1} C_i C_{n - 1 - i} </tex>
====Доказательство====
Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях.

Пусть <tex dpi = 120>X</tex> — произвольная правильная скобочная последовательность длины <tex dpi = 120>2n</tex>. Она начинается с открывающейся скобки. Найдем парную ей закрывающуюся скобку и представим последовательность <tex dpi = 120>X</tex> в виде: <tex dpi = 120>X = (A)B</tex>, где <tex dpi = 120>A</tex> и <tex dpi = 120>B</tex> — тоже правильные скобочные последовательности. Если длина последовательности <tex dpi = 120>A</tex> равна <tex dpi = 120>2k</tex>, то последовательность <tex dpi = 120>A</tex> можно составить <tex dpi = 120>C_k</tex> способами. Тогда длина последовательности <tex dpi = 120>B</tex> равна <tex dpi = 120>2(n - k - 1)</tex> и последовательность <tex dpi =120>B</tex> можно составить <tex dpi = 120>C_{n - k - 1}</tex> способами. Комбинация любого способа составить последовательность <tex dpi = 120>A</tex> с любым способом составить последовательность <tex dpi = 120>B</tex> даст новую последовательность <tex dpi = 120>X</tex>, а величина <tex dpi = 120>k</tex> может меняться от <tex dpi = 120>0</tex> до <tex dpi = 120>n - 1</tex>. Получили рекуррентное соотношение: <tex dpi = 120>C_n = C_0 C_{n-1} + C_1 C_{n-2} + \ldots + C_{n-1} C_0 </tex>. Так как <tex dpi = 120>C_0 = 1</tex>, то последовательность совпадает с числами Каталана.

===Аналитическая формула===

<tex dpi = 150> C_n = \dfrac{1}{n+1} \dbinom {2n} {n} </tex>
====Доказательство====

Правильной скобочной структуре из <tex dpi = 120>n</tex> открывающих и <tex dpi = 120>n</tex> закрывающих скобок мы поставим в соответствие путь в квадрате <tex dpi = 120>[0, n]×[0, n]</tex>. Путь начинается в точке <tex dpi = 120>(0,0)</tex> и заканчивается в точке <tex dpi = 120>(n, n)</tex>. Открывающей скобке мы сопоставляем горизонтальный отрезок длины <tex dpi = 120>1</tex>, а закрывающей — вертикальный.
Если путь сопоставлен правильной структуре, то ни одна его точка не может лежать выше главной диагонали квадрата. Обратно, такому пути ("правильному пути") сопоставляется правильная скобочная структура.
Геометрическое представление правильных скобочных структур позволяет найти выражение для чисел Каталана.

Сместим правильный путь на одну клетку вниз. Теперь правильный путь начинается в точке
<tex dpi = 120> (0, -1) </tex>, заканчивается в точке <tex dpi = 120> (n, n-1) </tex> и не имеет общих точек с прямой <tex dpi = 120> y = x </tex> — биссектрисой первого квадранта. Нам нужно найти количество правильных путей. Для этого мы найдем количество неправильных, и из общего числа путей вычтем количество неправильных. Мы рассматриваем пути из точки <tex fpi = 120> (0, -1) </tex> в точку <tex dpi = 120> (n, n-1) </tex>. Длина такого пути равна <tex dpi = 120>2n</tex> и он содержит <tex dpi = 120>n</tex> вертикальных сегментов и <tex dpi = 120>n</tex> горизонтальных. Количество всех таких путей равно числу способов выбрать <tex dpi = 120>n</tex> вертикальных сегментов из общего числа <tex dpi = 120>2n</tex> сегментов, т.е. равно <tex dpi = 135> \dbinom {2n}{n} </tex>.

Рассмотрим неправильный путь и его первую точку на прямой <tex dpi = 120> y = x </tex> (точка <tex dpi = 120>A</tex>). Отрезок пути от точки <tex dpi = 120>(0, -1)</tex> до точки <tex dpi = 120>A</tex> заменим симметричным относительно прямой <tex dpi = 120>y = x</tex>. Мы получим путь длины <tex dpi = 120>2n</tex>, идущий из точки <tex dpi = 120>(-1, 0)</tex> в точку <tex dpi = 120>(n, n-1)</tex> (Смотри рис.).
[[Файл:Каталан2.PNG|right]]
Такой путь обязательно пересекает прямую <tex dpi = 120> y = x </tex>. Обратно, пусть нам дан путь длины <tex dpi = 120> 2n </tex> из точки <tex dpi = 120>(-1, 0)</tex> в точку <tex dpi = 120>(n, n-1)</tex> и пусть <tex dpi = 120> A </tex> — первая точка этого пути, лежащая на прямой <tex dpi = 120>y = x</tex>. Заменив участок пути от точки <tex dpi = 120>(-1, 0)</tex> до точки <tex dpi = 120>A</tex> на симметричный относительно прямой <tex dpi = 120>y = x</tex>, мы получим неправильный путь из точки <tex dpi = 120>(0, -1)</tex> в точку <tex dpi = 120>(n, n-1)</tex>. Следовательно, неправильных путей из точки <tex dpi = 120>(0, -1)</tex> в точку <tex dpi = 120>(n, n-1)</tex> столько же, сколько путей из точки <tex dpi = 120>(-1, 0)</tex> в
точку <tex dpi = 120>(n, n-1)</tex>. Такой путь длины <tex dpi = 120>2n</tex> содержит <tex dpi = 120>n+1</tex> горизонтальных и <tex dpi = 120>n-1</tex> вертикальных участков. Поэтому, количество таких путей равно <tex dpi = 135> \dbinom {2n}{n-1} </tex>. Значит, количество правильных путей (т.е. число Каталана <tex dpi = 120>C_n</tex>) равно

<tex> C_n = \dbinom {2n} {n} - \dbinom {2n} {n-1} = \dfrac{2n!}{n!n!} - \dfrac{2n!}{(n-1)!(n+1)!} = \dfrac{2n!}{n!} (\dfrac{1}{n!} - \dfrac{1}{(n-1)! (n+1)}) = \dfrac{2n!}{n!n!(n+1)} = \dfrac{1}{n+1} \dbinom {2n} {n} </tex>

==Задача разбиения выпуклого <tex dpi = 155 > n </tex>—угольника на треугольники не пересекающимися диагоналями==

===Доказательство===
[[Файл:Vectorpaint.png|145px|right]]

Пусть <tex dpi = 120>t_n</tex> — число триангуляций выпуклого <tex dpi = 120> (n + 2) </tex>-угольника при <tex dpi = 120> n \geqslant 1 </tex>. Положим <tex dpi = 120> t_0 = 1 </tex>. Пронумеруем вершины многоугольника, начиная с произвольной против часовой стрелки. Рассмотрим произвольную триангуляцию и выделим треугольник, примыкающий к стороне <tex dpi = 120>01</tex> (см. рис.).

Пусть <tex dpi = 120>k</tex> — номер третьей вершины этого треугольника. Выделенный треугольник разбивает <tex dpi = 120>(n + 2)</tex> — угольник на <tex dpi = 120>k</tex> — угольник и <tex dpi = 120>(n-k+3)</tex> — угольник, каждый из которых триангулирован диагоналями. Перенумеруем вершины этих многоугольников против часовой стрелки так, чтобы нумерация вершин в каждом из них начиналась с 0. В результате получим пару триангуляций <tex dpi = 120>k</tex>-угольника и <tex dpi = 120>(n-k+3)</tex> — угольника. Наоборот, каждая пара триангуляций <tex dpi = 120>k</tex> — угольника и <tex dpi = 120>(n-k+3)</tex> — угольника
определяет триангуляцию исходного многоугольника. Поэтому
<tex dpi = 120>t_{n+1} = t_0 t_n + t_1 t_{n-1} + \ldots + t_n t_0 </tex>
и поскольку <tex dpi = 120>t_0 = 1</tex>, последовательность чисел <tex dpi = 120>t_n</tex> совпадает с последовательностью Каталана.

===Пример===
[[Файл:Каталан.PNG|315px|thumb|right|Разбиение выпуклого шестиугольника]]
Ответ на задачу при <tex dpi = 120> n = 3 </tex> тривиален: никаких
диагоналей проводить не надо. В четырёхугольнике можно провести любую из
двух диагоналей, так что способов два. В пятиугольнике — из любой вершины две
диагонали, <tex dpi = 120> 5 </tex> способов. При <tex dpi = 120> n = 6 </tex> — первый не вполне очевидный ответ: <tex dpi = 120> 14 </tex> способов (см. рис.); чтобы
не запутаться, сторона BC выделена и отдельно нарисованы разрезания, в которых
к ней примыкают соответственно треугольники <tex dpi = 120> BCA, BCF, BCE </tex> и <tex dpi = 120> BCD </tex>.

Для семиугольника можно выделить одну из сторон и расклассифицировать разрезания в зависимости от того, какой треугольник к этой стороне примыкает. Имеем <tex>5</tex> разных случаев. В первом и последнем из них количество разбиений равно <tex>14</tex>,
ибо после отрезания треугольника остаётся шестиугольник. Во втором и четвёртом
случаях при вырезании треугольника семиугольник распадается на треугольник и
пятиугольник. В третьем случае семиугольник распадается на два четырёхугольника. Поскольку каждый из них можно разбить двумя способами, получаем
<tex dpi = 120>2 \cdot 2 = 4</tex>
варианта. Итак, семиугольник можно разбить всего
<tex dpi = 120> 14 + 5 + 2 \cdot 2 + 5 + 14 = 42 </tex>
способами. Рассматривая восьмиугольник, аналогично получаем
<tex dpi = 120> 42 + 14 + 2 \cdot 5 + 5 \cdot 2 + 14 + 42 = 132 </tex>
способа.Такие вычисления можно проводить и дальше.

==Подсчет чисел Каталана==
Числа Каталана просто посчитать с помощью рекуррентной формулы. Для этого понадобится <tex dpi = 120>O(n)</tex> памяти и <tex dpi = 120>O(n^2)</tex> времени. За <tex dpi = 120>O(n)</tex> времени их можно посчитать, если использовать аналитическую формулу. Также из аналитической формулы можно выразить простую реккурентную формулу:

<tex dpi = 135> C_n = \dfrac{4n-2}{n+1} C_{n-1} </tex>.

==Вычисление [[Производящая функция |производящей функции]] чисел Каталана==

{{Лемма
|id=lemma1.
|statement=<tex>\dbinom{\frac{1}{2}}{k} = \dfrac{(-1)^{k - 1}}{(2k - 1) \cdot 4^k} \cdot \dbinom{2k}{k} </tex>
|proof=
<tex>\dbinom{\frac{1}{2}}{k} = \dfrac{\dfrac{1}{2} \cdot (\dfrac{1}{2} - 1) \cdot (\dfrac{1}{2} - 2) \cdots (\dfrac{1}{2} - k + 1)}{k!} =
\dfrac{1 \cdot (1 - 2) \cdot (1 - 4) \cdots (1 - 2k + 2)}{2^k \cdot k!} = \dfrac{1 \cdot (-1) \cdot (-3) \cdots (-2k + 3)}{2^k \cdot k!}</tex>

<tex> = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{1 \cdot 3 \cdot (2k - 3) \cdot (2k - 1)}{2^k \cdot k!} = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{1 \cdot 2 \cdot 3 \cdots (2k - 3) \cdot (2k - 2) \cdot (2k - 1) \cdot 2k}{2 \cdot 4 \cdots (2k - 2) \cdot 2k \cdot 2^k \cdot k!}</tex>

<tex>= \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{(2k)!}{(2 \cdot 1) \cdot (2 \cdot 2) \cdots (2 \cdot (2k - 1)) \cdot (2 \cdot k) \cdot 2^k \cdot k!} = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{(2k)!}{2^k \cdot (1 \cdot 2 \cdots (k - 1) \cdot k) \cdot 2^k\cdot k!} </tex>

<tex> = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{(2k)!}{2^k \cdot k! \cdot 2^k\cdot k!} = \dfrac{(-1)^{k - 1}}{(2k - 1) \cdot 2^k \cdot 2^k} \cdot \dfrac{(2k)!}{k! \cdot k!}= \dfrac{(-1)^{k - 1}}{(2k - 1) \cdot 4^k} \dbinom{2k}{k}</tex>
}}

{{Задача
|definition = Вычислить производящую функцию чисел Каталана
}}

Пусть мы имеем последовательность чисел Каталана <tex>(C_0, C_1, C_2, \ldots)</tex>.

Будем искать её производящую функцию в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} C_n \cdot z^n</tex>

Как известно, рекуррентное соотношение для чисел Каталана имеет вид

<tex>

C_n=
\begin{cases}
1,&\text{если $n = 0$;}\\
\sum\limits_{k = 0}^{n - 1}C_k C_{n - k - 1},&\text{если $n > 0$.}
\end{cases}

</tex>

Домножаем <tex>C_n</tex> на <tex>z^n</tex>, получая

<tex>

z^n \cdot C_n=
\begin{cases}
z^0 = 1,&\text{если $n = 0$;}\\
z^n \sum\limits_{k = 0}^{n - 1}C_k C_{n - k - 1},&\text{если $n > 0$.}
\end{cases}

</tex>

Суммируя <tex>C_n z^n</tex> по всем <tex>n</tex> от <tex>0</tex> до <tex>\infty</tex>, получаем:

<tex>G(z) = \sum\limits_{n = 0}^{\infty} C_n z^n = C_0 z^0 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1} =
C_0 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1} = 1 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1}</tex> (так как <tex>C_0 = 1</tex> по определению чисел Каталана).

Получили, что <tex>G(z) = 1 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1}~~~~~ \textbf{(1)}</tex>

Распишем произведение <tex>G(z) \cdot G(z)</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul | произведения формальных степенных рядов]].

<tex>G(z) \cdot G(z) = (\sum\limits_{n = 0}^{\infty} C_n z^n) \cdot (\sum\limits_{n = 0}^{\infty} C_n z^n) = \sum\limits_{n = 0}^{\infty}z^n \sum\limits_{k = 0}^{n} C_k C_{n - k}</tex>

В последнем выражении выполним сдвиг индексации, положив <tex>n' = n + 1</tex>. Тогда имеем: <tex>n = n' - 1, n = 0 \Rightarrow n' = 1</tex>. Кроме того, <tex>z^n = z^{n' - 1}</tex>. <tex>n - k</tex> преобразуется в <tex>n' - 1 - k</tex> (так как <tex>n' - 1 = n</tex>). Тогда, преобразуя предыдущее выражение, получаем:

<tex>G(z) \cdot G(z) = \sum\limits_{n = 0}^{\infty}z^n \sum\limits_{k = 0}^{n} C_k C_{n - k} = \sum\limits_{n' = 1}^{\infty}z^{n' - 1} \sum\limits_{k = 0}^{n' - 1} C_k C_{n' - k - 1}</tex>

Домножая это произведение на <tex>z</tex>, получаем

<tex>z \cdot G^2(z) = z \cdot \sum\limits_{n' = 1}^{\infty}z^{n' - 1} \sum\limits_{k = 0}^{n' - 1} C_k C_{n' - k - 1} = \sum\limits_{n' = 1}^{\infty}z^{n'} \sum\limits_{k = 0}^{n' - 1} C_k C_{n' - k - 1}</tex>

Тогда

<tex>z \cdot G^2(z) = \sum\limits_{n = 1}^{\infty}z^{n} \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1} ~~~~ \textbf{(2)}</tex>

Из <tex> \textbf{(1)}</tex> и <tex>\textbf{(2)}</tex> получаем:

<tex>G(z) = 1 + z \cdot G^2(z)</tex>

Преобразуя, получаем квадратное уравнение на <tex>G(z) :</tex>

<tex>z \cdot G^2(z) - G(z) + 1 = 0</tex>

Из этого квадратного уравнения находим два варианта <tex>G(z) :</tex>

<tex>G(z) = \dfrac{1 \pm \sqrt{1-4z}}{2z}</tex>

Выберем из двух корней тот, который удовлетворяет определению <tex>G(z)</tex> как производящей функции чисел Каталана.

Домножая обе части на <tex>2z</tex>, получаем <tex>G(z) \cdot 2z = 1 \pm \sqrt{1-4z} ~~~~~\textbf{(3)}</tex>

Выберем нужный из двух корней, посчитав значение обеих частей при <tex>z = 0</tex>

Из определения производящей функции для чисел Каталана известно, что <tex>G(z) = C_0 + C_1 \cdot x + \ldots + C_n \cdot x^n + \ldots</tex>, тогда <tex>G(0) = C_0 = 1</tex>

Тогда при <tex>z = 0</tex> выражение <tex>\textbf{(3)}</tex> принимает вид <tex>G(0) \cdot 2 \cdot 0 = 1 \pm \sqrt{1-4 \cdot 0}</tex>, или <tex>0 = 1 \pm 1</tex>.

Тогда очевидно, нужно выбрать знак <tex>-</tex> в выражении, чтобы при <tex>z = 0</tex> левая и правая части были равны.

Тогда <tex>G(z) = \dfrac{1 - \sqrt{1-4z}}{2z}</tex>

Проверим, что <tex>G(z)</tex> действительно является производящей функцией чисел Каталана. Для этого разложим <tex>G(z)</tex> в ряд.

<tex>G(z) = \dfrac{1 - \sqrt{1-4z}}{2z} = \dfrac{1}{2z} - \dfrac{\sqrt{1-4z}}{2z} = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sqrt{1 - 4z} = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot (1 - 4z)^{\frac{1}{2}} = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} ((-4z)^n \cdot \dbinom{\frac{1}{2}}{n})</tex>

<tex> = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} ((-4z)^n \cdot \dfrac{(-1)^{n - 1}}{(2n - 1) \cdot 4^n} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} (\dfrac{(-1)^n \cdot 4^n \cdot z^n \cdot (-1)^{n - 1}}{(2n - 1) \cdot 4^n} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} (\dfrac{(-1)^{2n - 1} \cdot 4^n \cdot z^n}{(2n - 1) \cdot 4^n} \cdot \dbinom{2n}{n})</tex>

<tex> = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \dfrac{-z^0}{2 \cdot 0 - 1} \cdot \dbinom{2 \cdot 0}{0} - \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n})</tex>

<tex>= \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \dfrac{-1}{-1} \cdot 1- \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{z^n}{(2n - 1)} \cdot \dbinom{2n}{n})</tex>

<tex> = \sum\limits_{n = 1}^{\infty} (\dfrac{z^{n - 1}}{(4n - 2)} \cdot \dbinom{2n}{n}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dbinom{2n + 2}{n + 1}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dbinom{2n + 2}{n + 1}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{(2n + 2)!}{(n + 1)! \cdot (n + 1)!}</tex>

<tex> = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{(2n)! \cdot (2n + 1) \cdot 2 \cdot (n + 1)}{(n)! \cdot (n)! \cdot (n + 1) \cdot (n + 1)}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{2 \cdot (2n + 1)}{n + 1} \cdot \dbinom{2n}{n}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{(4n + 2)}{n + 1} \cdot \dbinom{2n}{n})</tex>

<tex>= \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{2 \cdot (2n + 1)}{n + 1} \cdot \dbinom{2n}{n}) = \sum\limits_{n = 0}^{\infty} (z^n \cdot \dfrac{1}{n + 1} \cdot \dbinom{2n}{n})</tex>

Тогда коэффициент при <tex>z^n</tex> в разложении <tex>G(z)</tex> равен <tex>\dfrac{1}{n + 1} \cdot \dbinom{2n}{n}</tex>, что совпадает с аналитической формулой для чисел Каталана. (<tex>C_n = \dfrac{1}{n + 1} \cdot \dbinom{2n}{n}</tex>) Поэтому <tex>G(z) = \sum\limits_{n = 0}^{\infty} z^n \cdot C_n</tex>, поэтому <tex>G(z) = \dfrac{1 - \sqrt{1-4z}}{2z}</tex> является производящей функцией чисел Каталана.

==Смотри также==
*[[Производящая_функция|Производящая функция]]

*[[Числа_Стирлинга_первого_рода|Числа Стирлинга первого рода]]

*[[Числа_Стирлинга_второго_рода|Числа Стирлинга второго рода]]

*[[Числа_Эйлера_I_и_II_рода|Числа Эйлера первого и второго рода]]

==Источники информации==
*[http://e-maxx.ru/algo/catalan_numbers MAXimal :: algo :: Числа Каталана]

*[http://habrahabr.ru/post/165295/ Числа Каталана / Хабрахабр]

*[https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD%D0%B0 Википедия — Числа Каталана]

*[http://kvant.mccme.ru/1978/07/chisla_katalana.htm Журнал "Квант"]

*[http://desolt.ru/karimova.html Глава 5. Комбинаторика]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]

Обучение в реальном времени

2022-09-01T03:59:37Z

185.220.101.2:

Консенсус в синхронных системах

2022-09-01T03:59:32Z

185.220.101.2:

Недетерминированные вычисления

2022-09-01T03:59:26Z

185.220.101.2:

Формула Уитни

2022-09-01T03:59:20Z

185.220.101.2:

Идеальное хеширование

2022-09-01T03:59:04Z

185.220.101.2:

Оценка сложности вычисления гиперобъема

2022-09-01T03:58:58Z

185.220.101.2:

Qqqq

2022-09-01T03:58:52Z

185.220.101.2:

Протоколы аутентификации

2022-09-01T03:58:47Z

185.220.101.2:

Сумма обратных к простым

2022-09-01T03:58:28Z

185.220.101.2:

Битовые операции

2022-09-01T03:58:22Z

185.220.101.2:

Гомоморфизм групп

2022-09-01T03:58:12Z

185.220.101.2:

Cравнение RMHC и генетического алгоритма на Royal Road Function

2022-09-01T03:57:59Z

185.220.101.2:

Арифметическое кодирование

2022-09-01T03:57:52Z

185.220.101.2:

{| 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 Майкл Наки].
|}

{{Определение
|definition=
'''Арифметическое кодирование''' (англ. ''Arithmetic coding'') {{---}} алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка <tex>[0; 1)</tex>.
Данный метод, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]], является [[Энтропия случайного источника|энтропийным]], то есть длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов.
}}

== Принцип действия ==
При арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>-\log_2 p(a)</tex>, следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки).
=== Кодирование ===
На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.
# Рассмотрим отрезок <tex>[0; 1)</tex> на координатной прямой.
# Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
# Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов.
# Повторим пункт <tex>(3)</tex> до конца входного потока.
# Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.

=== Псевдокод ===

*<math>\mathtt{s}\,</math> {{---}} текст, подаваемый на вход;
*<math>\mathtt{n}\,</math> {{---}} длина исходного текста;
*<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста;
*<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста;
*<math>\mathtt{probability[m]}\,</math> {{---}} массив вероятностей обнаружения символа в тексте;
*<math>\mathtt{Segment}\,</math> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:
**<math>\mathtt{left}\,</math> {{---}} левая граница подотрезка;
**<math>\mathtt{right}\,</math> {{---}} правая граница подотрезка;
*<math>\mathtt{left}\,</math>, <math>\mathtt{right}\,</math> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования.

'''struct''' Segment:
'''double''' left
'''double''' right

'''Segment'''[m] defineSegments(letters: '''char'''[m], probability: '''double'''[m]):
'''Segment'''[m] segment
'''double''' l = 0
'''for''' i = 0 '''to''' m - 1
segment[letters[i]].left = l
segment[letters[i]].right = l + probability[i]
l = segment[letters[i]].right
'''return''' segment

'''double''' arithmeticCoding(letters: '''char'''[m], probability: '''double'''[m], s: '''char'''[n]):
'''Segment'''[m] segment = defineSegments(letters, probability)
'''double''' left = 0
'''double''' right = 1
'''for''' i = 0 '''to''' n - 1
'''char''' symb = s[i]
'''double''' newRight = left + (right - left) * segment[symb].right
'''double''' newLeft = left + (right - left) * segment[symb].left
left = newLeft
right = newRight
'''return''' (left + right) / 2

'''Замечание:''' для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона <tex>[left; right]</tex> число, содержащее наименьшее количество знаков в двоичной записи.

=== Декодирование ===
Алгоритм по вещественному числу восстанавливает исходный текст.
# Выберем на отрезке <tex>[0; 1)</tex>, разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ.
# Нормируем подотрезок и вещественное число.
# Повторим пункты <tex>1</tex>{{---}}<tex>2</tex> до тех пор, пока не получим ответ.

=== Псевдокод ===

*<math>\mathtt{code}\,</math> {{---}} вещественное число, подаваемое на вход;
*<math>\mathtt{n}\,</math> {{---}} длина восстанавливаемого текста;
*<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста;
*<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста;
*<math>\mathtt{probability[m]}\,</math> {{---}} массив вероятностей обнаружения символа в тексте;
*<math>\mathtt{segment}\,</math> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:
** <math>\mathtt{left}\,</math> {{---}} левая граница подотрезка;
** <math>\mathtt{right}\,</math> {{---}} правая граница подотрезка;
** <math>\mathtt{character}\,</math> {{---}} значение символа.

'''struct''' Segment:
'''double''' left
'''double''' right
'''char''' character

'''Segment'''[m] defineSegments(letters: '''char'''[n], probability: '''double'''[n]):
'''Segment'''[m] segment
'''double''' l = 0
'''for''' i = 0 '''to''' m - 1
segment[i].left = l
segment[i].right = l + probability[i]
segment[i].character = letters[i]
l = segment[i].right
'''return''' segment

'''string''' arithmeticDecoding(letters: '''char'''[m], probability: '''double'''[m], code: '''double''', n: '''int'''):
'''Segment'''[m] segment = defineSegments(letters, probability)
'''string''' s = ""
'''for''' i = 0 '''to''' n - 1
'''for''' j = 0 '''to''' m - 1
'''if''' code<tex>\small{~\geqslant~}</tex>segment[j].left '''and''' code < segment[j].right
s += segment[j].character
code = (code – segment[j].left) / (segment[j].right – segment[j].left)
'''break'''
'''return''' s

'''Замечание:''' кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.

'''Замечание:''' Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера {{---}} поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, <tex>\dfrac{1}{3}</tex>), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число. В такой реализации вероятность встречи символа представляется в виде рационального числа. Поскольку в каждой итерации будет переход из текущего отрезка в один из его <tex>m</tex> подотрезков, кратных по длине <tex>n</tex>, а всего итераций <tex>n</tex>, в конечном результате знаменатель дроби не превысит <tex>n^{n}</tex>, а поскольку сумма всех вероятностей встречи символов равна <tex>1</tex>, полученная дробь будет находиться в промежутке <tex>[0; 1)</tex>.

== Пример работы ==
Рассмотрим в качестве примера строку <tex>abacaba</tex>:
=== Кодирование ===
{|class="wikitable"
!Символ||Частота появления
|-
|<tex>a</tex>||<tex>0.571429</tex>
|-
|<tex>b</tex>||<tex>0.285714</tex>
|-
|<tex>c</tex>||<tex>0.142857</tex>
|}
[[Файл:Code_png.png|thumb|right|200px|Пример работы кодировщика ]]
{|class="wikitable"
!Считанный символ||Левая граница отрезка||Правая граница отрезка
|-
|||<tex>0</tex>||<tex>1</tex>
|-
|<tex>a</tex>||<tex>0</tex>||<tex>0.571429</tex>
|-
|<tex>b</tex>||<tex>0.326531</tex>||<tex>0.489796</tex>
|-
|<tex>a</tex>||<tex>0.326531</tex>||<tex>0.419825</tex>
|-
|<tex>c</tex>||<tex>0.406497</tex>||<tex>0.419825</tex>
|-
|<tex>a</tex>||<tex>0.406497</tex>||<tex>0.414113</tex>
|-
|<tex>b</tex>||<tex>0.410849</tex>||<tex>0.413025</tex>
|-
|<tex>a</tex>||<tex>0.410849</tex>||<tex>0.412093</tex>
|}
Код: <tex>0.411471</tex>

=== Декодирование ===
Код: <tex>0.411471</tex>
[[Файл:decode1_png.png|thumb|right|200px|Пример работы декодировщика ]]
{|class="wikitable"
!Декодируемый символ||Код
|-
|<tex>a</tex>||<tex>0.411471</tex>
|-
|<tex>b</tex>||<tex>0.720074</tex>
|-
|<tex>a</tex>||<tex>0.520259</tex>
|-
|<tex>c</tex>||<tex>0.910454</tex>
|-
|<tex>a</tex>||<tex>0.373178</tex>
|-
|<tex>b</tex>||<tex>0.653061</tex>
|-
|<tex>a</tex>||<tex>0.285714</tex>
|}

'''Замечание:''' при декодировании текста можно не только нормализовывать рабочий отрезок и текущий код, но и уменьшать рабочий отрезок (аналогично кодированию), не изменяя значение кода.
=== Декодирование (второй способ)===
Код: <tex>0.411471</tex>
[[Файл:decode2_png.png|thumb|right|200px|Пример работы декодировщика (второй способ) ]]
{|class="wikitable"
!Декодируемый символ||colspan="4" |Границы отрезка
|-
|<tex>a</tex>||<tex>0</tex>||<tex>0.571429</tex>||<tex>0.857143</tex>||<tex>1</tex>
|-
|<tex>b</tex>||<tex>0</tex>||<tex>0.326531</tex>||<tex>0.489796 </tex>||<tex>0.571429</tex>
|-
|<tex>a</tex>||<tex>0.326531 </tex>||<tex>0.419825 </tex>||<tex>0.466472 </tex>||<tex>0.489796 </tex>
|-
|<tex>c</tex>||<tex>0.326531</tex>||<tex>0.379842</tex>||<tex>0.406497</tex>||<tex>0.419825</tex>
|-
|<tex>a</tex>||<tex>0.406497</tex>||<tex>0.414113</tex>||<tex>0.417921 </tex>||<tex>0.419825</tex>
|-
|<tex>b</tex>||<tex>0.406497</tex>||<tex>0.410849</tex>||<tex>0.413025</tex>||<tex>0.414113</tex>
|-
|<tex>a</tex>||<tex>0.410849</tex>||<tex>0.412093</tex>||<tex>0.412714</tex>||<tex>0.413025</tex>

|}
== Оценка длины кодового слова ==
{{Теорема
|statement=При арифметическом кодировании длина кодового слова не превышает энтропии Шеннона случайного источника с частотами, равными долям вхождения символа в строку, умноженной на длину строки.

||proof=Условные обозначения:
*<tex>A(s)</tex> {{---}} размер кодового слова <tex>s</tex>,
*<tex>L</tex> {{---}} длина последнего отрезка в арифметическом кодировании <tex>s</tex>,
*<tex>l</tex> {{---}} длина исходной строки <tex>s</tex>,
*<tex>A(s)</tex> {{---}} размер кодового слова <tex>s</tex>,
*<tex>n</tex> {{---}} размер алфавита,
*<tex>f_i</tex> {{---}} частота встречаемости символа,
*<tex>p_i = \dfrac{f i}{l}</tex> {{---}} вероятность вхождения символа,
*<tex>H(p_1 \ldots p_n)</tex> {{---}} энтропия случайного источника с частотами <tex>(p_1 \ldots p_n)</tex>.

Пусть в результате арифметического кодирования мы получили число <tex>\dfrac{x}{2^q}</tex>, где <tex>q</tex> {{---}} количество бит в кодовом слове, т.е. <tex>q = A(s)</tex>.

Из алгоритма арифметического кодирования <tex> L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}</tex>.

Тогда <tex>A(s) = q \leq -\log_2 L = -\log_2 \prod\limits_{i=1}^n p_{i}^{f_{i}} = -\sum\limits_{i=1}^n f_i\cdot \log_2 p_i = -l \cdot \sum\limits_{i=1}^n p_i\cdot \log_2 p_i </tex>.

Энтропия источника вычисляется по следующей формуле <tex>H(p_1 \ldots p_n) = -\sum\limits_{i=1}^n p_i\cdot \log_2 p_i</tex>.

Следовательно, <tex>A(s) \leq l \cdot H(p_1 \ldots p_n)</tex>.
}}

== Адаптивное арифметическое кодирование ==

Необходимость применения адаптивного алгоритма возникает в том случае, если вероятностные оценки символов сообщения не известны до начала работы алгоритма. Преимущество такого подхода кодирования заключается в том, что декодировщику не нужно передавать вероятностные оценки для символов, он будет строить их по мере декодирования сообщения, что может сильно сократить вес такого сообщения.

=== Алгоритм кодирования ===

На вход алгоритму передаётся последовательность символов и алфавит. Каждому символу алфавита <tex>\alpha \in \sum</tex> сопоставляется его вес <tex>w_\alpha</tex>. В начале работы алгоритма все веса символов равны <tex>1</tex>.
Вероятность каждого символа <tex>\alpha</tex> {{---}} <tex>p(\alpha)</tex> устанавливется равной его весу, делённому на суммарный вес всех символов: <tex dpi="180">p(\alpha) = \dfrac{w_\alpha}{\sum_{i=1}^n w_i}</tex>. После получения очередного символа и построения нужного интервала, вес символа увеличивается на <tex>1</tex>. Когда все символы последовательности будут обработаны, необходимо либо записать маркер конца последовательности, либо запомнить её длину, чтобы позже передать декодировщику. После получения нужных границ <tex>[l, r]</tex>, в котором будет лежать код, необходмо выбрать число <tex>x</tex>, описывающее кодирование:
<tex>x \in [l, r]</tex>. Выбор числа <tex>x</tex> производится также, как и в неадаптивном алгоритме. Выбирается число вида <tex>\dfrac{x}{2^p}: x,p \in \mathbb N</tex>.

=== Псевдокод алгоритма ===

* <tex>\mathtt{in}</tex> {{---}} текст, подаваемый на вход
* <tex>\mathtt{n}</tex> {{---}} длина исходного текста
* <tex>\mathtt{Segment}</tex> {{---}} структура, задающая подотрезок отрезка <tex>[0, 1)</tex>, соответствующая конкретному символу. Имеет следующие поля:
** <tex> \mathtt{left} </tex> {{---}} левая граница подотрезка
** <tex> \mathtt{right} </tex> {{---}} правая граница подотрезка
* <tex> \mathtt{m} </tex> {{---}} мощность алфавита
* <tex> \mathtt{weight} </tex> {{---}} веса символов алфавита
* <tex> \mathtt{segments} </tex> {{---}} набор подотрезков, соответствующих символам алфавита
* <tex> \mathtt{left, right} </tex> {{---}} границы отрезка, содержащие возможный результат арифметического кодирования
* <tex> \mathtt{getAlphabet(in : char[n])}</tex> {{---}} функция возвращает множество различных символов в тексте <tex> \mathtt{in} </tex>

==== Подотрезок ====

'''struct''' Segment:
'''double''' left;
'''double''' right;

==== Определение начальных границ подотрезков ====

'''map<char,''' '''Segment'''> defineSegments'''('''set<char>''' alphabet):
// определяем размер подотрезков 
double p = 1 / alphabet.size()
'''Segments'''[m] segments
// задаём левую и правую границы каждого из отрезков 
'''double''' curLeft = 0
'''double''' curRight = p
// разбиваем отрезок [0,1) на подотрезки, соответсвующие символам алфавита 
'''for''' i = 0 '''to''' m - 1
segments[i].left = curLeft
segments[i].right = curRight
curLeft = curRight
curRight = curRight + p
'''return''' segments

==== Перестройка подотрезков ====
'''map<char''', '''Segment'''> '''resizeSegments'''(alphabet : '''char'''[m], weight : '''map<char''', '''int>''', segments : '''map<char''', '''Segment>''')
// новая левая граница подотрезка
'''double''' l = 0
// сумма весов символов алфавита
'''int''' sum = 0
// подсчет суммы весов символов алфавита
'''for''' i = 0 '''to''' m - 1
sum = sum + weight[i]
// перестроение подотрезков, для символов алфавита
'''for''' i = 0 '''to''' m - 1
'''char''' c = alphabet[i]
segments[c].left = l
segments[c].right = l + (weight[c] / sum)
l = segments[c].right;
'''return''' segments

==== Определение начальных весов символов алфавита ====
'''map<char''', '''int> defineWeights'''(alphabet : '''set<char>'''):
'''map<char''', '''int>''' weight
// проход по всем символам алфавита и установка начального веса
'''for''' i = 0 '''to''' m - 1
'''char''' c = alphabet[i]
weight[c] = 1
'''return''' weight

==== Кодирование строки ====
'''double''' '''adaptiveCoding'''(in : '''char'''[n], alphabet : '''set<char>'''):
'''int'''[m] weight = defineWeights(alphabet)
'''int'''[m] segments = defineSegments(alphabet)
// начальные границы отрезка
'''double''' left = 0
'''double''' right = 1
'''for''' i = 0 '''to''' n - 1
'''char''' c = in[i]
// увеличение веса символа строки
weight[c]++
// определение новых границ диапазона с искомым кодом, с учётом полученного символа c
'''double''' newRight = left + (right - left) * segments[c].right
'''double''' newLeft = left + (right - left) * segments[c].left
left = newLeft
right = newRight
resizeSegments(alphabet, weight, segments)
'''return''' (left + right) / 2;

=== Алгоритм декодирования ===
При декодировании последовательности символов также используется множество весов <tex>w</tex> символов алфавита <tex>\sum</tex>. В начале работы алгоритма все веса символов равны <tex>1</tex>. На каждом шаге определяется интевал, содержащий данный код, по интервалу находится символ, который потом записывается в выходную последовательность. Вес полученного символа <tex>\alpha</tex> увеличивается на <tex>1</tex>. Отрезки, соответствующие символам алфавита, перестраиваются в зависимости от изменённых весов символов и размера текущего подотрезка. При получении символа конца последовательности или обработки нужного числа символов алгоритм завершает работу.

==== Декодирование ====
* <tex>\mathtt{code}</tex> {{---}} вещественное число, подаваемое на вход;
* <tex>\mathtt{n}</tex> {{---}} длина декодируемой строки;
* <tex>\mathtt{m}</tex> {{---}} мощность алфавита;
* <tex>\mathtt{weight}</tex> {{---}} веса символов алфавита;
* <tex>\mathtt{segments}</tex> {{---}} веса символов алфавита;

'''string''' '''decode('''code : '''double''', alphabet : '''set<char>''', '''int''' len):
'''map<char, int>''' weight = '''defineWeights('''alphabet''')'''
'''map<char, Segment>''' segments = '''defineSegments('''alphabet''')'''
'''string''' ans = ""
// декодирование строки
'''for''' i = 0 '''to''' n - 1:
// поиск нужного символа исходной строки по текущему значению кода
'''for''' j = 0 '''to''' m - 1:
'''char''' c = alphabet[j]
'''if''' code >= segments[c].left '''and''' code < segments[c].right
ans = ans + c
weight[c]++
// вычисление следующего значения кода, с учетом декодированного символа c
code = (code - segments[c].left) / segments[c].right - segments[c].left)
// перестроение подотрезков, с учётом декодированного символа c 
resizeSegments(alphabet, weight, segments)
'''break;'''
'''return''' ans

=== Оценка минимальной и максимальной длины кода ===

{{Теорема
|id = th1.
|statement= При адаптивном арифметическом кодировании строки длины <tex>\mathtt{l}</tex>, символы которой принадлежат алфавиту мощности <tex>\mathtt{n}</tex>, полученный код будет лежать в диапазоне <tex>[\dfrac{(n-1)!}{(n+l-1)!}, \dfrac{l!(n-1)!}{(n+l-1)!}]</tex>
|proof=
Во время кодирования строки алгоритм выбирает необходимый подотрезок, увеличивает вес символа и перестраивает подотрезки.
Пусть <tex>L</tex> {{---}} результат кодирования строки длины <tex>l</tex>, использующей алфавит длины <tex>n</tex>. Код <tex>L</tex> формируется следующим образом: на каждом из шагов <tex>k=1, 2, \dots, l</tex>
он изменяется в <tex>\dfrac{w_{\alpha_k}}{n+k-1}</tex> раз. На каждом шаге <tex>k</tex>-й символ <tex>\alpha</tex> будет иметь вес <tex>\alpha_k</tex> (каждый раз больший на <tex>1</tex>, потому что алгоритм адаптивный).
Значит, на каждом шаге суммарный вес символов будет увеличиваться на <tex>1</tex>, т.е. на шаге <tex>k</tex> суммарный вес символов будет равен <tex>n+k-1</tex>
Во время перестроения подотрезков, по алгоритму, каждому символу ствавится в соответствие подотрезок длины <tex>\dfrac{w_{\alpha_k}}{n+k-1}</tex>.

В общем виде его можно представить так:

<tex>
L = \prod_{i=1}^l \dfrac{w_{\alpha_i}}{n+i-1}
</tex>

Знаменатель каждого следующего члена произведения будет увеличиваться на <tex>1</tex>, так как на каждом шаге увеличивается вес одного из символов алфавита.
Соответственно, чтобы минимизировать произведение, необходимо минимизировать числители его членов.
Этого можно достичь, если передать на вход алгоритму строку, состоящую из неповторяющихся символов.
В таком случае вес каждого из полученных символов будет равен <tex>1</tex>, а значение кода на каждом из шагов <tex>k=1, 2, \dots, l</tex> будет изменяться в <tex>\dfrac{1}{n+k-1}</tex> раз.

Соответственно, формула примет вид:

<tex>
L_{min} = \prod_{i=1}^l \dfrac{1}{n+i-1} = \dfrac{1}{\dfrac{(n+l-1)!}{(n-1)!}} = \dfrac{(n-1)!}{(n+l-1)!}
</tex>

Можно записать, используя формулы комбинаторики:

<tex>
L_{min} = \dfrac{1}{{\binom{l}{n+l-1}}l!} = \dfrac{1}{C_{n+l-1}^{l}l!}
</tex>
==== Верхняя граница ====

Для того, чтобы максимизировать произведение, необходимо увеличить числитель каждого члена произведения. Этого можно достичь, если передать на вход алгоритму строку, состоящую из одинаковых символов. В таком случае, на каждом из шагов <tex>k=1, 2, \dots, l</tex> вес символа будет равен k, а значение кода будет изменяться в <tex>\dfrac{k}{n+k-1}</tex> раз.

Соответственно, формула будет иметь следующий вид:

<tex>
L_{max} = \prod_{i=1}^l \dfrac{i}{n+i-1} = \dfrac{l!(n-1)!}{(n+l-1)!}
</tex>

Можно записать, используя формулы комбинаторики:

<tex>
L_{max} = \dfrac{1}{\binom{n+l-1}{l}} = \dfrac{1}{C_{n+l-1}^{l}}
</tex>

}}

{{Утверждение
|id = th1.
|statement=При адаптивном арифметическом кодировании строки длины <tex>l</tex>, символы которой принадлежат алфавиту мощности <tex>n</tex>, количество бит, необходимых для кодирования сообщения будет лежать в диапазоне <tex>[-\sum_{i=1}^{l} log_2{\dfrac{1}{n+i-1}}, -\sum_{i=0}^{l-1}log_2\dfrac{i+1}{n+i}]</tex>
|proof=
Произведём оценку количества бит, необходимых для записи кода $L$ в общем случае:

<tex>
log_2 L = -\sum_{i=1}^{l} log_2 \frac{w_{\alpha_i}}{n+i-1}
</tex>

Все коды лежат в диапазоне <tex>[0, 1)</tex>.

Таким образом:

Максимальное количество бит будет затрачено при записи кода, являющегося минимальной дробью:

<tex>
log_2 L_{min} = -\sum_{i=1}^{l} log_2 \frac{1}{n+i-1}
</tex>

Минимальное число бит будет затрачено в случае записи кода максимального размера:

<tex>
log_2 L_{max} = -\sum_{i=0}^{l-1} log_2 \frac{i+1}{n+i}
</tex>
}}

== См. также ==
* [[Алгоритм_Хаффмана | Алгоритм Хаффмана]]
* [[Алгоритмы_LZ77_и_LZ78 | Алгоритмы LZ77 и LZ78]]
* [[Энтропия_случайного_источника | Энтропия случайного источника]]

== Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Википедия {{---}} Арифметическое кодирование]
* [https://en.wikipedia.org/wiki/Arithmetic_coding Wikipedia {{---}} Arithmetic coding]
* [http://www.sernam.ru/cod_3.php Арифметическое кодирование]
* [http://rain.ifmo.ru/cat/view.php/vis/data-compression/arithmetic-coding-2006 Визуализатор арифметического кодирования]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория вероятности]]
[[Категория: Алгоритмы сжатия]]

Полином Жегалкина

2022-09-01T03:57:41Z

185.220.101.2:

{| 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 Майкл Наки].
|}

'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') — полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве средства для представления [[Определение булевой функции|функций булевой логики]]. Полином Жегалкина имеет следующий вид:

<tex>P = a_{000\ldots000} \oplus a_{100\ldots0} x_1 \oplus a_{010\ldots0} x_2 \oplus \ldots \oplus a_{00\ldots01} x_n \oplus a_{110\ldots0} x_1 x_2 \oplus \ldots \oplus a_{00\ldots011} x_{n-1} x_n \oplus \ldots \oplus a_{11\ldots1} x_1 x_2 \ldots x_n </tex>

== Полнота ==

По [[Теорема Поста о полной системе функций|теореме Поста]], чтобы система булевых функций была полной, надо, чтобы в ней существовали

#Хотя бы одна функция, не сохраняющая <tex>0</tex>;
#Хотя бы одна функция, не сохраняющая <tex>1</tex>;
#Хотя бы одна нелинейная функция;
#Хотя бы одна немонотонная функция;
#Хотя бы одна несамодвойственная функция.

Исходя из этого, система функций <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex> является полной:

{| class="wikitable" style="width:8cm" border="1"
|-align="center" bgcolor=#EEEEFF
!<tex>x_0</tex>||<tex>x_1</tex>||<tex>\ldots</tex>||<tex>x_n</tex>
|<tex>1</tex>||<tex>\land</tex>||<tex>\oplus</tex>
|-align="center"
!<tex>0</tex>||<tex>0</tex>||<tex>\ldots</tex>||<tex>0</tex>
|<tex>1</tex>||<tex>0</tex>||<tex>0</tex>
|-align="center"
!<tex>1</tex>||<tex>0</tex>||<tex>\ldots</tex>||<tex>0</tex>
|<tex>1</tex>||<tex>0</tex>||<tex>1</tex>
|-align="center"
!<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>
|<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>
|-align="center"
!<tex>1</tex>||<tex>1</tex>||<tex>\ldots</tex>||<tex>1</tex>
|<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Сохраняет 0]]
|<tex>0</tex>||<tex>1</tex>||<tex>1</tex>
|-align="center"
!colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Сохраняет 1]]
|<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Самодвойственная]]
|<tex>0</tex>||<tex>0</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Монотонная]]
|<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Линейная]]
|<tex>1</tex>||<tex>0</tex>||<tex>1</tex>
|}

На основе этой системы и строятся полиномы Жегалкина.

== Существование и единственность представления (теорема Жегалкина) ==
{{Теорема
|author=Жегалкина
|statement=
Каждая булева функция единственным образом представляется в виде полинома Жегалкина.
|proof=
Заметим, что различных булевых функций от <tex>n</tex> переменных <tex>2^{2^n}</tex> штук. При этом конъюнкций вида <tex>x_{i_1} \ldots x_{i_k}</tex> существует ровно <tex>2^n</tex>, так как из <tex>n</tex> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит <tex>0</tex> или <tex>1</tex>, то есть существует <tex>2^{2^n}</tex> различных полиномов Жегалкина от <tex>n</tex> переменных.

Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.
}}

== Построение полинома Жегалкина ==

Существует несколько способов построения полинома Жегалкина.

=== По таблице истинности ===
Пусть для функции <tex>f(x_1,x_2,\ldots,x_n)</tex> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты с учётом того, что <tex> a \oplus 1 = \bar{a}</tex>, а <tex> a \oplus 0 = a</tex>. За каждую подстановку находим только один коэффициент.

'''Пример:'''
Дана функция <tex>f(x_1,x_2,x_3,x_4)</tex> и её таблица истинности:

{| class="wikitable" style="width:8cm" border="1"
|-
!class="dark" style="font-weight:normal"| <tex>x_1</tex>
!class="dark" style="font-weight:normal"| <tex>x_2</tex>
!class="dark" style="font-weight:normal"| <tex>x_3</tex>
!class="dark" style="font-weight:normal"| <tex>x_4</tex>
!class="dark" style="font-weight:normal"| <tex>f(x_1,x_2,x_3,x_4)</tex>
|- align="center"
||0||0||0||0||0
|- align="center"
||0||0||0||1||0
|- align="center"
||0||0||1||0||0
|- align="center"
||0||0||1||1||0
|- align="center"
||0||1||0||0||0
|- align="center"
||0||1||0||1||0
|- align="center"
||0||1||1||0||1
|- align="center"
||0||1||1||1||0
|- align="center"
||1||0||0||0||1
|- align="center"
||1||0||0||1||0
|- align="center"
||1||0||1||0||0
|- align="center"
||1||0||1||1||1
|- align="center"
||1||1||0||0||1
|- align="center"
||1||1||0||1||0
|- align="center"
||1||1||1||0||1
|- align="center"
||1||1||1||1||0
|}
Построим для неё полином Жегалкина:

<tex>f(x_1,x_2,x_3,x_4) = a_{0000} \oplus a_{1000} x_1 \oplus a_{0100} x_2 \oplus a_{0010} x_3 \oplus a_{0001} x_4 \oplus a_{1100} x_1 x_2 \oplus a_{1010} x_1 x_3 \oplus a_{1001} x_1 x_4 \oplus a_{0110} x_2 x_3 \oplus a_{0101} x_2 x_4 \oplus a_{0011} x_3 x_4 \oplus a_{1110} x_1 x_2 x_3 \oplus a_{1101} x_1 x_2 x_4 \oplus a_{1011} x_1 x_3 x_4 \oplus a_{0111} x_2 x_3 x_4 \oplus a_{1111} x_1 x_2 x_3 x_4</tex>

Так как <tex>f(0,0,0,0) = 0</tex>, то <tex>a_{0000} = 0</tex>.
Далее подставляем все остальные наборы в порядке возрастания числа единиц, подставляя вновь полученные значения в следующие формулы:

<tex>f(1,0,0,0) = a_{0000} \oplus a_{1000} = 1,</tex> следовательно <tex>a_{1000} = 1</tex>

<tex>f(0,1,0,0) = a_{0000} \oplus a_{0100} = 0,</tex> следовательно <tex>a_{0100} = 0</tex>

<tex>f(0,0,1,0) = a_{0000} \oplus a_{0010} = 0,</tex> следовательно <tex> a_{0010} = 0</tex>

<tex>f(0,0,0,1) = a_{0000} \oplus a_{0001} = 0,</tex> следовательно <tex> a_{0001} = 0</tex>

<tex>f(1,1,0,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{1100} = 1,</tex> следовательно <tex> a_{1100} = 0</tex>

<tex>f(1,0,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0010} \oplus a_{1010} = 0, </tex> следовательно <tex> a_{1010} = 1</tex>

<tex>f(1,0,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0001} \oplus a_{1001} = 0, </tex> следовательно <tex> a_{1001} = 1</tex>

<tex>f(0,1,1,0) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0110} = 1, </tex> следовательно <tex> a_{0110} = 1</tex>

<tex>f(0,1,0,1) = a_{0000} \oplus a_{0100} \oplus a_{0001} \oplus a_{0101} = 0, </tex> следовательно <tex> a_{0101} = 0</tex>

<tex>f(0,0,1,1) = a_{0000} \oplus a_{0010} \oplus a_{0001} \oplus a_{0011} = 0, </tex> следовательно <tex> a_{0011} = 0</tex>

<tex>f(1,1,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{1100} \oplus a_{1010} \oplus a_{0110} \oplus a_{1110} = 1, </tex> следовательно <tex> a_{1110} = 0</tex>

<tex>f(1,1,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0001} \oplus a_{1100} \oplus a_{1001} \oplus a_{0101} \oplus a_{1101} = 0, </tex> следовательно <tex> a_{1101} = 0</tex>

<tex>f(1,0,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0010} \oplus a_{0001} \oplus a_{1010} \oplus a_{1001} \oplus a_{0011} \oplus a_{1011} = 1, </tex> следовательно <tex> a_{1011} = 0</tex>

<tex>f(0,1,1,1) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{0111} = 0, </tex> следовательно <tex> a_{0111} = 1</tex>

<tex>f(1,1,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{1100} \oplus a_{1010} \oplus a_{1001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{1110} \oplus a_{1101} \oplus a_{1011} \oplus a_{0111} \oplus a_{1111} = 0, </tex> следовательно <tex> a_{1111} = 1</tex>

Таким образом, полином Жегалкина выглядит так:

<tex>f(x_1,x_2,x_3,x_4) = x_1 \oplus x_1 x_3 \oplus x_1 x_4 \oplus x_2 x_3 \oplus x_2 x_3 x_4 \oplus x_1 x_2 x_3 x_4</tex>

=== Преобразование [[Определение_булевой_функции#Дизъюнктивная нормальная форма (ДНФ)|дизъюнктивной нормальной формы]] ===
Этот способ основан на том, что <tex> X \oplus 1 = \bar{X} </tex>. Если функция задана в виде ДНФ, то можно сначала убрать дизъюнкцию, используя правило де Моргана, а все отрицания заменить прибавлением единицы по модулю два, после чего раскрыть скобки по обычным правилам, при этом учитывая, что четное число одинаковых слагаемых равно нулю (так как <tex> X \oplus X = 0 </tex>), а нечетное число одинаковых слагаемых равно одному такому слагаемому. Либо же можно заменить дизъюнкцию по следующему правилу:
<tex> A \lor B = AB \oplus A \oplus B </tex>   <tex> (1) </tex>.

Если функция задана в СДНФ, то так как при любых значениях входных переменных в единицу обращается не более одного члена выражения, то достаточно просто заменить все дизъюнкции исключающим ИЛИ.

'''Пример:'''
Дана функция в ДНФ <tex> f(x_1,x_2,x_3,x_4) = (x_1 \land x_2 \land \neg x_3 \land x_4) \lor (\neg x_1 \land \neg x_4) \lor (x_1 \land x_2) \lor x_2 </tex>, построим полином Жегалкина.

Запишем функцию так:

<tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 + \neg x_1 \neg x_4 + x_1 x_2 + x_2</tex>;

Сгруппируем слагаемые и воспользуемся преобразованием (1):

<tex>f(x_1,x_2,x_3,x_4) = (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_1 x_2 \neg x_3 x_4 \neg x_1 \neg x_4) + (x_1 x_2 \oplus x_2 \oplus \oplus x_1 x_2 x_2)</tex>

Воспользуемся свойствами конъюнкции <tex>A \land A = A</tex> и <tex>\neg A \land A = 0</tex>, а также тем, что <tex>A \oplus A = 0</tex>, и упростим выражение:

<tex>f(x_1,x_2,x_3,x_4) = (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4) + x_2</tex>

Ещё раз воспользуемся преобразованием (1):

<tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_2 \oplus (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4) x_2</tex>

Раскроем скобку по алгебраическим правилам:

<tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_2 \oplus x_1 x_2 x_2 \neg x_3 x_4 \oplus \neg x_1 x_2 \neg x_4</tex>

Снова воспользуемся свойствами конъюнкции и исключающего ИЛИ:

<tex>f(x_1,x_2,x_3,x_4) = \neg x_1 \neg x_4 \oplus x_2 \oplus \neg x_1 x_2 \neg x_4</tex>

Заменим отрицание на прибавление <tex>1</tex>:

<tex>f(x_1,x_2,x_3,x_4) = (x_1 \oplus 1) (x_4 \oplus 1) \oplus x_2 \oplus (x_1 \oplus 1) x_2 (x_4 \oplus 1)</tex>

Раскроем скобки:

<tex>f(x_1,x_2,x_3,x_4) = x_1 x_4 \oplus x_1 \oplus x_4 \oplus 1 \oplus x_2 \oplus x_1 x_2 x_4 \oplus x_1 x_2 \oplus x_2 x_4 \oplus x_2</tex>

Выкинем парные слагаемые и получим окончательную формулу:

<tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 x_4 \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 \oplus x_4 \oplus 1</tex>

=== Метод треугольника === 
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:
# Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от <tex>000\ldots00</tex> до <tex>111\ldots11</tex>.
# Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
# Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
# Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
# Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке <tex>111</tex> соответствует член <tex>ABC</tex>, ячейке <tex>101</tex> — член <tex>AC</tex>, ячейке <tex>010</tex> — член <tex>B</tex>, ячейке <tex>000</tex> — член <tex>1</tex> и т.д.
# Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.

Фактически, этот метод является модификацией метода построения по таблице истинности, описанного выше. По сравнению с ним он удобнее тем, что расчёты занимают мало места и в них сложнее ошибиться, но метод треугольника требует бо́льшего количества операций.

Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных <tex>P(A,B,C)</tex> показан на рисунке.

[[Файл:Преобразование таблицы истинности в полином Жегалкина методом треугольника.gif]]

Чтобы получить формулу, по которой рассчитывается какой-либо коэффициент, нужно из клетки, в которой он записан, пройтись всеми возможными путями влево, до столбца <tex>''P''</tex> таблицы истинности, делая ходы влево и влево-вниз, записать значения в конечных ячейках и сложить их все между собой по модулю 2.

Таким образом, в первом столбце сверху записан коэффициент <tex> a_0 = P(0,0,0) </tex>,

во втором — <tex> a_1 = P(0,0,0) \oplus P(0,0,1) </tex>,

в третьем — <tex> a_2 = P(0,0,0) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,1,0) = P(0,0,0) \oplus P(0,1,0) </tex>,

в четвёртом —

<tex> a_3 = P(0,0,0) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,1) = P(0,0,0) \oplus P(0,1,0) \oplus P(0,0,1) \oplus P(0,1,1), </tex>

и так далее, то есть при построении вспомогательной таблицы коэффициенты полинома просчитываются автоматически.

=== Преобразование Мёбиуса ===
Пусть задана [[Определение булевой функции|булева функция]] <tex>f: B^n \rightarrow B, \;\; B=\{ 0; 1 \}</tex>.
Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.

Пусть <tex> i = (i_1, i_2, \ldots i_n), \;\; i_k \in \{0 ; 1\}</tex>, и введем обозначение <tex> x ^{i_k} \sim \left\{\begin{matrix} x, \;\; i_k=1
\\ 1, \;\; i_k=0
\end{matrix}\right. </tex>

Тогда полином Жегалкина можно записать как:
<tex> f(x) = \bigoplus\limits_i \alpha_i \cdot x_1^{i_1} \cdot x_2^{i_2} \cdot</tex> <tex>\ldots</tex> <tex>\cdot x_n^{i_n}</tex>, где <tex>\alpha_i \in \{ 0; 1 \}</tex>.

Множество коэффициентов <tex>\{\alpha _i\}</tex> можно рассматривать как функцию <tex>\alpha</tex>, заданной на множестве индексов <tex> i = (i_1, i_2, \ldots i_n)</tex>, то есть <tex>\alpha: i \mapsto \alpha_i</tex>.

Очевидно, функцию <tex> f </tex> можно записать и следующим образом: <tex> f(x) = \bigoplus \limits_i \alpha_i \cdot [x_1 , \; </tex> если <tex> \;\; i_1] \cdot [x_2 , \; </tex> если <tex> \;\; i_2] \cdot</tex> <tex>\ldots</tex> <tex>\cdot [x_n , \; </tex> если <tex> \;\; i_n]</tex>.

Тут запись <tex>[x_k , \; </tex> если <tex> \; i_k]</tex> означает, что элелемент <tex> x_k </tex> присутствует в соответствующем члене полинома только если <tex> i_k = 1 </tex>.
Тогда если для какого-то <tex>x</tex>, <tex>i \succ x*</tex> ,то в слагаемом будет существовать хотя бы один множитель, равный нулю, и такое слагаемое на сумму не повлияет.
Отсюда ясно, что <tex> f(x) = \bigoplus \limits_{i \preceq x} \alpha_i </tex>  <tex> (2) </tex>
Найдем отображение <tex> f \mapsto \alpha</tex> (То есть такое, которое по заданной функции вычисляет значения всех коэффициентов).

<tex>*</tex> <tex>i \succ x</tex> обозначает, что <tex>x</tex> "меньше" <tex>i</tex> как последовательность бит

{{Теорема
|statement=Пусть задана функция <tex> f </tex>. Тогда функцию <tex> \alpha_x </tex> можно найти по формуле: <tex>\alpha_x = \bigoplus \limits_{j\preceq x} f(j)</tex>     <tex> (3) </tex>.
||proof=Докажем при помощи индукции по количеству единиц в векторе <tex> x </tex> ( иначе говоря, по сумме <tex>x_1+x_2+</tex><tex>\ldots</tex><tex>+x_n</tex> ) и для удобства обозначим это количество единиц(сумму) <tex> wt(x) </tex>.

'''1)''' База: если <tex> x = 0 </tex>, то, очевидно <tex> f(0) = \alpha_0 </tex>

'''2)''' Пускай теорема справедлива для всех сумм <tex>wt(x) < k</tex>. Покажем, что в таком случае она верна и для <tex>wt(x) = k</tex>. По <tex> (2) </tex>, а далее по предположению индукции видим: <tex> f(x) = \bigoplus \limits_{i \preceq x} \alpha_i = \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq i} f(j) \right ] \oplus \alpha_x</tex> .

Рассмотрим сумму <tex> \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq i} f(j) \right ] </tex>. Каждый элемент <tex> f(j) </tex> содержится в ней, только если <tex> j \prec x </tex>, и для фиксированных <tex> j</tex> и <tex> x </tex> элемент <tex> f(j)</tex> встречается ровно столько раз, сколько существует <tex> i </tex> , таких, что <tex> j \preceq i \prec x</tex>. Несложно увидеть, что таких <tex> i </tex> существует ровно <tex> 2^{wt(x)-wt(j)}-1 </tex>, то есть нечетное количество раз. Тогда <tex> \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq i} f(j) \right ] = \bigoplus \limits_{j\prec x} f(j) </tex>.
Но тогда <tex> f(x) = \left [ \bigoplus \limits_{j\prec x} f(j) \right ] \oplus \alpha_x \Leftrightarrow f(x) \oplus \bigoplus \limits_{j\prec x} f(j) = \alpha_x \Leftrightarrow \alpha_x = \bigoplus \limits_{j\preceq x} f(j)</tex>.
То есть при <tex>wt(x) = k</tex> формула также выполняется, значит при любых <tex> x </tex> выполняется <tex>\alpha_x = \bigoplus \limits_{j\preceq x} f(j)</tex>.

}}
Отображение <tex> f \rightarrow \alpha</tex> также называется преобразованием Мёбиуса.

Видно, что <tex> (2) </tex> и <tex> (3) </tex> — это одно и тоже преобразование. Значит, если применить преобразование Мёбиуса к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию <tex>f</tex>. То есть преобразование Мёбиуса обратно самому себе, иными словами, является инволюцией.

== См. также ==
* [[Определение_булевой_функции|Булевы функции]]
* [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|Полные системы функций, теорема Поста]]
* [[СДНФ|ДНФ]]
* [[СКНФ|КНФ]]

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

* [http://www.stat-mat.com/?p=330 Cтатистика | Математика НГУ]
* [http://ru.wikipedia.org/wiki/Полином_Жегалкина Википедия {{---}} Полином Жегалкина]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская, дискретная математика]
* Логачёв О.А, Сальников А.А., Ященко В.В. Булевы фунции в теории кодирования и криптологии — МЦНМО, 2004. - 470с. — ISBN 5-94057-117-4.

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции]]

Задача о динамической связности оффлайн

2022-09-01T03:57:26Z

185.220.101.2:

Поиск в матрице

2022-09-01T03:57:20Z

185.220.101.2:

Вычисления с оракулом

2022-09-01T03:56:53Z

185.220.101.2:

Матрица инцидентности графа

2022-09-01T03:56:45Z

185.220.101.2:

Задача о числе путей в ациклическом графе

2022-09-01T03:56:40Z

185.220.101.2:

LZSS

2022-09-01T03:56:34Z

185.220.101.2:

Коды Грея

2022-09-01T03:56:14Z

185.220.101.2:

Нахождение количества разбиений числа на слагаемые

2022-09-01T03:56:04Z

185.220.101.2:

CAP теорема

2022-09-01T03:55:51Z

185.220.101.2:

Слабый конъюнктивный предикат

2022-09-01T03:55:40Z

185.220.101.2: