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

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

2017-01-07T15:40:16Z

Max 27: Исправил замечания

{{Шаблон: Задача
|definition =
Даны два массива: <tex> a[1..n] </tex> и <tex> b[1..m] </tex>. Требуется найти их ''наибольшую общую возрастающую подпоследовательность (НОВП).''}}
{{Определение
|definition =
'''Наибольшая общая возрастающая подпоследовательность, НОВП''' (англ. ''longest common increasing subsequence, LCIS'') массива <tex> A </tex> длины <tex> n </tex> и массива <tex> B </tex> длины <tex> m </tex> — это последовательность <tex> X = \left \langle x_1, x_2, \ldots, x_k \right \rangle </tex> такая, что <tex> x_1 < x_2 < \ldots < x_k </tex>, <tex> X </tex> является ''подпоследовательностью'' <tex> A </tex> и <tex> B </tex>. }}

==Решение за время O(n2 × m2)==
Построим следующую динамику: <tex> d[i][j] </tex> {{---}} это длина наибольшей возрастающей подпоследовательности массивов <tex> a </tex> и <tex> b </tex>, последний элемент которой <tex> a[i] </tex> и <tex> b[j] (a[i] = b[j]) </tex>. Будем заполнять <tex> d[i][j] </tex> сначала по увеличению <tex> i </tex>, а при равенстве по увеличению <tex> j </tex>. Ответом на задачу будет максимум из всех элементов <tex> d[i][j] </tex> (где <tex> i = 1...n </tex>, <tex> j = 1...m. </tex>)

Заполнять <tex> d </tex> будем следующим образом: на очередном шаге сравниваем элементы <tex> a[i] </tex> и <tex> b[j] </tex>:
*Если <tex> a[i] \neq b[j] </tex>, то <tex> d[i][j] = 0 </tex> (так как нет НОВП, оканчивающейся в разных элементах).
*Если <tex> a[i] = b[j] </tex>, то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах <tex> a </tex> и <tex> b </tex>. Заметим, что предыдущие значения <tex> d </tex> уже известны, тогда очередное значение <tex dpi="130"> d[i][j] = \max\limits_{k = 1..i-1 \atop l = 1..j-1} d[k][l] + 1 </tex> при условии, что <tex> a[k] = b[l]. </tex>

Длина НОВП будет в элементе с максимальным значением <tex> d[i][j] </tex>. Для восстановления подпоследовательности можно хранить массив предков <tex> prev[1..n] </tex> массива <tex> a: prev[i] </tex> {{---}} индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>.

'''vector<int>''' LCIS(a: '''int[n]''', b: '''int[m]''')
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' m
'''if''' a[i] == b[j]
d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j] 
'''for''' k = 1 '''to''' i - 1
'''for''' l = 1 '''to''' j - 1
'''if''' a[k] == b[l] '''and''' a[k] < a[i] '''and''' d[i][j] < d[k][l] + 1
d[i][j] = d[k][l] + 1
prev[i] = k
// восстановление
b_i = 1
b_j = 1
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' m
'''if''' d[b_i][b_j] < d[i][j]
b_i = i
b_j = j
pos = b_i
// проходим по массиву a, выписывая элементы НОВП
answer: '''vector<int>'''
'''while''' pos <tex> \neq </tex> 0
answer.pushBack(a[pos])
pos = prev[pos]
'''return''' answer

==Решение за время O(n2 × m)==
Улучшим предыдущее решение. Пусть теперь <tex> d[i][j] </tex> {{---}} динамика, в которой элемент <tex> a[i] </tex> по-прежнему последний представитель НОВП массива <tex> a </tex>, а <tex> b[j] </tex> может не быть быть последним представителем массива <tex> b </tex>:
*Если <tex> a[i] \neq b[j] </tex>, будем "протаскивать" последнее удачное сравнение в динамике: <tex> d[i][j] = d[i][j-1] </tex> (понять это можно так: <tex> a[i] \neq b[j] </tex> , поэтому <tex> b[j] </tex> не последний представитель НОВП из массива <tex> b </tex>, а значит предыдущий элемент НОВП находится в префиксе <tex> b[1..j-1] </tex>, но <tex> d[i][j-1] </tex> уже посчитан).
*Если <tex> a[i] = b[j] </tex>, то одним дополнительным циклом пробежим по <tex> a </tex> и найдём предыдущий элемент НОВП, оканчивающейся в <tex> a[i] </tex> (он меньше <tex> a[i] </tex>). Из подходящих элементов выберем тот, для которого <tex> d[k][j] </tex> {{---}} максимальна.

<tex dpi="120"> d[i][j] = \max\limits_{k = 1..i-1} d[k][j] + 1 </tex> при условии, что <tex> a[k] < a[i].</tex>

Длина НОВП будет в элементе с максимальным значением <tex> d[i][m] </tex>. Для восстановления ответа будем хранить массив предков по массиву <tex> a </tex>, как и в предыдущем решении.

'''vector<int>''' LCIS(a: '''int[n]''', b: '''int[m]''')
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' m
'''if''' a[i] == b[j]
d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
'''for''' k = 1 '''to''' i - 1
'''if''' a[k] < a[i] '''and''' d[i][j] < d[k][j] + 1
d[i][j] = d[k][j] + 1
prev[i] = k
'''else'''
d[i][j] = d[i][j - 1]
// восстановление
pos = 1 // ищем элемент c максимальным d[pos][m]
'''for''' i = 1 '''to''' n
'''if''' d[pos][m] < d[i][m]
pos = i
// проходим по массиву a, выписывая элементы НОВП
answer: '''vector<int>'''
'''while''' pos <tex> \neq </tex> 0
answer.pushBack(a[pos])
pos = prev[pos]
'''return''' answer

==Решение за время O(n × m)==
Модифицируем предыдущее решение, добавив небольшую ''хитрость''. Теперь <tex> d[i][j] </tex> {{---}} это длина наибольшей общей возрастающей подпоследовательности префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, причем элемент <tex> b[j] </tex> {{---}} последний представитель НОВП массива <tex> b </tex>, а <tex> a[i] </tex> может не быть последним в массиве <tex> a </tex>. Вычислять <tex> d </tex> будем всё так же: сначала по увеличению <tex> i </tex>, а при равенстве {{---}} по увеличению <tex> j </tex>. Тогда для очередного значения <tex> d[i][j] </tex> есть два варианта:
*<tex> a[i] </tex> не входит в НОВП. Тогда <tex> d[i][j] = d[i-1][j] </tex>: значение динамики уже посчитано на префиксе <tex> a[1..i-1] </tex>.
*<tex> a[i] </tex> входит в НОВП. Это значит, что <tex> a[i] = b[j] </tex>, то есть для подсчёта <tex> d[i][j] </tex> нужно пробегать циклом по <tex> b </tex> в поисках элемента <tex> b[k] < b[j] </tex> с наибольшим значением <tex> d[i-1][k] </tex>. Но мы считаем <tex> d </tex> сначала по увеличению <tex> i </tex>, поэтому будем считать <tex> a[i] </tex> ''фиксированным''. Чтобы не запускать цикл при каждом равенстве <tex> a[i] </tex> элементу <tex> b[k] </tex>, в дополнительной переменной <tex> best </tex> будем хранить "лучший" элемент (и его индекс <tex> ind </tex> в массиве <tex> b </tex>) такой, что этот элемент строго меньше <tex> a[i] </tex> (а также меньше <tex> b[k] </tex>) и значение динамики для него максимально: <tex> b[ind] < a[i] = b[k] </tex> и <tex> best = d[i-1][ind] \rightarrow max. </tex>

'''vector<int>''' LCIS(a: '''int[n]''', b: '''int[m]''')
'''for''' i = 1 '''to''' n
ind = 0 // позиция "лучшего" элемента в массиве b
best = 0 // значение динамики для "лучшего" элемента
'''for''' j = 1 '''to''' m
d[i][j] = d[i - 1][j] // НОВП на a[1..i - 1] и b[1..j] (без элемента a[i])
'''if''' a[i] == b[j] '''and''' d[i - 1][j] < best + 1 // используем a[i]-й элемент для увеличения НОВП
d[i][j] = best + 1
prev[j] = ind
'''if''' a[i] > b[j] '''and''' d[i - 1][j] > best // при следующем равенстве a[i] == b[j']
best = d[i - 1][j] // в best будет храниться "лучший" элемент
ind = j // b[ind] < b[j'] и d[i][ind] <tex> \rightarrow </tex> max
// восстановление (по массиву b)
pos = 1 // ищем лучший элемент d[n][pos] <tex> \rightarrow </tex> max
'''for''' j = 1 '''to''' m
'''if''' d[n][pos] < d[n][j]
pos = j
// проходим по массиву b, выписывая элементы НОВП
answer: '''vector<int>'''
'''while''' pos <tex> \neq </tex> 0
answer.pushBack(b[pos])
pos = prev[pos]
'''return''' answer

=== Доказательство оптимальности ===
В данной задаче используется принцип оптимальности на префиксе. Использование дополнительной переменной для подсчета всех случаев <tex> a[i] = b[j] </tex> не влияет на корректность алгоритма {{---}} это всего лишь уловки реализации. Поэтому покажем, что для вычисления очередного значения <tex> d[i][j] </tex> мы используем оптимальность на подзадачах и обращаемся к уже посчитанным значениям.
Напомним, как обозначается динамика: <tex> d[i][j] </tex> {{---}} это НОВП на префиксах <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, где последним элементом НОВП является элемент <tex> b[j] </tex>, а <tex> a[i] </tex> может не быть равен <tex> b[j] </tex> (то есть элемент <tex> a[i'] = b[j] </tex> лежит где-то в префиксе <tex> a[1..i] </tex>). Итак, для <tex> d[i][j] </tex> есть два варианта:
* <tex> a[i] \neq b[j] </tex>, тогда <tex> a[i] </tex> не влияет на результат, и последний элемент НОВП <tex> a[i'] = b[j] </tex> лежит в <tex> a[1..i-1] </tex>.
* <tex> a[i] = b[j] </tex>, тогда <tex> a[i] </tex> и <tex> b[j] </tex> {{---}} последние элементы НОВП префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>: <tex> b[j] </tex> {{---}} по определению динамики, а <tex> a[i] </tex> как элемент, который может стать последним, не ухудшая результат. Действительно, последовательность строго возрастает, поэтому если в префиксе <tex> a[1..i-1] </tex> есть элемент <tex> a[k] = b[j] </tex>, то его можно заменить на элемент <tex> a[i] </tex> без уменьшения длины НОВП. Если же в <tex> a[1..i-1] </tex> такого элемента нет, то <tex> a[i] </tex> {{---}} единственный из возможных вариантов. Итак, <tex> a[i] </tex> и <tex> b[j] </tex> {{---}} последние элементы НОВП. Значит, начало НОВП (<tex> d[i][j] </tex>) лежит в префиксах <tex> a[1..i-1] </tex> и <tex> b[1..j-1] </tex> (значения для которых уже посчитаны). Мы ищем элемент <tex> b[k] < b[j] </tex> с лучшей динамикой <tex> d[i-1][k] </tex>, что удовлетворяет условию возрастания последовательности и автоматически гарантирует, что конец такой НОВП лежит в префиксе <tex> a[1..i-1] </tex>.

== См. также ==

*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о наибольшей возрастающей подпоследовательности]]

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

* [http://codeforces.ru/contest/10/problem/D Codeforces {{---}} Задача о наибольшей общей возрастающей подпоследовательности]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Другие задачи]]

Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза

2017-01-07T15:09:24Z

Max 27:

{{Определение
| definition =
'''[[Оптимальный префиксный код с длиной кодового слова не более L бит|Оптимальный префиксный код]] с сохранением порядка''' (англ. ''order-preserving code'', ''alphabetic code'').

Пусть у нас есть алфавит <tex> \Sigma </tex>. Каждому символу <tex>c_i </tex> сопоставим его код <tex> p_i </tex>. Кодирование называется оптимальным префиксным с сохранением порядка (алфавитным), если соблюдаются:
# Условие порядка {{---}} <tex> \forall i, j : c_i < c_j \iff p_i < p_j </tex>. То есть, если символ <tex>c_i </tex> лексикографически меньше символа <tex> c_j </tex>, его код также будет [[лексикографический порядок | лексикографически]] меньше, и наоборот.
# Условие оптимальности {{---}} <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> {{---}} минимально, где <tex> f_i </tex> {{---}} частота встречаемости символа <tex> c_i </tex> в тексте, а <tex> |p_i| </tex> {{---}} длина его кода.
}}

__TOC__
== Алгоритм ==
Решим задачу, используя ДП на подотрезках. Пусть в ячейке <tex> D[i][j] </tex> хранится минимальная стоимость кодового дерева для отрезка алфавита от <tex> i </tex> до <tex> j </tex>.

Тогда пересчет <tex> D[i][j] </tex> будет происходить так:

<tex> D[i][j] = \min\limits_{k = i}^{j - 1} \left ( D[i][k] + D[k + 1][j] \right ) + w[i][j]</tex>

Базой динамики будет <tex> D[i][i] = 0 </tex>

Добавочный член <tex>w[i][j] = \sum\limits_{t = i}^{j} f_t </tex> возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на <tex> 1 </tex>, а значит, и длины всех кодов символов <tex> c_i .. c_j </tex> также увеличиваются на <tex> 1 </tex>.

Тогда такое ''наибольшее'' <tex> k </tex>, на котором достигается этот минимум, называется точкой разреза для отрезка <tex> i..j </tex>. Пусть в ячейке <tex> R[i][j] </tex> хранится точка разреза на отрезке <tex> i..j </tex>.

Если разрез происходит по какому-то определенному индексу <tex> q </tex> , такой разрез обозначим <tex> D_q[i][j] </tex>.

Таким образом, получили алгоритм, работающий за <tex> O(n^3) </tex>. Коды каждого символа можно легко получить так же, как в алгоритме Хаффмана {{---}} обходом по построенному дереву.

Если доказать монотонность точки разреза, то можно уменьшить асимптотику алгоритма до <tex> O(n^2) </tex>.

== Монотонность точки разреза ==
Для доказательства этого сперва докажем несколько лемм.

{{Определение
| definition=
Функция <tex> a </tex> удовлетворяет '''неравенству четырехугольника''' (англ. ''quadrangle inequation''), если
: <tex>\forall i \leqslant i' \leqslant j \leqslant j' : a[i][j] + a[i'][j'] \leqslant a[i'][j] + a[i][j']</tex>.
}}

{{Лемма
| statement=
<tex> w </tex> удовлетворяет неравенству четырехугольника.
| proof=
Заметим, что <tex> w[i][j] = w[i][t] + w[t+1][j] </tex>, так как <tex> w[i][j] </tex> {{---}} простая арифметическая сумма. Тогда:
: <tex> w[i][j] + w[i'][j'] \leqslant w[i'][j] + w[i][j']</tex>
: <tex> (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \leqslant (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) </tex>
Получили <tex> 0 \leqslant 0 </tex>.
}}

{{Лемма
| statement=
Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то <tex> D </tex> также удовлетворяет неравенству четырехугольника, то есть:

<tex>\forall i \leqslant i' \leqslant j \leqslant j' : D[i][j] + D[i'][j'] \leqslant D[i'][j] + D[i][j'] </tex>.
| proof=
При <tex> i = i' </tex> или <tex> j = j' </tex>, очевидно, неравенство выполняется.

Рассмотрим два случая:
# <tex> i' = j </tex>
#: <tex> i < i' = j < j' </tex>. Тогда неравенство четырехугольника сводится к:
#: <tex> D[i][j] + D[j][j'] \leqslant D[i][j'] </tex>
#: Пусть <tex> k = R[i][j'] </tex>. Получили два симметричных случая:
## <tex> k \leqslant j </tex>
##: <tex> D[i][j] + D[j][j'] \leqslant w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{---}} по определению <tex> D[i][j] </tex>
##: <tex> \leqslant w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{---}} так как <tex> w[i][j'] \geqslant w[i][j] </tex>
##: <tex> \leqslant w[i][j'] + D[i][k-1] + D[k][j'] </tex> {{---}} по индукционному предположению для <tex> D </tex>
##: <tex> \leqslant D[i][j'] </tex> {{---}} по определению <tex> D[i][j'] </tex>
## <tex> k \geqslant j </tex> {{---}} аналогичный предыдущему случай.
# <tex> i' < j </tex>
#: <tex> i < i' < j < j' </tex>
#: Пусть <tex> y = R[i'][j] </tex> и <tex> z = R[i][j'] </tex>. Получили два симметричных случая:
## <tex> z \leqslant y </tex>
##: Получили <tex> i \leqslant z \leqslant y \leqslant j </tex>. Запишем:
##: <tex> D[i'][j'] + D[i][j] \leqslant D_y[i'][j'] + D_z[i][j] = w[i'][j'] + D[i'][y-1] + D[y][j'] + w[i][j] + D[i][z-1] + D[z][j] </tex>
##: <tex> \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] </tex> {{---}} по неравенству четырехугольника для <tex> w </tex>
##: <tex> \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] </tex> {{---}} по индукционному предположению для <tex> D </tex>
##: <tex> \leqslant D[i][j'] + D[i'][j] </tex> {{---}} по определению <tex> D </tex>
## <tex> z \geqslant y </tex> доказывается аналогично.
}}

{{Теорема
| about=
Монотонность точки разреза
| statement=
Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то:

<tex> \forall i \leqslant j : R[i][j] \leqslant R[i][j+1] \leqslant R[i+1][j+1] </tex>.
| proof=
В случае <tex> i = j </tex> неравенство, очевидно, выполняется. Рассматриваем случай <tex> i < j </tex> и только случай <tex> R[i][j] \leqslant R[i][j+1] </tex> (вторая часть доказывается аналогично):

Так как <tex> R[i][j] </tex> {{---}} максимальный индекс, в котором достигается минимум, достаточно показать, что:
: <tex> \forall i < k \leqslant k' \leqslant j: [D_{k'}[i][j] \leqslant D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \leqslant D_k[i][j+1]] </tex> {{---}} фактически, это означает что если на отрезке <tex> i..j </tex> разрез оптимальнее по <tex> k' </tex>, чем по <tex> k </tex>, то он также будет оптимальнее и на отрезке <tex> i..j+1 </tex>.
Докажем более сильное неравенство:
: <tex> \forall i < k \leqslant k' \leqslant j: D_k[i][j] - D_{k'}[i][j] \leqslant D_k[i][j+1] - D_{k'}[i][j+1] </tex>

: <tex> D_k[i][j] + D_{k'}[i][j+1] \leqslant D_k[i][j+1] + D_{k'}[i][j] </tex>

: <tex> (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \leqslant (w[i][j+1] + D[i][k-1] + D[k][j+1]) + (w[i][j] + D[i][k'-1] + D[k'][j]) </tex> {{---}} по определению <tex> D </tex>

: <tex> D[k][j] + D[k'][j+1] \leqslant D[k][j+1] + D[k'][j] </tex> {{---}} получили неравенство четырехугольника для <tex> k \leqslant k' \leqslant j \leqslant j+1 </tex>, что является верным из предыдущей леммы.
}}

== Объяснение квадратичной асимптотики ==
Рассмотрим матрицу <tex> R </tex>. Так как отрезки <tex> i..j </tex>, где <tex> i > j </tex> мы не рассматриваем, она будет верхнетреугольной. Вначале она будет заполнена так, что <tex> R[i][i] = i </tex> (так как для отрезка, состоящего из одного элемента, он же и является точкой разреза). Далее, для любого элемента <tex> R[i][j] </tex> его значения лежат между <tex> R[i][j-1] </tex> (левый элемент в матрице) и <tex> R[i+1][j] </tex> (нижний элемент в матрице). Так как мы используем динамику по подотрезкам, то сначала мы рассчитаем <tex> R </tex> для отрезков длины <tex> 2 </tex>, затем <tex> 3 </tex>, и так далее до <tex> n </tex>. Фактически, мы будем обходить диагонали матрицы, количество которых равно <tex> n </tex>.

Рассмотрим элемент <tex> R[i][j] </tex>. Для него выполняется <tex> R[i][j-1] \leqslant R[i][j] \leqslant R[i+1][j] </tex>. Следующий элемент, который мы будем пересчитывать {{---}} <tex> R[i+1][j+1] </tex>. Для него выполняется <tex> R[i+1][j] \leqslant R[i+1][j+1] \leqslant R[i+2][j+1] </tex>. Таким образом, заполняя одну диагональ, алгоритм сделает не более <tex> n </tex> шагов, а так как диагоналей <tex> n </tex>, получили асимптотику <tex> O(n^2) </tex>.

==Источники информации ==
* [http://www.sciencedirect.com/science/article/pii/S0304397596003209 S.V. Nagaraj {{---}} Tutorial: Optimal binary search trees]
* ''Кнут Д.Э.'' {{---}} Искусство программирования, том 3. Сортировка и поиск. — М.: «Вильямс», 2005, стр. 486 - 488

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Способы оптимизации методов динамического программирования]]

Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза

2017-01-07T15:07:49Z

Max 27: Исправил замечания

{{Определение
| definition =
'''[[Оптимальный префиксный код с длиной кодового слова не более L бит|Оптимальный префиксный код]] с сохранением порядка''' (англ. ''order-preserving code'', ''alphabetic code'').

Пусть у нас есть алфавит <tex> \Sigma </tex>. Каждому символу <tex>c_i </tex> сопоставим его код <tex> p_i </tex>. Кодирование называется оптимальным префиксным с сохранением порядка (алфавитным), если соблюдаются:
# Условие порядка {{---}} <tex> \forall i, j : c_i < c_j \iff p_i < p_j </tex>. То есть, если символ <tex>c_i </tex> лексикографически меньше символа <tex> c_j </tex>, его код также будет [[лексикографический порядок | лексикографически]] меньше, и наоборот.
# Условие оптимальности {{---}} <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> {{---}} минимально, где <tex> f_i </tex> {{---}} частота встречаемости символа <tex> c_i </tex> в тексте, а <tex> |p_i| </tex> {{---}} длина его кода.
}}

__TOC__

== Алгоритм ==
Решим задачу, используя ДП на подотрезках. Пусть в ячейке <tex> D[i][j] </tex> хранится минимальная стоимость кодового дерева для отрезка алфавита от <tex> i </tex> до <tex> j </tex>.

Тогда пересчет <tex> D[i][j] </tex> будет происходить так:

<tex> D[i][j] = \min\limits_{k = i}^{j - 1} \left ( D[i][k] + D[k + 1][j] \right ) + w[i][j]</tex>

Базой динамики будет <tex> D[i][i] = 0 </tex>

Добавочный член <tex>w[i][j] = \sum\limits_{t = i}^{j} f_t </tex> возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на <tex> 1 </tex>, а значит, и длины всех кодов символов <tex> c_i .. c_j </tex> также увеличиваются на <tex> 1 </tex>.

Тогда такое ''наибольшее'' <tex> k </tex>, на котором достигается этот минимум, называется точкой разреза для отрезка <tex> i..j </tex>. Пусть в ячейке <tex> R[i][j] </tex> хранится точка разреза на отрезке <tex> i..j </tex>.

Если разрез происходит по какому-то определенному индексу <tex> q </tex> , такой разрез обозначим <tex> D_q[i][j] </tex>.

Таким образом, получили алгоритм, работающий за <tex> O(n^3) </tex>. Коды каждого символа можно легко получить так же, как в алгоритме Хаффмана {{---}} обходом по построенному дереву.

Если доказать монотонность точки разреза, то можно уменьшить асимптотику алгоритма до <tex> O(n^2) </tex>.

== Монотонность точки разреза ==
Для доказательства этого сперва докажем несколько лемм.

{{Определение
| definition=
Функция <tex> a </tex> удовлетворяет '''неравенству четырехугольника''' (англ. ''quadrangle inequation''), если
: <tex>\forall i \leqslant i' \leqslant j \leqslant j' : a[i][j] + a[i'][j'] \leqslant a[i'][j] + a[i][j']</tex>.
}}

{{Лемма
| statement=
<tex> w </tex> удовлетворяет неравенству четырехугольника.
| proof=
Заметим, что <tex> w[i][j] = w[i][t] + w[t+1][j] </tex>, так как <tex> w[i][j] </tex> {{---}} простая арифметическая сумма. Тогда:
: <tex> w[i][j] + w[i'][j'] \leqslant w[i'][j] + w[i][j']</tex>
: <tex> (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \leqslant (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) </tex>
Получили <tex> 0 \leqslant 0 </tex>.
}}

{{Лемма
| statement=
Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то <tex> D </tex> также удовлетворяет неравенству четырехугольника, то есть:

<tex>\forall i \leqslant i' \leqslant j \leqslant j' : D[i][j] + D[i'][j'] \leqslant D[i'][j] + D[i][j'] </tex>.
| proof=
При <tex> i = i' </tex> или <tex> j = j' </tex>, очевидно, неравенство выполняется.

Рассмотрим два случая:
# <tex> i' = j </tex>
#: <tex> i < i' = j < j' </tex>. Тогда неравенство четырехугольника сводится к:
#: <tex> D[i][j] + D[j][j'] \leqslant D[i][j'] </tex>
#: Пусть <tex> k = R[i][j'] </tex>. Получили два симметричных случая:
## <tex> k \leqslant j </tex>
##: <tex> D[i][j] + D[j][j'] \leqslant w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{---}} по определению <tex> D[i][j] </tex>
##: <tex> \leqslant w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{---}} так как <tex> w[i][j'] \geqslant w[i][j] </tex>
##: <tex> \leqslant w[i][j'] + D[i][k-1] + D[k][j'] </tex> {{---}} по индукционному предположению для <tex> D </tex>
##: <tex> \leqslant D[i][j'] </tex> {{---}} по определению <tex> D[i][j'] </tex>
## <tex> k \geqslant j </tex> {{---}} аналогичный предыдущему случай.
# <tex> i' < j </tex>
#: <tex> i < i' < j < j' </tex>
#: Пусть <tex> y = R[i'][j] </tex> и <tex> z = R[i][j'] </tex>. Получили два симметричных случая:
## <tex> z \leqslant y </tex>
##: Получили <tex> i \leqslant z \leqslant y \leqslant j </tex>. Запишем:
##: <tex> D[i'][j'] + D[i][j] \leqslant D_y[i'][j'] + D_z[i][j] = w[i'][j'] + D[i'][y-1] + D[y][j'] + w[i][j] + D[i][z-1] + D[z][j] </tex>
##: <tex> \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] </tex> {{---}} по неравенству четырехугольника для <tex> w </tex>
##: <tex> \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] </tex> {{---}} по индукционному предположению для <tex> D </tex>
##: <tex> \leqslant D[i][j'] + D[i'][j] </tex> {{---}} по определению <tex> D </tex>
## <tex> z \geqslant y </tex> доказывается аналогично.
}}

{{Теорема
| about=
Монотонность точки разреза
| statement=
Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то:

<tex> \forall i \leqslant j : R[i][j] \leqslant R[i][j+1] \leqslant R[i+1][j+1] </tex>.
| proof=
В случае <tex> i = j </tex> неравенство, очевидно, выполняется. Рассматриваем случай <tex> i < j </tex> и только случай <tex> R[i][j] \leqslant R[i][j+1] </tex> (вторая часть доказывается аналогично):

Так как <tex> R[i][j] </tex> {{---}} максимальный индекс, в котором достигается минимум, достаточно показать, что:
: <tex> \forall i < k \leqslant k' \leqslant j: [D_{k'}[i][j] \leqslant D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \leqslant D_k[i][j+1]] </tex> {{---}} фактически, это означает что если на отрезке <tex> i..j </tex> разрез оптимальнее по <tex> k' </tex>, чем по <tex> k </tex>, то он также будет оптимальнее и на отрезке <tex> i..j+1 </tex>.
Докажем более сильное неравенство:
: <tex> \forall i < k \leqslant k' \leqslant j: D_k[i][j] - D_{k'}[i][j] \leqslant D_k[i][j+1] - D_{k'}[i][j+1] </tex>

: <tex> D_k[i][j] + D_{k'}[i][j+1] \leqslant D_k[i][j+1] + D_{k'}[i][j] </tex>

: <tex> (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \leqslant (w[i][j+1] + D[i][k-1] + D[k][j+1]) + (w[i][j] + D[i][k'-1] + D[k'][j]) </tex> {{---}} по определению <tex> D </tex>

: <tex> D[k][j] + D[k'][j+1] \leqslant D[k][j+1] + D[k'][j] </tex> {{---}} получили неравенство четырехугольника для <tex> k \leqslant k' \leqslant j \leqslant j+1 </tex>, что является верным из предыдущей леммы.
}}

== Объяснение квадратичной асимптотики ==
Рассмотрим матрицу <tex> R </tex>. Так как отрезки <tex> i..j </tex>, где <tex> i > j </tex> мы не рассматриваем, она будет верхнетреугольной. Вначале она будет заполнена так, что <tex> R[i][i] = i </tex> (так как для отрезка, состоящего из одного элемента, он же и является точкой разреза). Далее, для любого элемента <tex> R[i][j] </tex> его значения лежат между <tex> R[i][j-1] </tex> (левый элемент в матрице) и <tex> R[i+1][j] </tex> (нижний элемент в матрице). Так как мы используем динамику по подотрезкам, то сначала мы рассчитаем <tex> R </tex> для отрезков длины <tex> 2 </tex>, затем <tex> 3 </tex>, и так далее до <tex> n </tex>. Фактически, мы будем обходить диагонали матрицы, количество которых равно <tex> n </tex>.

Рассмотрим элемент <tex> R[i][j] </tex>. Для него выполняется <tex> R[i][j-1] \leqslant R[i][j] \leqslant R[i+1][j] </tex>. Следующий элемент, который мы будем пересчитывать {{---}} <tex> R[i+1][j+1] </tex>. Для него выполняется <tex> R[i+1][j] \leqslant R[i+1][j+1] \leqslant R[i+2][j+1] </tex>. Таким образом, заполняя одну диагональ, алгоритм сделает не более <tex> n </tex> шагов, а так как диагоналей <tex> n </tex>, получили асимптотику <tex> O(n^2) </tex>.

==Источники информации ==
* [http://www.sciencedirect.com/science/article/pii/S0304397596003209 S.V. Nagaraj {{---}} Tutorial: Optimal binary search trees]
* ''Кнут Д.Э.'' {{---}} Искусство программирования, том 3. Сортировка и поиск. — М.: «Вильямс», 2005, стр. 486 - 488

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Способы оптимизации методов динамического программирования]]

Категория:Другие задачи динамического программирования

2017-01-06T17:52:44Z

Max 27: Новая страница: «Категория:Дискретная математика и алгоритмы [[Категория:Динамическое программирован...»

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

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

2017-01-06T17:52:01Z

Max 27:

'''[[Задача о наибольшей общей подпоследовательности]]''' (англ. ''longest common subsequence (LCS)'') {{---}} классическая и хорошо изученная проблема.

'''[[Задача о наибольшей подпоследовательности-палиндроме]]''' (англ. ''longest palindromic subsequence (LPS)'') {{---}} также хорошо изучена.

Здесь мы рассмотрим задачу, которая объединяет две вышеперечисленные задачи в одну.
{{Определение
|definition = Для последовательности <tex>X</tex>, мы обозначим её подпоследовательность <tex>x_{i}...x_{j}\ (1 \leqslant i \leqslant j \leqslant n)\ </tex> как <tex>X_{i,j}</tex>. Для двух последовательностей <tex>X</tex> и <tex>Y</tex>, если общая подпоследовательность <tex>Z</tex> последовательностей <tex>X</tex> и <tex>Y</tex> является палиндромом, то <tex>Z</tex> называется '''общей подпалиндромной подпоследовательностью''' (англ. ''common palindromic subsequence''). Общая подпалиндромная последовательность, имеющая максимальную длину, называется '''наибольшей общей подпалиндромной подпоследовательностью''' (англ. ''longest common palindromic subsequence (LCPS)'') и мы обозначим её как <tex>LCPS(X,Y)</tex>.
}}{{Задача
|definition = '''Наибольшая общая подпалиндромная подпоследовательность''' {{---}} задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая также накладывает условия, что эта подпоследовательность должна быть палиндромом.
}}
==Наивное решение==
Можно придумать такое решение данной задачи: найти наибольшую общую подпоследовательность, в ней найти наибольшую подпалиндромную подпоследовательность. Но, к сожалению, это решение '''неверно'''.
===Контрпример===
Возьмем две последовательности <tex>X=[1,\ 2,\ 3,\ 1]</tex> и <tex>Y=[1,\ 1,\ 2,\ 3]</tex>.

Наибольшей общая подпоследовательность данных последовательностей равна <tex>LCS(X,Y) = [1,\ 2,\ 3]</tex> и в ней наибольшая подпалиндромная последовательность имеет длину <tex>1</tex>.

Но очевидно, что на самом деле последовательность <tex>Z=[1,\ 1]</tex> является наибольшим общей палиндромной подпоследовательностью <tex>X</tex> и <tex>Y</tex> и имеет длину <tex>2</tex>.
==Решение с помощью динамического программирования==
Заметим, что в качестве подзадач для <tex>LCPS</tex>, в которых мы можем посчитать ответ, логично взять подпоследовательность от <tex>X</tex> и от <tex>Y</tex>. Основываясь на этом наблюдении мы сформулируем следующую теорему, которая доказывает оптимальную подструктуру свойств задачи <tex>LCPS</tex>, что даст возможность воспользоваться идеей [[Динамическое программирование | динамического программирования]].
{{Теорема
|statement=Пусть <tex>X</tex> и <tex>Y</tex> {{---}} две последовательности длин <tex>n</tex> и <tex>m</tex> соответственно, а <tex>X_{i,j}</tex> и <tex>Y_{k,l}</tex> {{---}} две подпоследовательности последовательностей <tex>X</tex> и <tex>Y</tex> соответственно. Пусть <tex>Z = z_{1}z_{2}...z_{u}</tex> {{---}} наибольшая общая подпалиндромная последовательность двух подпоследовательностей <tex>X_{i,j}</tex> и <tex>Y_{k,l}</tex>. Тогда выполняются следующие утверждения,

# Если <tex>x_i=x_j=y_k=y_l=a</tex> (для произвольного <tex>a</tex>), тогда <tex>z_1=z_u=a</tex> и <tex>Z_{2, u-1}</tex> {{---}} НОПП от подпоследовательностей <tex>X_{i+1,j-1}</tex> и <tex>Y_{k+1,l-1}</tex>.
# Если <tex>x_i=x_j=y_k=y_l</tex> не выполняется, то <tex>Z</tex> {{---}} НОПП от подпоследовательностей (<tex>X_{i+1,j}</tex> и <tex>Y_{k,l}</tex>) или (<tex>X_{i,j-1}</tex> и <tex>Y_{k,l}</tex>) или (<tex>X_{i,j}</tex> и <tex>Y_{k+1,l}</tex>) или (<tex>X_{i,j}</tex> и <tex>Y_{k,l-1}</tex>).
}}
На основании теоремы мы напишем следующую рекурсивную формулу для длины наибольшей общей подпалиндромной подпоследовательности:

<tex>
lcps[i,j,k,l] = \left\{\begin{array}{llcl}
0&&;&i > j\ \lor\ k > l\\
1&&;&(i = j)\ \land\ (k = l)\ \land\ (x_i=x_j=y_k=y_l)\\
2+lcps[i+1,j-1,k+1,l-1]&&;&(i < j)\ \land\ (k < l)\ \land\ (x_i=x_j=y_k=y_l)\\
\max{(}lcps[i+1,j,k,l],lcps[i,j-1,k,l],&&;&(i \leqslant j)\ \land\ (k \leqslant l)\ \land\ \lnot(x_i=x_j=y_k=y_l)\\
\:\:\:\:\:\:\:\:\:\:\:lcps[i,j,k+1,l],lcps[i,j,k,l-1])
\end{array}\right.
</tex>

Где <tex>lcps[i,j,k,l]</tex> {{---}} длина наибольшей общей палиндромной подпоследовательности от <tex>X_{i,j}</tex> и <tex>Y_{k,l}</tex>. Длина наибольшей общей палиндромной подпоследовательности от последовательностей <tex>X</tex> и <tex>Y</tex> будет расположена в <tex>lcps[1,n,1,m]</tex>. Мы можем вычислить эту длину за время <tex>O(n^4)</tex> используя динамическое программирование.

===Реализация===
Будем использовать динамику с запоминанием ответа (с мемоизацией). Оформим решения в виде рекурсивной функции <tex>lcps</tex>, которая возвращает ответ для подзадачи, на которую она была вызвана. В массиве <tex>\mathtt{ans}</tex> хранятся ответы для подзадач. До запуска функции <tex>lcps</tex> заполним массив <tex>ans</tex> значением <tex>-1</tex>. Так как каждое значение считается не более одного раза и эта операция происходит за <tex>O(1)</tex>, мы получим асимптотику <tex>O(n^4)</tex>.

===Псевдокод===
'''int''' lcps(i: '''int''', j: '''int''', k: '''int''', l: '''int''')
'''if''' (ans[i][j][k][l] <tex> \neq </tex> -1) // если значение уже посчитано, то надо его вернуть
'''return''' ans[i][j][k][l]
'''if''' (i > j '''or''' k > l)
ans[i][j][k][l] = 0
'''return''' 0
'''if''' (X[i] == X[j] == Y[k] == Y[l])
'''if''' (i == j '''and''' k == l)
ans[i][j][k][l] = 1
'''return''' 1
'''else'''
ans[i][j][k][l] = (2 + lcps(i + 1, j - 1, k + 1, l - 1))
'''return''' ans[i][j][k][l]
ans[i][j][k][l] = max(lcps(i + 1, j, k, l), lcps(i, j - 1, k, l), lcps(i, j, k + 1, l), lcps(i, j, k, l - 1))
'''return''' ans[i][j][k][l]
==См. также==
* [[Задача о наибольшей возрастающей подпоследовательности]]
* [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
==Источники информации==
* [https://www.academia.edu/2015585/Computing_a_Longest_Common_Palindromic_Subsequence Academia.edu {{---}} Computing a Longest Common Palindromic Subsequence]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Другие задачи]]

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

2017-01-06T17:50:39Z

Max 27: Исправил замечания

{{Шаблон: Задача
|definition =
Даны два массива: <tex> a[1..n] </tex> и <tex> b[1..m] </tex>. Требуется найти их ''наибольшую общую возрастающую подпоследовательность (НОВП).''}}
{{Определение
|definition =
'''Наибольшая общая возрастающая подпоследовательность, НОВП''' (англ. ''longest common increasing subsequence, LCIS'') массива <tex> A </tex> длины <tex> n </tex> и массива <tex> B </tex> длины <tex> m </tex> — это последовательность <tex> X = \left \langle x_1, x_2, \ldots, x_k \right \rangle </tex> такая, что <tex> x_1 < x_2 < \ldots < x_k </tex>, <tex> X </tex> является ''подпоследовательностью'' <tex> A </tex> и <tex> B </tex>. }}

==Решение за время O(N4)==
Построим следующую динамику: <tex> d[i][j] </tex> {{---}} это длина наибольшей возрастающей подпоследовательности массивов <tex> a </tex> и <tex> b </tex>, последний элемент которой <tex> a[i] </tex> и <tex> b[j] (a[i] = b[j]) </tex>. Будем заполнять <tex> d[i][j] </tex> сначала по увеличению <tex> i </tex>, а при равенстве по увеличению <tex> j </tex>. Ответом на задачу будет максимум из всех элементов <tex> d[i][j] </tex> (где <tex> i = 1...n </tex>, <tex> j = 1...m. </tex>)

Заполнять <tex> d </tex> будем следующим образом: на очередном шаге сравниваем элементы <tex> a[i] </tex> и <tex> b[j] </tex>:
*Если <tex> a[i] \neq b[j] </tex>, то <tex> d[i][j] = 0 </tex> (так как нет НОВП, оканчивающейся в разных элементах).
*Если <tex> a[i] = b[j] </tex>, то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах <tex> a </tex> и <tex> b </tex>. Заметим, что предыдущие значения <tex> d </tex> уже известны, тогда очередное значение <tex dpi="130"> d[i][j] = \max\limits_{k = 1..i-1 \atop l = 1..j-1} d[k][l] + 1 </tex> при условии, что <tex> a[k] = b[l]. </tex>

Длина НОВП будет в элементе с максимальным значением <tex> d[i][j] </tex>. Для восстановления подпоследовательности можно хранить массив предков <tex> prev[1..n] </tex> массива <tex> a: prev[i] </tex> {{---}} индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>.

'''int[]''' LCIS(a: '''int[n]''', b: '''int[m]''')
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' m
'''if''' a[i] == b[j]
d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j] 
'''for''' k = 1 '''to''' i - 1
'''for''' l = 1 '''to''' j - 1
'''if''' a[k] == b[l] '''and''' a[k] < a[i] '''and''' d[i][j] < d[k][l] + 1
d[i][j] = d[k][l] + 1
prev[i] = k
// восстановление
b_i = 1
b_j = 1
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' m
'''if''' d[b_i][b_j] < d[i][j]
b_i = i
b_j = j
pos = b_i
// проходим по массиву a, выписывая элементы НОВП
'''while''' pos <tex> \neq </tex> 0
answer.pushBack(a[pos])
pos = prev[pos]
'''return''' answer

==Решение за время O(N3)==
Улучшим предыдущее решение. Пусть теперь <tex> d[i][j] </tex> {{---}} динамика, в которой элемент <tex> a[i] </tex> по-прежнему последний представитель НОВП массива <tex> a </tex>, а <tex> b[j] </tex> может не быть быть последним представителем массива <tex> b </tex>:
*Если <tex> a[i] \neq b[j] </tex>, будем "протаскивать" последнее удачное сравнение в динамике: <tex> d[i][j] = d[i][j-1] </tex> (понять это можно так: <tex> a[i] \neq b[j] </tex> , поэтому <tex> b[j] </tex> не последний представитель НОВП из массива <tex> b </tex>, а значит предыдущий элемент НОВП находится в префиксе <tex> b[1..j-1] </tex>, но <tex> d[i][j-1] </tex> уже посчитан).
*Если <tex> a[i] = b[j] </tex>, то одним дополнительным циклом пробежим по <tex> a </tex> и найдём предыдущий элемент НОВП, оканчивающейся в <tex> a[i] </tex> (он меньше <tex> a[i] </tex>). Из подходящих элементов выберем тот, для которого <tex> d[k][j] </tex> {{---}} максимальна.

<tex dpi="120"> d[i][j] = \max\limits_{k = 1..i-1} d[k][j] + 1 </tex> при условии, что <tex> a[k] < a[i].</tex>

Длина НОВП будет в элементе с максимальным значением <tex> d[i][m] </tex>. Для восстановления ответа будем хранить массив предков по массиву <tex> a </tex>, как и в предыдущем решении.

'''int[]''' LCIS(a: '''int[n]''', b: '''int[m]''')
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' m
'''if''' a[i] == b[j]
d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
'''for''' k = 1 '''to''' i - 1
'''if''' a[k] < a[i] '''and''' d[i][j] < d[k][j] + 1
d[i][j] = d[k][j] + 1
prev[i] = k
'''else'''
d[i][j] = d[i][j - 1]
// восстановление
pos = 1 // ищем элемент c максимальным d[pos][m]
'''for''' i = 1 '''to''' n
'''if''' d[pos][m] < d[i][m]
pos = i
// проходим по массиву a, выписывая элементы НОВП
'''while''' pos <tex> \neq </tex> 0
answer.pushBack(a[pos])
pos = prev[pos]
'''return''' answer

==Решение за время O(N2)==
Модифицируем предыдущее решение, добавив небольшую "хитрость". Теперь <tex> d[i][j] </tex> {{---}} это длина наибольшей общей возрастающей подпоследовательности префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, причем элемент <tex> b[j] </tex> {{---}} последний представитель НОВП массива <tex> b </tex>, а <tex> a[i] </tex> может не быть последним в массиве <tex> a </tex>. Вычислять <tex> d </tex> будем всё так же: сначала по увеличению <tex> i </tex>, а при равенстве {{---}} по увеличению <tex> j </tex>. Тогда для очередного значения <tex> d[i][j] </tex> есть два варианта:
*<tex> a[i] </tex> не входит в НОВП. Тогда <tex> d[i][j] = d[i-1][j] </tex>: значение динамики уже посчитано на префиксе <tex> a[1..i-1] </tex>.
*<tex> a[i] </tex> входит в НОВП. Это значит, что <tex> a[i] = b[j] </tex>, то есть для подсчёта <tex> d[i][j] </tex> нужно пробегать циклом по <tex> b </tex> в поисках элемента <tex> b[k] < b[j] </tex> с наибольшим значением <tex> d[i-1][k] </tex>. Но мы считаем <tex> d </tex> сначала по увеличению <tex> i </tex>, поэтому будем считать <tex> a[i] </tex> ''фиксированным''. Чтобы не запускать цикл при каждом равенстве <tex> a[i] </tex> элементу <tex> b[k] </tex>, в дополнительной переменной <tex> best </tex> будем хранить "лучший" элемент (и его индекс <tex> ind </tex> в массиве <tex> b </tex>) такой, что этот элемент строго меньше <tex> a[i] </tex> (а также меньше <tex> b[k] </tex>) и значение динамики для него максимально: <tex> b[ind] < a[i] = b[k] </tex> и <tex> best = d[i-1][ind] \rightarrow max. </tex>

'''int[]''' LCIS(a: '''int[n]''', b: '''int[m]''')
'''for''' i = 1 '''to''' n
ind = 0 // позиция "лучшего" элемента в массиве b
best = 0 // значение динамики для "лучшего" элемента
'''for''' j = 1 '''to''' m
d[i][j] = d[i - 1][j] // НОВП на a[1..i - 1] и b[1..j] (без элемента a[i])
'''if''' a[i] == b[j] '''and''' d[i - 1][j] < best + 1 // используем a[i]-й элемент для увеличения НОВП
d[i][j] = best + 1
prev[j] = ind
'''if''' a[i] > b[j] '''and''' d[i - 1][j] > best // при следующем равенстве a[i] == b[j']
best = d[i - 1][j] // в best будет храниться "лучший" элемент
ind = j // b[ind] < b[j'] и d[i][ind] <tex> \rightarrow </tex> max
// восстановление (по массиву b)
pos = 1 // ищем лучший элемент d[n][pos] <tex> \rightarrow </tex> max
'''for''' j = 1 '''to''' m
'''if''' d[n][pos] < d[n][j]
pos = j
// проходим по массиву b, выписывая элементы НОВП
'''while''' pos <tex> \neq </tex> 0
answer.pushBack(b[pos])
pos = prev[pos]
'''return''' answer

=== Доказательство оптимальности ===
В данной задаче используется принцип оптимальности на префиксе. Использование дополнительной переменной для подсчета всех случаев <tex> a[i] = b[j] </tex> не влияет на корректность алгоритма {{---}} это всего лишь уловки реализации. Поэтому покажем, что для вычисления очередного значения <tex> d[i][j] </tex> мы используем оптимальность на подзадачах и обращаемся к уже посчитанным значениям.
Напомним, как обозначается динамика: <tex> d[i][j] </tex> {{---}} это НОВП на префиксах <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, где последним элементом НОВП является элемент <tex> b[j] </tex>, а <tex> a[i] </tex> может не быть равен <tex> b[j] </tex> (то есть элемент <tex> a[i'] = b[j] </tex> лежит где-то в префиксе <tex> a[1..i] </tex>). Итак, для <tex> d[i][j] </tex> есть два варианта:
* <tex> a[i] \neq b[j] </tex>, тогда <tex> a[i] </tex> не влияет на результат, и последний элемент НОВП <tex> a[i'] = b[j] </tex> лежит в <tex> a[1..i-1] </tex>.
* <tex> a[i] = b[j] </tex>, тогда <tex> a[i] </tex> и <tex> b[j] </tex> {{---}} последние элементы НОВП префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>: <tex> b[j] </tex> {{---}} по определению динамики, а <tex> a[i] </tex> как элемент, который может стать последним, не ухудшая результат. Действительно, последовательность строго возрастает, поэтому если в префиксе <tex> a[1..i-1] </tex> есть элемент <tex> a[k] = b[j] </tex>, то его можно заменить на элемент <tex> a[i] </tex> без уменьшения длины НОВП. Если же в <tex> a[1..i-1] </tex> такого элемента нет, то <tex> a[i] </tex> {{---}} единственный из возможных вариантов. Итак, <tex> a[i] </tex> и <tex> b[j] </tex> {{---}} последние элементы НОВП. Значит, начало НОВП (<tex> d[i][j] </tex>) лежит в префиксах <tex> a[1..i-1] </tex> и <tex> b[1..j-1] </tex> (значения для которых уже посчитаны). Мы ищем элемент <tex> b[k] < b[j] </tex> с лучшей динамикой <tex> d[i-1][k] </tex>, что удовлетворяет условию возрастания последовательности и автоматически гарантирует, что конец такой НОВП лежит в префиксе <tex> a[1..i-1] </tex>.

== См. также ==

*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о наибольшей возрастающей подпоследовательности]]

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

* [http://codeforces.ru/contest/10/problem/D Codeforces {{---}} Задача о наибольшей общей возрастающей подпоследовательности]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Другие задачи]]

Категория:Способы оптимизации методов динамического программирования

2017-01-06T17:29:45Z

Max 27: Новая страница: «Категория: Дискретная математика и алгоритмы [[Категория:Динамическое программирован...»

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

Применение метода четырёх русских в задачах ДП на примере задачи о НОП

2017-01-06T17:27:26Z

Max 27:

== Описание алгоритма ==

=== Предподсчёт ===
Рассмотрим [[Задача о наибольшей общей подпоследовательности|задачу о наибольшей общей подпоследовательности]] для двух последовательностей одинаковой длины. Тогда таблица динамического программирования имеет размер <tex> (n + 1) \times (n + 1) </tex>. Разобьём её на квадраты размера <tex> k \times k </tex> следующим образом: выделим каждую <tex> k + 1 </tex>-ую строчку, начиная с первой. Аналогично выделяем столбцы.

Требуется, чтобы <tex> k </tex> делило <tex> n </tex>, но это не является ограничением - можно дописать в конец последовательностей символы, которые не встречались в других местах этих последовательностей (символы для каждой последовательности должны быть разными). Тогда ответ на задачу не изменится, а длину можно «довести» до делителя <tex> k </tex>.

Сделаем предподсчёт действия каждого возможного квадрата. Окончательный результат зависит только от значений в верхнем левом «уголке» над квадратом и подстрок, для которых считается ответ — остальные значения в квадрате однозначно считаются с их помощью. Окончательным результатом будут значения в нижнем правом «уголке» квадрата.

Может показаться, что таких уголков может быть много. Но, так как соседние числа в матрице отличаются не более, чем на один, то результат зависит только от константы в верхнем левом элементе матрицы, и возрастания чисел в верхнем и левом крае квадрата. Возрастание чисел будем хранить с помощью битовых масок: сначала <tex> k - 1 </tex> бит кодирует возрастание чисел в верхнем крае квадрата (0 - элемент равен предыдущему, 1 - больше предыдущего на один), потом <tex> k - 1 </tex> бит кодируют возрастание чисел в квадрате по левому краю аналогичным образом.

Более того, константу в верхнем левом элементе квадрата можно вообще не хранить: её можно прибавить при необходимости к каждому элементу результата.

Посчитаем эти квадраты для строк abbabb и bababb. Возьмём <tex> k = 3 </tex>. Тогда предподсчитанные квадраты, которые понадобятся для дальнейшего вычисления НОП, выглядят так:

[[Файл:4 russians lcs precalc.png]]

=== Вычисление НОП на сжатой матрице ===
Ответ для самой задачи НОП считается аналогично обычному алгоритму, только рассматривая не каждую ячейку таблицы, а квадраты <tex> k \times k </tex>. В очередной квадрат (пусть его левый верхний угол находится в ячейке с координатами <tex> i, j </tex>) вставляем значения предподсчитанного квадрата, соответствующего данным подстрокам и битовым маскам, и прибавляем ко всем элементам в квадрате число, стоящее в уголке над квадратом, т.е. в ячейке с координатами <tex> i - 1, j - 1 </tex>.

Для нашего примера итоговая таблица выглядит так:

[[Файл:4 russians lcs table.png]]

== Анализ алгоритма ==

=== Время работы ===
При предподсчёте перебирается <tex> | \Sigma | ^k </tex> (где <tex> | \Sigma | </tex> — мощность алфавита) возможных подстрок первой строки и столько же — второй строки. Для каждой возможной подстроки обеих строк перебирается по <tex> 2^{k - 1} </tex> битовых масок. Для самого предподсчёта требуется время <tex> O(k^2) </tex>. Дальнейший алгоритм поиска НОП требует <tex> O \left ( \frac{n^2}{k^2} \right ) </tex>. Тогда суммарное время работы алгоритма составляет <tex> O \left ( |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k^2 + \frac{n^2}{k^2} \right ) </tex>.
Понятно, что для получения выигрыша в производительности по сравнению с обычным алгоритмом необходимо, чтобы первое слагаемое не превышало второе. Найдём <tex> k </tex>, решив неравенство:

<tex> |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k^2 \leqslant \frac{n^2}{k^2} </tex>

<tex> \left ( 2 | \Sigma | \right ) ^{2k} \cdot \frac{1}{4} \cdot k^4 \leqslant n^2 </tex>

<tex> \left ( 2 | \Sigma | \right ) ^k \cdot k^2 \leqslant 2n </tex>.

<tex> k \log {2 | \Sigma |} + 2 \log k \leqslant \log 2 + \log n </tex>.

Пренебрегая <tex> \log k </tex> и <tex> \log 2 </tex> как <tex> o(k) </tex>, получаем <tex> k \leqslant \frac{\log n}{1 + \log | \Sigma |}</tex>

=== Используемая память ===
Для каждого предподсчитанного квадрата хранятся подстроки длиной <tex> 2k </tex>, битовые маски длиной <tex> 2k </tex> и результат — нижний «уголок» длины <tex> 2k - 1 </tex>. Как уже было подсчитано, всего предподсчитывается <tex> |\Sigma| ^{2k} \cdot 2^{2k - 2} </tex> квадратов. Дальнейший алгоритм требует <tex> O \left ( \frac{n^2}{k^2} \right ) </tex>, значит, всего требуется <tex> O \left ( |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot (2k + 2k + 2k - 1) + \frac{n^2}{k^2} \right ) = O \left ( |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k + \frac{n^2}{k^2} \right ) </tex> памяти.

== Источники ==
* http://pages.cpsc.ucalgary.ca/~pmohasse/private-lcs.pdf

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Способы оптимизации методов динамического программирования]]

Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза

2017-01-06T17:21:19Z

Max 27: Исправил замечания

__TOC__
== Определение ==
{{Определение
| definition =
'''[[Оптимальный префиксный код с длиной кодового слова не более L бит|Оптимальный префиксный код]] с сохранением порядка''' (англ. ''order-preserving code'', ''alphabetic code'').

Пусть у нас есть алфавит <tex> \Sigma </tex>. Каждому символу <tex>c_i </tex> сопоставим его код <tex> p_i </tex>. Кодирование называется оптимальным префиксным с сохранением порядка (алфавитным), если соблюдаются:
# Условие порядка {{---}} <tex> \forall i, j : c_i < c_j \iff p_i < p_j </tex>. То есть, если символ <tex>c_i </tex> лексикографически меньше символа <tex> c_j </tex>, его код также будет [[лексикографический порядок | лексикографически]] меньше, и наоборот.
# Условие оптимальности {{---}} <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> {{---}} минимально, где <tex> f_i </tex> {{---}} частота встречаемости символа <tex> c_i </tex> в тексте, а <tex> |p_i| </tex> {{---}} длина его кода.
}}

== Алгоритм ==
Решим задачу, используя ДП на подотрезках. Пусть в ячейке <tex> D[i][j] </tex> хранится минимальная стоимость кодового дерева для отрезка алфавита от <tex> i </tex> до <tex> j </tex>.

Тогда пересчет <tex> D[i][j] </tex> будет происходить так:

<tex> D[i][j] = \min\limits_{k = i}^{j - 1} \left ( D[i][k] + D[k + 1][j] \right ) + w[i][j]</tex>

Базой динамики будет <tex> D[i][i] = 0 </tex>

Добавочный член <tex>w[i][j] = \sum\limits_{t = i}^{j} f_t </tex> возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на 1, а значит, и длины всех кодов символов <tex> c_i .. c_j </tex> также увеличиваются на 1.

Тогда такое ''наибольшее'' <tex> k </tex>, на котором достигается этот минимум, называется точкой разреза для отрезка <tex> i..j </tex>. Пусть в ячейке <tex> R[i][j] </tex> хранится точка разреза на отрезке <tex> i..j </tex>.

Если разрез происходит по какому-то определенному индексу <tex> q </tex> , такой разрез обозначим <tex> D_q[i][j] </tex>.

Таким образом, получили алгоритм, работающий за <tex> O(n^3) </tex>. Коды каждого символа можно легко получить так же, как в алгоритме Хаффмана {{---}} обходом по построенному дереву.

Если доказать монотонность точки разреза, то можно уменьшить асимптотику алгоритма до <tex> O(n^2) </tex>.

== Монотонность точки разреза ==
Для доказательства этого сперва докажем несколько лемм.

{{Определение
| definition=
Функция <tex> a </tex> удовлетворяет '''неравенству четырехугольника''' (англ. ''quadrangle inequation''), если
: <tex>\forall i \leqslant i' \leqslant j \leqslant j' : a[i][j] + a[i'][j'] \leqslant a[i'][j] + a[i][j']</tex>.
}}

{{Лемма
| statement=
<tex> w </tex> удовлетворяет неравенству четырехугольника.
| proof=
Заметим, что <tex> w[i][j] = w[i][t] + w[t+1][j] </tex>, так как <tex> w[i][j] </tex> {{---}} простая арифметическая сумма. Тогда:
: <tex> w[i][j] + w[i'][j'] \leqslant w[i'][j] + w[i][j']</tex>
: <tex> (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \leqslant (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) </tex>
Получили <tex> 0 \leqslant 0 </tex>.
}}

{{Лемма
| statement=
Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то <tex> D </tex> также удовлетворяет неравенству четырехугольника, то есть:

<tex>\forall i \leqslant i' \leqslant j \leqslant j' : D[i][j] + D[i'][j'] \leqslant D[i'][j] + D[i][j'] </tex>.
| proof=
При <tex> i = i' </tex> или <tex> j = j' </tex>, очевидно, неравенство выполняется.

Рассмотрим два случая:
# <tex> i' = j </tex>
#: <tex> i < i' = j < j' </tex>. Тогда неравенство четырехугольника сводится к:
#: <tex> D[i][j] + D[j][j'] \leqslant D[i][j'] </tex>
#: Пусть <tex> k = R[i][j'] </tex>. Получили два симметричных случая:
## <tex> k \leqslant j </tex>
##: <tex> D[i][j] + D[j][j'] \leqslant w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{---}} по определению <tex> D[i][j] </tex>
##: <tex> \leqslant w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{---}} так как <tex> w[i][j'] \geqslant w[i][j] </tex>
##: <tex> \leqslant w[i][j'] + D[i][k-1] + D[k][j'] </tex> {{---}} по индукционному предположению для <tex> D </tex>
##: <tex> \leqslant D[i][j'] </tex> {{---}} по определению <tex> D[i][j'] </tex>
## <tex> k \geqslant j </tex> {{---}} аналогичный предыдущему случай.
# <tex> i' < j </tex>
#: <tex> i < i' < j < j' </tex>
#: Пусть <tex> y = R[i'][j] </tex> и <tex> z = R[i][j'] </tex>. Получили два симметричных случая:
## <tex> z \leqslant y </tex>
##: Получили <tex> i \leqslant z \leqslant y \leqslant j </tex>. Запишем:
##: <tex> D[i'][j'] + D[i][j] \leqslant D_y[i'][j'] + D_z[i][j] = w[i'][j'] + D[i'][y-1] + D[y][j'] + w[i][j] + D[i][z-1] + D[z][j] </tex>
##: <tex> \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] </tex> {{---}} по неравенству четырехугольника для <tex> w </tex>
##: <tex> \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] </tex> {{---}} по индукционному предположению для <tex> D </tex>
##: <tex> \leqslant D[i][j'] + D[i'][j] </tex> {{---}} по определению <tex> D </tex>
## <tex> z \geqslant y </tex> доказывается аналогично.
}}

{{Теорема
| about=
Монотонность точки разреза
| statement=
Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то:

<tex> \forall i \leqslant j : R[i][j] \leqslant R[i][j+1] \leqslant R[i+1][j+1] </tex>.
| proof=
В случае <tex> i = j </tex> неравенство, очевидно, выполняется. Рассматриваем случай <tex> i < j </tex> и только случай <tex> R[i][j] \leqslant R[i][j+1] </tex> (вторая часть доказывается аналогично):

Так как <tex> R[i][j] </tex> {{---}} максимальный индекс, в котором достигается минимум, достаточно показать, что:
: <tex> \forall i < k \leqslant k' \leqslant j: [D_{k'}[i][j] \leqslant D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \leqslant D_k[i][j+1]] </tex> {{---}} фактически, это означает что если на отрезке <tex> i..j </tex> разрез оптимальнее по <tex> k' </tex>, чем по <tex> k </tex>, то он также будет оптимальнее и на отрезке <tex> i..j+1 </tex>.
Докажем более сильное неравенство:
: <tex> \forall i < k \leqslant k' \leqslant j: D_k[i][j] - D_{k'}[i][j] \leqslant D_k[i][j+1] - D_{k'}[i][j+1] </tex>

: <tex> D_k[i][j] + D_{k'}[i][j+1] \leqslant D_k[i][j+1] + D_{k'}[i][j] </tex>

: <tex> (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \leqslant (w[i][j+1] + D[i][k-1] + D[k][j+1]) + (w[i][j] + D[i][k'-1] + D[k'][j]) </tex> {{---}} по определению <tex> D </tex>

: <tex> D[k][j] + D[k'][j+1] \leqslant D[k][j+1] + D[k'][j] </tex> {{---}} получили неравенство четырехугольника для <tex> k \leqslant k' \leqslant j \leqslant j+1 </tex>, что является верным из предыдущей леммы. Теорема доказана.
}}

== Объяснение квадратичной асимптотики ==
Рассмотрим матрицу <tex> R </tex>. Так как отрезки <tex> i..j </tex>, где <tex> i > j </tex> мы не рассматриваем, она будет верхнетреугольной. Вначале она будет заполнена так, что <tex> R[i][i] = i </tex> (так как для отрезка, состоящего из одного элемента, он же и является точкой разреза). Далее, для любого элемента <tex> R[i][j] </tex> его значения лежат между <tex> R[i][j-1] </tex> (левый элемент в матрице) и <tex> R[i+1][j] </tex> (нижний элемент в матрице). Так как мы используем динамику по подотрезкам, то сначала мы рассчитаем <tex> R </tex> для отрезков длины 2, затем 3, и так далее до n. Фактически, мы будем обходить диагонали матрицы, количество которых равно n.

Рассмотрим элемент <tex> R[i][j] </tex>. Для него выполняется <tex> R[i][j-1] \leqslant R[i][j] \leqslant R[i+1][j] </tex>. Следующий элемент, который мы будем пересчитывать {{---}} <tex> R[i+1][j+1] </tex>. Для него выполняется <tex> R[i+1][j] \leqslant R[i+1][j+1] \leqslant R[i+2][j+1] </tex>. Таким образом, заполняя одну диагональ, алгоритм сделает не более n шагов, а так как диагоналей n, получили асимптотику <tex> O(n^2) </tex>.

==Источники информации ==
* [http://www.sciencedirect.com/science/article/pii/S0304397596003209 S.V. Nagaraj {{---}} Tutorial: Optimal binary search trees]
* ''Кнут Д.Э.'' {{---}} Искусство программирования, том 3. Сортировка и поиск. — М.: «Вильямс», 2005.

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Способы оптимизации методов динамического программирования]]

Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП

2017-01-06T17:10:34Z

Max 27: Исправил замечания

{{Определение
|definition=
'''Последовательность''' (англ. ''sequence'') {{---}} это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества.
}}

==Виды последовательностей ==
{{Определение
|definition =
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''неубывающей''''' (англ. ''nondecreasing''), если каждый элемент этой последовательности не превосходит следующего за ним. <tex>\{x_n\}</tex> — '''''неубывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \leqslant x_{n+1}</tex>.
}}

{{Определение
|definition =
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''невозрастающей''''' (англ. ''nonincreasing''), если каждый следующий элемент этой последовательности не превосходит предыдущего. <tex>\{x_n\}</tex> — '''''невозрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \geqslant x_{n+1}</tex>.
}}

{{Определение
|definition =
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''возрастающей''''' (англ. ''increasing''), если каждый следующий элемент этой последовательности превышает предыдущий. <tex>\{x_n\}</tex> — '''''возрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n < x_{n+1}</tex>.
}}

{{Определение
|definition =
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''убывающей''''' (англ. ''decreasing''), если каждый элемент этой последовательности превышает следующий за ним. <tex>\{x_n\}</tex> — '''''убывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n > x_{n+1}</tex>.
}}

{{Определение
|definition =
Последовательность называется '''монотонной''' (англ. ''monotonic''), если она является неубывающей, либо невозрастающей.
}}

{{Определение
|definition =
Последовательность называется '''строго монотонной''' (англ. ''strictly monotonic''), если она является возрастающей, либо убывающей.
}}

Очевидно, что строго монотонная последовательность является монотонной.

== Теорема о связи длины НВП и НУП ==

{{
Теорема
|author=
|about=
|statement=
Пусть <tex>a</tex> {{---}} перестановка чисел длины <tex>n, l</tex> {{---}} длина наибольшей возрастающей подпоследовательности ([[Задача о наибольшей возрастающей подпоследовательности|НВП]]), <tex>k</tex> {{---}} длина наибольшей убывающей подпоследовательности (НУП). Тогда <tex>l k \geqslant n</tex>.

|proof=
Рассмотрим два массива длины <tex>n : S </tex> и <tex> T </tex>, где <tex> S_i </tex> {{---}} длина НВП, которая заканчивается на <tex>a_i</tex>, <tex> T_i </tex> {{---}} длина НУП, которая начинается на <tex>a_i</tex>.

Докажем, что все пары <tex>(S_i, T_i)</tex> различны.
Пусть существуют такие <tex>i < j</tex> , что <tex> S_i </tex> = <tex> S_j </tex> и <tex> T_i </tex> = <tex> T_j</tex>. Если <tex>a_i < a_j</tex>, тогда <tex> a_j </tex> можно добавить к НВП, заканчивающейся на <tex> a_i </tex>, следовательно <tex>S_j \geqslant S_i + 1</tex>. Если <tex>a_i > a_j</tex>, то по аналогии <tex>T_i \geqslant T_j + 1</tex>. Противоречие! Следовательно все такие пары различны.

Заметим что <tex>1 \leqslant S_i \leqslant l, 1 \leqslant T_i \leqslant k</tex>, поэтому существуют <tex>l k</tex> различных пар <tex> (S_i, T_i) </tex>. Если <tex>l k < n</tex> тогда среди <tex> n </tex> пар найдутся две одинаковые. Такого быть не может по доказанному выше, т. е. <tex>l k \geqslant n</tex>, ч. т. д.
}}

== Следствие из теоремы ==

{{Утверждение
|statement=
Пусть <tex>n</tex> {{---}} длина последовательности, тогда длина наибольшей монотонной подпоследовательности не меньше <tex>\sqrt{n}</tex>.
}}

== Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C#.D0.9D.D0.B5.D0.BA.D0.BE.D1.82.D0.BE.D1.80.D1.8B.D0.B5_.D0.B2.D0.B8.D0.B4.D1.8B_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B5.D0.B9 Википедия {{---}} Последовательность]

*[http://en.wikipedia.org/wiki/Longest_increasing_subsequence Wikipedia {{---}} Longest increasing subsequence]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Свойства комбинаторных объектов]]

ДНФ

2017-01-06T16:43:46Z

Max 27: Исправил замечания

== ДНФ ==
{{Определение
|definition =
'''Простой конъюнкцией''' (англ. ''inclusive conjunction'') или '''конъюнктом''' (англ. ''conjunct'') называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
}}
Простая конъюнкция
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно <tex> 1 </tex> раз;
* '''монотонная''', если она не содержит отрицаний переменных.

{{Определение
|definition =
'''Дизъюнктивная нормальная форма, ДНФ''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов.
}}
Пример ДНФ:
<tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>.

== СДНФ ==
{{Определение
|definition =
'''Совершенная дизъюнктивная нормальная форма, СДНФ''' (англ. ''perfect disjunctive normal form, PDNF'') — это ДНФ, удовлетворяющая условиям:
* в ней нет одинаковых простых конъюнкций,
* каждая простая конъюнкция полная.
}}
Пример СДНФ:
<tex>f(x,y,z) = (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>.

{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec {x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая.
|proof =
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона''':

<tex>f(\vec{x}) = \neg x_i \wedge f(x_1, \dots ,x_{i-1},0,x_{i+1}, \dots ,x_n) \vee
x_i \wedge f(x_1, \dots ,x_{i-1},1,x_{i+1}, \dots ,x_n)</tex>.

Данное соотношение легко проверить подстановкой возможных значений <tex>x_i</tex> (<tex>0</tex> и <tex>1</tex>). Эта формула позволяет выносить <tex>x_i</tex> за знак функции. Последовательно вынося <tex>x_1</tex>, <tex>x_2</tex>,.., <tex>x_n</tex> за знак <tex>f(\vec{x})</tex>, получаем следующую формулу:
<tex> f(\vec{x}) = \neg x_1 \wedge \neg x_2 \wedge ...\wedge \neg x_{n-1} \wedge \neg x_n \wedge f(0,0,...,0,0)~\vee~</tex>

<tex>\neg x_1 \wedge \neg x_2 \wedge ... \wedge \neg x_{n-1} \wedge x_n \wedge f(0,0,...,0,1) ~\vee~ \\
\dots \\
~\vee~ x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge \neg x_n \wedge f(1,1,...,1,0) ~\vee~\\
x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge x_n \wedge f(1,1,...,1) </tex>

Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от <tex>n</tex> переменных мы имеем <tex>2^n</tex> конъюнктов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений <tex> n </tex> переменных. Если на некотором наборе <tex>f(\vec{x})=0</tex>, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})=1</tex>, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.
}}

== Алгоритм построения СДНФ по таблице истинности ==
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>.
# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
# Все полученные конъюнкции связываем операциями дизъюнкции.

== Пример построения СДНФ для медианы==
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>.

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1
|}

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex> ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || <tex>(\neg {x} \land y \land z)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || <tex>(x \land \neg {y} \land z)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || <tex>(x \land y \land \neg {z})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1 || <tex>(x \land y \land z)</tex>
|}

3. Все полученные конъюнкции связываем операциями дизъюнкции:

<tex> \langle x,y,z \rangle = (x \land y \land z) \lor (\neg {x} \land y \land z) \lor (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>.

==Примеры СДНФ для некоторых функций==
Стрелка Пирса: <tex> x \downarrow y = (\neg {x} \land \neg {y})</tex>.

Исключающее или: <tex> x \oplus y \oplus z = (\overline{x} \land \overline{y} \land z) \lor (\overline{x} \land y \land \overline{z}) \lor (x \land \overline{y} \land \overline{z}) \lor (x \land y \land z)</tex>.
== См. также ==

* [[Сокращенная и минимальная ДНФ]]
* [[КНФ]]

==Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика]

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

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

Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза

2017-01-05T21:23:55Z

Max 27: Исправил битую ссылку

__TOC__
== Определение ==
{{Определение
| definition =
[[Оптимальный префиксный код с длиной кодового слова не более L бит|Оптимальный префиксный код]] с сохранением порядка (англ. ''order-preserving code'', ''alphabetic code'').

Пусть у нас есть алфавит <tex> \Sigma </tex>. Каждому символу <tex>c_i </tex> сопоставим его код <tex> p_i </tex>. Кодирование называется оптимальным префиксным с сохранением порядка (алфавитным), если соблюдаются:
# Условие порядка {{---}} <tex> \forall i, j : c_i < c_j \iff p_i < p_j </tex>. То есть, если символ <tex>c_i </tex> лексикографически меньше символа <tex> c_j </tex>, его код также будет [[лексикографический порядок | лексикографически]] меньше, и наоборот.
# Условие оптимальности {{---}} <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> {{---}} минимально, где <tex> f_i </tex> {{---}} частота встречаемости символа <tex> c_i </tex> в тексте, а <tex> |p_i| </tex> {{---}} длина его кода.
}}

== Алгоритм ==
Решим задачу, используя ДП на подотрезках. Пусть в ячейке <tex> D[i][j] </tex> хранится минимальная стоимость кодового дерева для отрезка алфавита от <tex> i </tex> до <tex> j </tex>.

Тогда пересчет <tex> D[i][j] </tex> будет происходить так:

<tex> D[i][j] = \min\limits_{k = i}^{j - 1} \left ( D[i][k] + D[k + 1][j] \right ) + w[i][j]</tex>

Базой динамики будет <tex> D[i][i] = 0 </tex>

Добавочный член <tex>w[i][j] = \sum\limits_{t = i}^{j} f_t </tex> возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на 1, а значит, и длины всех кодов символов <tex> c_i .. c_j </tex> также увеличиваются на 1.

Тогда такое ''наибольшее'' <tex> k </tex>, на котором достигается этот минимум, называется точкой разреза для отрезка <tex> i..j </tex>. Пусть в ячейке <tex> R[i][j] </tex> хранится точка разреза на отрезке <tex> i..j </tex>.

Если разрез происходит по какому-то определенному индексу <tex> q </tex> , такой разрез обозначим <tex> D_q[i][j] </tex>.

Таким образом, получили алгоритм, работающий за <tex> O(n^3) </tex>. Коды каждого символа можно легко получить так же, как в алгоритме Хаффмана {{---}} обходом по построенному дереву.

Если доказать монотонность точки разреза, то можно уменьшить асимптотику алгоритма до <tex> O(n^2) </tex>.

== Монотонность точки разреза ==
Для доказательства этого сперва докажем несколько лемм.

{{Определение
| definition=
Функция <tex> a </tex> удовлетворяет '''неравенству четырехугольника''' (англ. ''quadrangle inequation''), если
: <tex>\forall i \leqslant i' \leqslant j \leqslant j' : a[i][j] + a[i'][j'] \leqslant a[i'][j] + a[i][j']</tex>
}}

{{Лемма
| statement=
<tex> w </tex> удовлетворяет неравенству четырехугольника.
| proof=
Заметим, что <tex> w[i][j] = w[i][t] + w[t+1][j] </tex>, так как <tex> w[i][j] </tex> {{---}} простая арифметическая сумма. Тогда:
: <tex> w[i][j] + w[i'][j'] \leqslant w[i'][j] + w[i][j']</tex>
: <tex> (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \leqslant (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) </tex>
Получили <tex> 0 \leqslant 0 </tex>, что является верным. Лемма доказана.
}}

{{Лемма
| statement=
Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то <tex> D </tex> также удовлетворяет неравенству четырехугольника, то есть:

<tex>\forall i \leqslant i' \leqslant j \leqslant j' : D[i][j] + D[i'][j'] \leqslant D[i'][j] + D[i][j'] </tex>
| proof=
При <tex> i = i' </tex> или <tex> j = j' </tex>, очевидно, неравенство выполняется.

Рассмотрим два случая:
# <tex> i' = j </tex>
#: <tex> i < i' = j < j' </tex>. Тогда неравенство четырехугольника сводится к:
#: <tex> D[i][j] + D[j][j'] \leqslant D[i][j'] </tex>
#: Пусть <tex> k = R[i][j'] </tex>. Получили два симметричных случая:
## <tex> k \leqslant j </tex>
##: <tex> D[i][j] + D[j][j'] \leqslant w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{---}} по определению <tex> D[i][j] </tex>
##: <tex> \leqslant w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{---}} так как <tex> w[i][j'] \geqslant w[i][j] </tex>
##: <tex> \leqslant w[i][j'] + D[i][k-1] + D[k][j'] </tex> {{---}} по индукционному предположению для <tex> D </tex>
##: <tex> \leqslant D[i][j'] </tex> {{---}} по определению <tex> D[i][j'] </tex>
## <tex> k \geqslant j </tex> {{---}} аналогичный предыдущему случай.
# <tex> i' < j </tex>
#: <tex> i < i' < j < j' </tex>
#: Пусть <tex> y = R[i'][j] </tex> и <tex> z = R[i][j'] </tex>. Получили два симметричных случая:
## <tex> z \leqslant y </tex>
##: Получили <tex> i \leqslant z \leqslant y \leqslant j </tex>. Запишем:
##: <tex> D[i'][j'] + D[i][j] \leqslant D_y[i'][j'] + D_z[i][j] = w[i'][j'] + D[i'][y-1] + D[y][j'] + w[i][j] + D[i][z-1] + D[z][j] </tex>
##: <tex> \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] </tex> {{---}} по неравенству четырехугольника для <tex> w </tex>
##: <tex> \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] </tex> {{---}} по индукционному предположению для <tex> D </tex>
##: <tex> \leqslant D[i][j'] + D[i'][j] </tex> {{---}} по определению <tex> D </tex>
## <tex> z \geqslant y </tex> доказывается аналогично.
Лемма доказана.
}}

{{Теорема
| about=
Монотонность точки разреза
| statement=
Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то:

<tex> \forall i \leqslant j : R[i][j] \leqslant R[i][j+1] \leqslant R[i+1][j+1] </tex>
| proof=
В случае <tex> i = j </tex> неравенство, очевидно, выполняется. Рассматриваем случай <tex> i < j </tex> и только случай <tex> R[i][j] \leqslant R[i][j+1] </tex>(вторая часть доказывается аналогично):

Так как <tex> R[i][j] </tex> {{---}} максимальный индекс, в котором достигается минимум, достаточно показать, что:
: <tex> \forall i < k \leqslant k' \leqslant j: [D_{k'}[i][j] \leqslant D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \leqslant D_k[i][j+1]] </tex> {{---}} фактически, это означает что если на отрезке <tex> i..j </tex> разрез оптимальнее по <tex> k' </tex>, чем по <tex> k </tex>, то он также будет оптимальнее и на отрезке <tex> i..j+1 </tex>.
Докажем более сильное неравенство:
: <tex> \forall i < k \leqslant k' \leqslant j: D_k[i][j] - D_{k'}[i][j] \leqslant D_k[i][j+1] - D_{k'}[i][j+1] </tex>

: <tex> D_k[i][j] + D_{k'}[i][j+1] \leqslant D_k[i][j+1] + D_{k'}[i][j] </tex>

: <tex> (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \leqslant (w[i][j+1] + D[i][k-1] + D[k][j+1]) + (w[i][j] + D[i][k'-1] + D[k'][j]) </tex> {{---}} по определению <tex> D </tex>

: <tex> D[k][j] + D[k'][j+1] \leqslant D[k][j+1] + D[k'][j] </tex> {{---}} получили неравенство четырехугольника для <tex> k \leqslant k' \leqslant j \leqslant j+1 </tex>, что является верным из предыдущей леммы. Теорема доказана.
}}

== Объяснение квадратичной асимптотики ==
Рассмотрим матрицу <tex> R </tex>. Так как отрезки <tex> i..j </tex>, где <tex> i > j </tex> мы не рассматриваем, она будет верхнетреугольной. Вначале она будет заполнена так, что <tex> R[i][i] = i </tex>(так как для отрезка, состоящего из одного элемента, он же и является точкой разреза). Далее, для любого элемента <tex> R[i][j] </tex> его значения лежат между <tex> R[i][j-1] </tex> (левый элемент в матрице) и <tex> R[i+1][j] </tex> (нижний элемент в матрице). Так как мы используем динамику по подотрезкам, то сначала мы рассчитаем <tex> R </tex> для отрезков длины 2, затем 3, и так далее до n. Фактически, мы будем обходить диагонали матрицы, количество которых равно n.

Рассмотрим элемент <tex> R[i][j] </tex>. Для него выполняется <tex> R[i][j-1] \leqslant R[i][j] \leqslant R[i+1][j] </tex>. Следующий элемент, который мы будем пересчитывать {{---}} <tex> R[i+1][j+1] </tex>. Для него выполняется <tex> R[i+1][j] \leqslant R[i+1][j+1] \leqslant R[i+2][j+1] </tex>. Таким образом, заполняя одну диагональ, алгоритм сделает не более n шагов, а так как диагоналей n, получили асимптотику <tex> O(n^2) </tex>.

==Источники информации ==
[http://www.sciencedirect.com/science/article/pii/S0304397596003209 S.V. Nagaraj {{---}} Tutorial: Optimal binary search trees]

''Кнут Д.Э.'' {{---}} Искусство программирования, том 3. Сортировка и поиск. — М.: «Вильямс», 2005.

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

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

2017-01-05T21:15:21Z

Max 27: Отформатировал псевдокод; заменил дефисы на тире; не нашёл терминов, нуждающихся в английском эквиваленте

{{Шаблон: Задача
|definition =
Даны два массива: <tex> a[1..n] </tex> и <tex> b[1..m] </tex>. Требуется найти их ''наибольшую общую возрастающую подпоследовательность (НОВП).''}}
{{Определение
|definition =
'''Наибольшая общая возрастающая подпоследовательность, НОВП''' (англ. ''longest common increasing subsequence, LCIS'') массива <tex> A </tex> длины <tex> n </tex> и массива <tex> B </tex> длины <tex> m </tex> — это последовательность <tex> X = \left \langle x_1, x_2, ..., x_k \right \rangle </tex> такая, что <tex> x_1 < x_2 < \dots < x_k </tex>, <tex> X </tex> является ''подпоследовательностью'' <tex> A </tex> и <tex> B </tex>. }}

==Решение за время O(N4)==
Построим следующую динамику: <tex> d[i][j] </tex> {{---}} это длина наибольшей возрастающей подпоследовательности массивов <tex> a </tex> и <tex> b </tex>, последний элемент которой <tex> a[i] </tex> и <tex> b[j] (a[i] = b[j]) </tex>. Будем заполнять <tex> d[i][j] </tex> сначала по увеличению <tex> i </tex>, а при равенстве по увеличению <tex> j </tex>. Ответом на задачу будет максимум из всех элементов <tex> d[i][j] </tex> (где <tex> i = 1...n </tex>, <tex> j = 1...m. </tex>)

Заполнять <tex> d </tex> будем следующим образом: на очередном шаге сравниваем элементы <tex> a[i] </tex> и <tex> b[j] </tex>:
*Если <tex> a[i] \neq b[j] </tex>, то <tex> d[i][j] = 0 </tex> (так как нет НОВП, оканчивающейся в разных элементах).
*Если <tex> a[i] = b[j] </tex>, то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах <tex> a </tex> и <tex> b </tex>. Заметим, что предыдущие значения <tex> d </tex> уже известны, тогда очередное значение <tex dpi="130"> d[i][j] = \max\limits_{k = 1..i-1 \atop l = 1..j-1} d[k][l] + 1 </tex> при условии, что <tex> a[k] = b[l]. </tex>

Длина НОВП будет в элементе с максимальным значением <tex> d[i][j] </tex>. Для восстановления подпоследовательности можно хранить массив предков <tex> prev[1..n] </tex> массива <tex> a: prev[i] </tex> {{---}} индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>.

int[] '''LCIS'''(a: int[], b: int[])
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' m
'''if''' a[i] == b[j]
d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j] 
'''for''' k = 1 '''to''' i - 1
'''for''' l = 1 '''to''' j - 1
'''if''' a[k] == b[l] '''and''' a[k] < a[i] '''and''' d[i][j] < d[k][l] + 1
d[i][j] = d[k][l] + 1
prev[i] = k
// восстановление
b_i = 1
b_j = 1
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' m
'''if''' d[b_i][b_j] < d[i][j]
b_i = i
b_j = j
pos = b_i
// проходим по массиву a, выписывая элементы НОВП
'''while''' pos <tex> \neq </tex> 0
answer.pushBack(a[pos])
pos = prev[pos]
'''return''' answer

==Решение за время O(N3)==
Улучшим предыдущее решение. Пусть теперь <tex> d[i][j] </tex> {{---}} динамика, в которой элемент <tex> a[i] </tex> по-прежнему последний представитель НОВП массива <tex> a </tex>, а <tex> b[j] </tex> может не быть быть последним представителем массива <tex> b </tex>:
*Если <tex> a[i] \neq b[j] </tex>, будем "протаскивать" последнее удачное сравнение в динамике: <tex> d[i][j] = d[i][j-1] </tex> (понять это можно так: <tex> a[i] \neq b[j] </tex> , поэтому <tex> b[j] </tex> не последний представитель НОВП из массива <tex> b </tex>, а значит предыдущий элемент НОВП находится в префиксе <tex> b[1..j-1] </tex>, но <tex> d[i][j-1] </tex> уже посчитан).
*Если <tex> a[i] = b[j] </tex>, то одним дополнительным циклом пробежим по <tex> a </tex> и найдём предыдущий элемент НОВП, оканчивающейся в <tex> a[i] </tex> (он меньше <tex> a[i] </tex>). Из подходящих элементов выберем тот, для которого <tex> d[k][j] </tex> {{---}} максимальна.

<tex dpi="120"> d[i][j] = \max\limits_{k = 1..i-1} d[k][j] + 1 </tex> при условии, что <tex> a[k] < a[i].</tex>

Длина НОВП будет в элементе с максимальным значением <tex> d[i][m] </tex>. Для восстановления ответа будем хранить массив предков по массиву <tex> a </tex>, как и в предыдущем решении.

int[] '''LCIS'''(a: int[], b: int[])
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' m
'''if''' a[i] == b[j]
d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
'''for''' k = 1 '''to''' i - 1
'''if''' a[k] < a[i] '''and''' d[i][j] < d[k][j] + 1
d[i][j] = d[k][j] + 1
prev[i] = k
'''else'''
d[i][j] = d[i][j - 1]
// восстановление
pos = 1 // ищем элемент c максимальным d[pos][m]
'''for''' i = 1 '''to''' n
'''if''' d[pos][m] < d[i][m]
pos = i
// проходим по массиву a, выписывая элементы НОВП
'''while''' pos <tex> \neq </tex> 0
answer.pushBack(a[pos])
pos = prev[pos]
'''return''' answer

==Решение за время O(N2)==
Модифицируем предыдущее решение, добавив небольшую "хитрость". Теперь <tex> d[i][j] </tex> {{---}} это длина наибольшей общей возрастающей подпоследовательности префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, причем элемент <tex> b[j] </tex> {{---}} последний представитель НОВП массива <tex> b </tex>, а <tex> a[i] </tex> может не быть последним в массиве <tex> a </tex>. Вычислять <tex> d </tex> будем всё так же: сначала по увеличению <tex> i </tex>, а при равенстве {{---}} по увеличению <tex> j </tex>. Тогда для очередного значения <tex> d[i][j] </tex> есть два варианта:
*<tex> a[i] </tex> не входит в НОВП. Тогда <tex> d[i][j] = d[i-1][j] </tex>: значение динамики уже посчитано на префиксе <tex> a[1..i-1] </tex>.
*<tex> a[i] </tex> входит в НОВП. Это значит, что <tex> a[i] = b[j] </tex>, то есть для подсчёта <tex> d[i][j] </tex> нужно пробегать циклом по <tex> b </tex> в поисках элемента <tex> b[k] < b[j] </tex> с наибольшим значением <tex> d[i-1][k] </tex>. Но мы считаем <tex> d </tex> сначала по увеличению <tex> i </tex>, поэтому будем считать <tex> a[i] </tex> ''фиксированным''. Чтобы не запускать цикл при каждом равенстве <tex> a[i] </tex> элементу <tex> b[k] </tex>, в дополнительной переменной <tex> best </tex> будем хранить "лучший" элемент (и его индекс <tex> ind </tex> в массиве <tex> b </tex>) такой, что этот элемент строго меньше <tex> a[i] </tex> (а также меньше <tex> b[k] </tex>) и значение динамики для него максимально: <tex> b[ind] < a[i] = b[k] </tex> и <tex> best = d[i-1][ind] \rightarrow max. </tex>

int[] '''LCIS'''(a: int[], b: int[])
'''for''' i = 1 '''to''' n
ind = 0 // позиция "лучшего" элемента в массиве b
best = 0 // значение динамики для "лучшего" элемента
'''for''' j = 1 '''to''' m
d[i][j] = d[i - 1][j] // НОВП на a[1..i - 1] и b[1..j] (без элемента a[i])
'''if''' a[i] == b[j] '''and''' d[i - 1][j] < best + 1 // используем a[i]-й элемент для увеличения НОВП
d[i][j] = best + 1
prev[j] = ind
'''if''' a[i] > b[j] '''and''' d[i - 1][j] > best // при следующем равенстве a[i] == b[j']
best = d[i - 1][j] // в best будет храниться "лучший" элемент
ind = j // b[ind] < b[j'] и d[i][ind] <tex> \rightarrow </tex> max
// восстановление (по массиву b)
pos = 1 // ищем лучший элемент d[n][pos] <tex> \rightarrow </tex> max
'''for''' j = 1 '''to''' m
'''if''' d[n][pos] < d[n][j]
pos = j
// проходим по массиву b, выписывая элементы НОВП
'''while''' pos <tex> \neq </tex> 0
answer.pushBack(b[pos])
pos = prev[pos]
'''return''' answer

=== Доказательство оптимальности ===
В данной задаче используется принцип оптимальности на префиксе. Использование дополнительной переменной для подсчета всех случаев <tex> a[i] = b[j] </tex> не влияет на корректность алгоритма {{---}} это всего лишь уловки реализации. Поэтому покажем, что для вычисления очередного значения <tex> d[i][j] </tex> мы используем оптимальность на подзадачах и обращаемся к уже посчитанным значениям.
Напомним, как обозначается динамика: <tex> d[i][j] </tex> {{---}} это НОВП на префиксах <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, где последним элементом НОВП является элемент <tex> b[j] </tex>, а <tex> a[i] </tex> может не быть равен <tex> b[j] </tex> (то есть элемент <tex> a[i'] = b[j] </tex> лежит где-то в префиксе <tex> a[1..i] </tex>). Итак, для <tex> d[i][j] </tex> есть два варианта:
* <tex> a[i] \neq b[j] </tex>, тогда <tex> a[i] </tex> не влияет на результат, и последний элемент НОВП <tex> a[i'] = b[j] </tex> лежит в <tex> a[1..i-1] </tex>.
* <tex> a[i] = b[j] </tex>, тогда <tex> a[i] </tex> и <tex> b[j] </tex> {{---}} последние элементы НОВП префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>: <tex> b[j] </tex> {{---}} по определению динамики, а <tex> a[i] </tex> как элемент, который может стать последним, не ухудшая результат. Действительно, последовательность строго возрастает, поэтому если в префиксе <tex> a[1..i-1] </tex> есть элемент <tex> a[k] = b[j] </tex>, то его можно заменить на элемент <tex> a[i] </tex> без уменьшения длины НОВП. Если же в <tex> a[1..i-1] </tex> такого элемента нет, то <tex> a[i] </tex> {{---}} единственный из возможных вариантов. Итак, <tex> a[i] </tex> и <tex> b[j] </tex> {{---}} последние элементы НОВП. Значит, начало НОВП (<tex> d[i][j] </tex>) лежит в префиксах <tex> a[1..i-1] </tex> и <tex> b[1..j-1] </tex> (значения для которых уже посчитаны). Мы ищем элемент <tex> b[k] < b[j] </tex> с лучшей динамикой <tex> d[i-1][k] </tex>, что удовлетворяет условию возрастания последовательности и автоматически гарантирует, что конец такой НОВП лежит в префиксе <tex> a[1..i-1] </tex>.

== См. также ==

*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о наибольшей возрастающей подпоследовательности]]

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

[http://codeforces.ru/contest/10/problem/D Codeforces {{---}} Задача о наибольшей общей возрастающей подпоследовательности]

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

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

2017-01-05T19:36:15Z

Max 27: Добавил шаблон "задача"; правильно оформил источники информации

{{Шаблон: Задача
|definition =
Даны два массива: <tex> a[1..n] </tex> и <tex> b[1..m] </tex>. Требуется найти их ''наибольшую общую возрастающую подпоследовательность (НОВП).''}}
{{Определение
|definition =
'''Наибольшая общая возрастающая подпоследовательность, НОВП''' (англ. ''longest common increasing subsequence, LCIS'') массива <tex> A </tex> длины <tex> n </tex> и массива <tex> B </tex> длины <tex> m </tex> — это последовательность <tex> X = \left \langle x_1, x_2, ..., x_k \right \rangle </tex> такая, что <tex> x_1 < x_2 < \dots < x_k </tex>, <tex> X </tex> является ''подпоследовательностью'' <tex> A </tex> и <tex> B </tex>. }}

==Решение за время O(N4)==
Построим следующую динамику: <tex> d[i][j] </tex> - это длина наибольшей возрастающей подпоследовательности массивов <tex> a </tex> и <tex> b </tex>, последний элемент которой <tex> a[i] </tex> и <tex> b[j] (a[i] = b[j]) </tex>. Будем заполнять <tex> d[i][j] </tex> сначала по увеличению <tex> i </tex>, а при равенстве по увеличению <tex> j </tex>. Ответом на задачу будет максимум из всех элементов <tex> d[i][j] </tex> (где <tex> i = 1...n </tex>, <tex> j = 1...m. </tex>)

Заполнять <tex> d </tex> будем следующим образом: на очередном шаге сравниваем элементы <tex> a[i] </tex> и <tex> b[j] </tex>:
*Если <tex> a[i] \neq b[j] </tex>, то <tex> d[i][j] = 0 </tex> (так как нет НОВП, оканчивающейся в разных элементах).
*Если <tex> a[i] = b[j] </tex>, то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах <tex> a </tex> и <tex> b </tex>. Заметим, что предыдущие значения <tex> d </tex> уже известны, тогда очередное значение <tex dpi="130"> d[i][j] = \max\limits_{k = 1..i-1 \atop l = 1..j-1} d[k][l] + 1 </tex> при условии, что <tex> a[k] = b[l]. </tex>

Длина НОВП будет в элементе с максимальным значением <tex> d[i][j] </tex>. Для восстановления подпоследовательности можно хранить массив предков <tex> prev[1..n] </tex> массива <tex> a: prev[i] </tex> - индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>.

vector<int> '''LCIS'''(vector<int> a, vector<int> b)
d = int[n][m]
prev = int[n]
'''for''' i = 1...n
'''for''' j = 1...m
'''if''' a[i] == b[j]
d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
'''for''' k = 1...i-1
'''for''' l = 1...j-1
'''if''' a[k] == b[l] '''and''' a[k] < a[i] '''and''' d[i][j] < d[k][l] + 1
d[i][j] = d[k][l] + 1
prev[i] = k
//восстановление
b_i = 1
b_j = 1
'''for''' i = 1...n
'''for''' j = 1...m
'''if''' d[b_i][b_j] < d[i][j]
b_i = i
b_j = j
vector<int> answer
pos = b_i // проходим по массиву a, выписывая элементы НОВП
'''while''' pos != 0
answer.push(a[pos])
pos = prev[pos]
'''return''' answer

==Решение за время O(N3)==
Улучшим предыдущее решение. Пусть теперь <tex> d[i][j] </tex> - динамика, в которой элемент <tex> a[i] </tex> по-прежнему последний представитель НОВП массива <tex> a </tex>, а <tex> b[j] </tex> может не быть быть последним представителем массива <tex> b </tex>:
*Если <tex> a[i] \neq b[j] </tex>, будем "протаскивать" последнее удачное сравнение в динамике: <tex> d[i][j] = d[i][j-1] </tex> (понять это можно так: <tex> a[i] \neq b[j] </tex> , поэтому <tex> b[j] </tex> не последний представитель НОВП из массива <tex> b </tex>, а значит предыдущий элемент НОВП находится в префиксе <tex> b[1..j-1] </tex>, но <tex> d[i][j-1] </tex> уже посчитан).
*Если <tex> a[i] = b[j] </tex>, то одним дополнительным циклом пробежим по <tex> a </tex> и найдём предыдущий элемент НОВП, оканчивающейся в <tex> a[i] </tex> (он меньше <tex> a[i] </tex>). Из подходящих элементов выберем тот, для которого <tex> d[k][j] </tex> - максимальна.

<tex dpi="120"> d[i][j] = \max\limits_{k = 1..i-1} d[k][j] + 1 </tex> при условии, что <tex> a[k] < a[i].</tex>

Длина НОВП будет в элементе с максимальным значением <tex> d[i][m] </tex>. Для восстановления ответа будем хранить массив предков по массиву <tex> a </tex>, как и в предыдущем решении.

vector<int> '''LCIS'''(vector<int> a, vector<int> b)
d = int[n][m]
prev = int[n]
'''for''' i = 1...n
'''for''' j = 1...m
'''if''' a[i] == b[j]
d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
'''for''' k = 1...i-1
'''if''' a[k] < a[i] '''and''' d[i][j] < d[k][j] + 1
d[i][j] = d[k][j] + 1
prev[i] = k
'''else'''
d[i][j] = d[i][j-1]
// восстановление
pos = 1 // ищем элемент c максимальным d[pos][m]
'''for''' i = 1...n
'''if''' d[pos][m] < d[i][m]
pos = i
vector<int> answer
'''while''' pos != 0
answer.push(a[pos])
pos = prev[pos]
'''return''' answer

==Решение за время O(N2)==
Модифицируем предыдущее решение, добавив небольшую "хитрость". Теперь <tex> d[i][j] </tex> - это длина наибольшей общей возрастающей подпоследовательности префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, причем элемент <tex> b[j] </tex> - последний представитель НОВП массива <tex> b </tex>, а <tex> a[i] </tex> может не быть последним в массиве <tex> a </tex>. Вычислять <tex> d </tex> будем всё так же: сначала по увеличению <tex> i </tex>, а при равенстве - по увеличению <tex> j </tex>. Тогда для очередного значения <tex> d[i][j] </tex> есть два варианта:
*<tex> a[i] </tex> не входит в НОВП. Тогда <tex> d[i][j] = d[i-1][j] </tex>: значение динамики уже посчитано на префиксе <tex> a[1..i-1] </tex>.
*<tex> a[i] </tex> входит в НОВП. Это значит, что <tex> a[i] = b[j] </tex>, то есть для подсчёта <tex> d[i][j] </tex> нужно пробегать циклом по <tex> b </tex> в поисках элемента <tex> b[k] < b[j] </tex> с наибольшим значением <tex> d[i-1][k] </tex>. Но мы считаем <tex> d </tex> сначала по увеличению <tex> i </tex>, поэтому будем считать <tex> a[i] </tex> ''фиксированным''. Чтобы не запускать цикл при каждом равенстве <tex> a[i] </tex> элементу <tex> b[k] </tex>, в дополнительной переменной <tex> best </tex> будем хранить "лучший" элемент (и его индекс <tex> ind </tex> в массиве <tex> b </tex>) такой, что этот элемент строго меньше <tex> a[i] </tex> (а также меньше <tex> b[k] </tex>) и значение динамики для него максимально: <tex> b[ind] < a[i] = b[k] </tex> и <tex> best = d[i-1][ind] \rightarrow max. </tex>

vector<int> '''LCIS'''(vector<int> a, vector<int> b)
d = int[n][m] // динамика
prev = int[n] // массив предков
'''for''' i = 1...n
ind = 0 // позиция "лучшего" элемента в массиве b
best = 0 // значение динамики для "лучшего" элемента
'''for''' j = 1...m
d[i][j] = d[i-1][j] // НОВП на a[1..i-1] и b[1..j] (без элемента a[i])
'''if''' a[i] == b[j] '''and''' d[i-1][j] < best + 1 // используем a[i]-й элемент для увеличения НОВП
d[i][j] = best + 1
prev[j] = ind
'''if''' a[i] > b[j] '''and''' d[i-1][j] > best // при следующем равенстве a[i] == b[j']
best = d[i-1][j] // в best будет храниться "лучший" элемент:
ind = j // b[ind] < b[j'] и d[i][ind] <tex> \rightarrow </tex> max
// восстановление (по массиву b)
pos = 1 // ищем лучший элемент d[n][pos] <tex> \rightarrow </tex> max
'''for''' j = 1...m
'''if''' d[n][pos] < d[n][j]
pos = j
vector<int> answer
'''while''' pos != 0 // проходим по массиву b, выписывая элементы НОВП
answer.push(b[pos])
pos = prev[pos]
'''return''' answer

=== Доказательство оптимальности ===
В данной задаче используется принцип оптимальности на префиксе. Использование дополнительной переменной для подсчета всех случаев <tex> a[i] = b[j] </tex> не влияет на корректность алгоритма - это всего лишь уловки реализации. Поэтому покажем, что для вычисления очередного значения <tex> d[i][j] </tex> мы используем оптимальность на подзадачах и обращаемся к уже посчитанным значениям.
Напомним, как обозначается динамика: <tex> d[i][j] </tex> - это НОВП на префиксах <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, где последним элементом НОВП является элемент <tex> b[j] </tex>, а <tex> a[i] </tex> может не быть равен <tex> b[j] </tex> (то есть элемент <tex> a[i'] = b[j] </tex> лежит где-то в префиксе <tex> a[1..i] </tex>). Итак, для <tex> d[i][j] </tex> есть два варианта:
* <tex> a[i] \neq b[j] </tex>, тогда <tex> a[i] </tex> не влияет на результат, и последний элемент НОВП <tex> a[i'] = b[j] </tex> лежит в <tex> a[1..i-1] </tex>.
* <tex> a[i] = b[j] </tex>, тогда <tex> a[i] </tex> и <tex> b[j] </tex> - последние элементы НОВП префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>: <tex> b[j] </tex> - по определению динамики, а <tex> a[i] </tex> как элемент, который может стать последним, не ухудшая результат. Действительно, последовательность строго возрастает, поэтому если в префиксе <tex> a[1..i-1] </tex> есть элемент <tex> a[k] = b[j] </tex>, то его можно заменить на элемент <tex> a[i] </tex> без уменьшения длины НОВП. Если же в <tex> a[1..i-1] </tex> такого элемента нет, то <tex> a[i] </tex> - единственный из возможных вариантов. Итак, <tex> a[i] </tex> и <tex> b[j] </tex> - последние элементы НОВП. Значит, начало НОВП (<tex> d[i][j] </tex>) лежит в префиксах <tex> a[1..i-1] </tex> и <tex> b[1..j-1] </tex> (значения для которых уже посчитаны). Мы ищем элемент <tex> b[k] < b[j] </tex> с лучшей динамикой <tex> d[i-1][k] </tex>, что удовлетворяет условию возрастания последовательности и автоматически гарантирует, что конец такой НОВП лежит в префиксе <tex> a[1..i-1] </tex>.

== См. также ==

*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о наибольшей возрастающей подпоследовательности]]

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

[http://codeforces.ru/contest/10/problem/D Codeforces {{---}} Задача о наибольшей общей возрастающей подпоследовательности]

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

Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза

2017-01-05T19:11:13Z

Max 27: Заменил ссылку; заменил дефисы на тире;взял переменные и константы в Тех; исправил знаки неравенств; оформил источники информации

__TOC__
== Определение ==
{{Определение
| definition =
[[Оптимальный префиксный код с длиной кодового слова не более L бит|Оптимальный префиксный код]] с сохранением порядка (англ. ''order-preserving code'', ''alphabetic code'').

Пусть у нас есть алфавит <tex> \Sigma </tex>. Каждому символу <tex>c_i </tex> сопоставим его код <tex> p_i </tex>. Кодирование называется оптимальным префиксным с сохранением порядка (алфавитным), если соблюдаются:
# Условие порядка {{---}} <tex> \forall i, j : c_i < c_j \iff p_i < p_j </tex>. То есть, если символ <tex>c_i </tex> лексикографически меньше символа <tex> c_j </tex>, его код также будет [[лексикографический порядок | лексикографически]] меньше, и наоборот.
# Условие оптимальности {{---}} <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> {{---}} минимально, где <tex> f_i </tex> {{---}} частота встречаемости символа <tex> c_i </tex> в тексте, а <tex> |p_i| </tex> {{---}} длина его кода.
}}

== Алгоритм ==
Решим задачу, используя ДП на подотрезках. Пусть в ячейке <tex> D[i][j] </tex> хранится минимальная стоимость кодового дерева для отрезка алфавита от <tex> i </tex> до <tex> j </tex>.

Тогда пересчет <tex> D[i][j] </tex> будет происходить так:

<tex> D[i][j] = \min\limits_{k = i}^{j - 1} \left ( D[i][k] + D[k + 1][j] \right ) + w[i][j]</tex>

Базой динамики будет <tex> D[i][i] = 0 </tex>

Добавочный член <tex>w[i][j] = \sum\limits_{t = i}^{j} f_t </tex> возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на 1, а значит, и длины всех кодов символов <tex> c_i .. c_j </tex> также увеличиваются на 1.

Тогда такое ''наибольшее'' <tex> k </tex>, на котором достигается этот минимум, называется точкой разреза для отрезка <tex> i..j </tex>. Пусть в ячейке <tex> R[i][j] </tex> хранится точка разреза на отрезке <tex> i..j </tex>.

Если разрез происходит по какому-то определенному индексу <tex> q </tex> , такой разрез обозначим <tex> D_q[i][j] </tex>.

Таким образом, получили алгоритм, работающий за <tex> O(n^3) </tex>. Коды каждого символа можно легко получить так же, как в алгоритме Хаффмана {{---}} обходом по построенному дереву.

Если доказать монотонность точки разреза, то можно уменьшить асимптотику алгоритма до <tex> O(n^2) </tex>.

== Монотонность точки разреза ==
Для доказательства этого сперва докажем несколько лемм.

{{Определение
| definition=
Функция <tex> a </tex> удовлетворяет '''неравенству четырехугольника''' (англ. ''quadrangle inequation''), если
: <tex>\forall i \leqslant i' \leqslant j \leqslant j' : a[i][j] + a[i'][j'] \leqslant a[i'][j] + a[i][j']</tex>
}}

{{Лемма
| statement=
<tex> w </tex> удовлетворяет неравенству четырехугольника.
| proof=
Заметим, что <tex> w[i][j] = w[i][t] + w[t+1][j] </tex>, так как <tex> w[i][j] </tex> {{---}} простая арифметическая сумма. Тогда:
: <tex> w[i][j] + w[i'][j'] \leqslant w[i'][j] + w[i][j']</tex>
: <tex> (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \leqslant (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) </tex>
Получили <tex> 0 \leqslant 0 </tex>, что является верным. Лемма доказана.
}}

{{Лемма
| statement=
Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то <tex> D </tex> также удовлетворяет неравенству четырехугольника, то есть:

<tex>\forall i \leqslant i' \leqslant j \leqslant j' : D[i][j] + D[i'][j'] \leqslant D[i'][j] + D[i][j'] </tex>
| proof=
При <tex> i = i' </tex> или <tex> j = j' </tex>, очевидно, неравенство выполняется.

Рассмотрим два случая:
# <tex> i' = j </tex>
#: <tex> i < i' = j < j' </tex>. Тогда неравенство четырехугольника сводится к:
#: <tex> D[i][j] + D[j][j'] \leqslant D[i][j'] </tex>
#: Пусть <tex> k = R[i][j'] </tex>. Получили два симметричных случая:
## <tex> k \leqslant j </tex>
##: <tex> D[i][j] + D[j][j'] \leqslant w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{---}} по определению <tex> D[i][j] </tex>
##: <tex> \leqslant w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{---}} так как <tex> w[i][j'] \geqslant w[i][j] </tex>
##: <tex> \leqslant w[i][j'] + D[i][k-1] + D[k][j'] </tex> {{---}} по индукционному предположению для <tex> D </tex>
##: <tex> \leqslant D[i][j'] </tex> {{---}} по определению <tex> D[i][j'] </tex>
## <tex> k \geqslant j </tex> {{---}} аналогичный предыдущему случай.
# <tex> i' < j </tex>
#: <tex> i < i' < j < j' </tex>
#: Пусть <tex> y = R[i'][j] </tex> и <tex> z = R[i][j'] </tex>. Получили два симметричных случая:
## <tex> z \leqslant y </tex>
##: Получили <tex> i \leqslant z \leqslant y \leqslant j </tex>. Запишем:
##: <tex> D[i'][j'] + D[i][j] \leqslant D_y[i'][j'] + D_z[i][j] = w[i'][j'] + D[i'][y-1] + D[y][j'] + w[i][j] + D[i][z-1] + D[z][j] </tex>
##: <tex> \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] </tex> {{---}} по неравенству четырехугольника для <tex> w </tex>
##: <tex> \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] </tex> {{---}} по индукционному предположению для <tex> D </tex>
##: <tex> \leqslant D[i][j'] + D[i'][j] </tex> {{---}} по определению <tex> D </tex>
## <tex> z \geqslant y </tex> доказывается аналогично.
Лемма доказана.
}}

{{Теорема
| about=
Монотонность точки разреза
| statement=
Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то:

<tex> \forall i \leqslant j : R[i][j] \leqslant R[i][j+1] \leqslant R[i+1][j+1] </tex>
| proof=
В случае <tex> i = j </tex> неравенство, очевидно, выполняется. Рассматриваем случай <tex> i < j </tex> и только случай <tex> R[i][j] \leqslant R[i][j+1] </tex>(вторая часть доказывается аналогично):

Так как <tex> R[i][j] </tex> {{---}} максимальный индекс, в котором достигается минимум, достаточно показать, что:
: <tex> \forall i < k \leqslant k' \leqslant j: [D_{k'}[i][j] \leqslant D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \leqslant D_k[i][j+1]] </tex> {{---}} фактически, это означает что если на отрезке <tex> i..j </tex> разрез оптимальнее по <tex> k' </tex>, чем по <tex> k </tex>, то он также будет оптимальнее и на отрезке <tex> i..j+1 </tex>.
Докажем более сильное неравенство:
: <tex> \forall i < k \leqslant k' \leqslant j: D_k[i][j] - D_{k'}[i][j] \leqslant D_k[i][j+1] - D_{k'}[i][j+1] </tex>

: <tex> D_k[i][j] + D_{k'}[i][j+1] \leqslant D_k[i][j+1] + D_{k'}[i][j] </tex>

: <tex> (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \leqslant (w[i][j+1] + D[i][k-1] + D[k][j+1]) + (w[i][j] + D[i][k'-1] + D[k'][j]) </tex> {{---}} по определению <tex> D </tex>

: <tex> D[k][j] + D[k'][j+1] \leqslant D[k][j+1] + D[k'][j] </tex> {{---}} получили неравенство четырехугольника для <tex> k \leqslant k' \leqslant j \leqslant j+1 </tex>, что является верным из предыдущей леммы. Теорема доказана.
}}

== Объяснение квадратичной асимптотики ==
Рассмотрим матрицу <tex> R </tex>. Так как отрезки <tex> i..j </tex>, где <tex> i > j </tex> мы не рассматриваем, она будет верхнетреугольной. Вначале она будет заполнена так, что <tex> R[i][i] = i </tex>(так как для отрезка, состоящего из одного элемента, он же и является точкой разреза). Далее, для любого элемента <tex> R[i][j] </tex> его значения лежат между <tex> R[i][j-1] </tex> (левый элемент в матрице) и <tex> R[i+1][j] </tex> (нижний элемент в матрице). Так как мы используем динамику по подотрезкам, то сначала мы рассчитаем <tex> R </tex> для отрезков длины 2, затем 3, и так далее до n. Фактически, мы будем обходить диагонали матрицы, количество которых равно n.

Рассмотрим элемент <tex> R[i][j] </tex>. Для него выполняется <tex> R[i][j-1] \leqslant R[i][j] \leqslant R[i+1][j] </tex>. Следующий элемент, который мы будем пересчитывать {{---}} <tex> R[i+1][j+1] </tex>. Для него выполняется <tex> R[i+1][j] \leqslant R[i+1][j+1] \leqslant R[i+2][j+1] </tex>. Таким образом, заполняя одну диагональ, алгоритм сделает не более n шагов, а так как диагоналей n, получили асимптотику <tex> O(n^2) </tex>.

==Источники информации ==
[http://www.cs.ust.hk/mjg_lib/Library/Tut_BST.pdf S.V. Nagaraj {{---}} Tutorial: Optimal binary search trees]

''Кнут Д.Э.'' {{---}} Искусство программирования, том 3. Сортировка и поиск. — М.: «Вильямс», 2005.

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

Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП

2017-01-05T17:58:14Z

Max 27: Добавил англ. терминов; взял определение в шаблон; заменил дефисы на тире; правильно оформил источники информации.

{{Определение
|definition=
'''Последовательность''' (англ. ''sequence'') {{---}} это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества.
}}

== Определения ==

Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''неубывающей''''' (англ. ''nondecreasing''), если каждый элемент этой последовательности не превосходит следующего за ним.

<tex>\{x_n\}</tex> — '''''неубывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \leqslant x_{n+1}</tex>

Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''невозрастающей''''' (англ. ''nonincreasing''), если каждый следующий элемент этой последовательности не превосходит предыдущего.

<tex>\{x_n\}</tex> — '''''невозрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \geqslant x_{n+1}</tex>

Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''возрастающей''''' (англ. ''increasing''), если каждый следующий элемент этой последовательности превышает предыдущий.

<tex>\{x_n\}</tex> — '''''возрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n < x_{n+1}</tex>

Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''убывающей''''' (англ. ''decreasing''), если каждый элемент этой последовательности превышает следующий за ним.

<tex>\{x_n\}</tex> — '''''убывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n > x_{n+1}</tex>

Последовательность называется '''монотонной''' (англ. ''monotonic''), если она является неубывающей, либо невозрастающей.

Последовательность называется '''строго монотонной''' (англ. ''strictly monotonic''), если она является возрастающей, либо убывающей.

Очевидно, что строго монотонная последовательность является монотонной.

== Теорема о связи длины НВП и НУП ==

{{
Теорема
|author=
|about=
|statement=
Пусть <tex>a</tex> {{---}} перестановка чисел длины <tex>n, l</tex> {{---}} длина наибольшей возрастающей подпоследовательности (НВП), <tex>k</tex> {{---}} длина наибольшей убывающей подпоследовательности (НУП). Тогда <tex>l k \geqslant n</tex>.

|proof=
Рассмотрим два массива длины <tex>n : S </tex> и <tex> T </tex>, где <tex> S_i </tex> {{---}} длина НВП, которая заканчивается на <tex>a_i</tex>, <tex> T_i </tex> {{---}} длина НУП, которая начинается на <tex>a_i</tex>.

Докажем, что все пары <tex>(S_i, T_i)</tex> различны.
Пусть существуют такие <tex>i < j</tex> , что <tex> S_i </tex> = <tex> S_j </tex> и <tex> T_i </tex> = <tex> T_j</tex>. Если <tex>a_i < a_j</tex>, тогда <tex> a_j </tex> можно добавить к НВП, заканчивающейся на <tex> a_i </tex>, следовательно <tex>S_j \geqslant S_i + 1</tex>. Если <tex>a_i > a_j</tex>, то по аналогии <tex>T_i \geqslant T_j + 1</tex>. Противоречие! Следовательно все такие пары различны.

Заметим что <tex>1 \leqslant S_i \leqslant l, 1 \leqslant T_i \leqslant k</tex>, поэтому существуют <tex>l k</tex> различных пар <tex> (S_i, T_i) </tex>. Если <tex>l k < n</tex> тогда среди <tex> n </tex> пар найдутся две одинаковые. Такого быть не может по доказанному выше, т. е. <tex>l k \geqslant n</tex>, ч. т. д.
}}

== Следствие из теоремы ==

{{Утверждение
|statement=
Пусть <tex>n</tex> {{---}} длина последовательности, тогда длина наибольшей монотонной подпоследовательности не меньше <tex>\sqrt{n}</tex>
}}

== Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C#.D0.9D.D0.B5.D0.BA.D0.BE.D1.82.D0.BE.D1.80.D1.8B.D0.B5_.D0.B2.D0.B8.D0.B4.D1.8B_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B5.D0.B9 Википедия {{---}} Последовательность]

*[http://en.wikipedia.org/wiki/Longest_increasing_subsequence Wikipedia {{---}} Longest increasing subsequence]

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

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

Каскадный сумматор

2017-01-05T17:25:45Z

Max 27: Добавил англ. терминов; правильно оформил источники информации.

{{Определение
|definition=
'''Каскадный сумматор''' (англ. ''ripple-carry adder'') {{---}} логическая [[Реализация булевой функции схемой из функциональных элементов|схема]], осуществляющая сложение многоразрядных двоичных чисел.
}}
Как известно, с помощью [[Сумматор|полного сумматора]] можно сложить 2 одноразрядных двоичных числа. Для сложения двух <tex>n</tex>-разрядных двоичных чисел можно использовать <tex>n</tex> полных сумматоров.

При сложении двух чисел в <tex>i</tex>-том разряде складываются <TeX>a_i</TeX>, <Tex>b_i</TeX> и входной бит переноса (англ. ''carry-in bit'') <TeX>c_i</TeX>. Младший разряд суммы записывается в <tex>i</tex>-й разряд ответа (<TeX>s_i</TeX>), а старший становится выходным битом переноса (англ. ''carry-out bit'') <TeX>c_{i+1}</TeX> и используется при сложении в следующем разряде.

При этом в первый входной бит переноса подаётся ноль, а последний бит переноса даёт старший разряд суммы.

Прежде чем сложить <tex>i</tex>-ые биты, надо ждать выходного бита переноса от сложения <tex> i-1 </tex> битов, то есть сумма в каждом разряде может зависеть от суммы предыдущих разрядов. Поэтому сложение с помощью каскадного сумматора выполняется за время <tex>O(n)</tex>.

[[Файл:Ripple_carry_adder.png]]

== См. также ==
*[[Сумматор]]
*[[Двоичный каскадный сумматор]]

==Источники информации ==
* [http://en.wikipedia.org/wiki/Adder_(electronics) Wikipedia {{---}} Adder (electronics)]
* [http://rain.ifmo.ru/cat/view.php/vis/arithmetics/binary-addition-2002/algorithm Каскадное сложение]

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

[[Категория: Схемы из функциональных элементов ]]

Суперпозиции

2017-01-05T16:57:45Z

Max 27: Добавил англ. терминов.

{{Определение
|definition =
'''Суперпозиция функций''' (или '''сложная функция''', или '''композиция функций''', англ. ''function composition'') {{---}} это функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.
}}
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует [[Представление функции формулой, полные системы функций|замыкание]] данного множества функций.

== Способы получения суперпозиций ==
Рассмотрим две [[Определение булевой функции|булевы функции]]:
функцию <tex>f</tex> от <tex>n</tex> аргументов <tex>f(x_{1}, x_{2}, ..., x_{n})</tex> и
функцию <tex>g</tex> от <tex>m</tex> аргументов <tex>g(y_{1}, y_{2}, ..., y_{m})</tex>.

Тогда мы можем получить новую функцию из имеющихся двумя способами:
#Подстановкой одной функции в качестве некоторого аргумента для другой;
#Отождествлением аргументов функций.

=== Подстановка одной функции в другую ===

{{Определение
|definition =
'''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>:

<center><tex>h(x_{1}, ..., x_{n+m-1}) = f(x_{1}, ..., x_{i-1}, g(x_{i}, ..., x_{i+m-1}), x_{i+m}, ..., x_{n+m-1})</tex></center>
}}

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

При подстановке функции <tex>g</tex> вместо <tex>i</tex>-того аргумента функции <tex>f</tex>, результирующая функция <tex>h</tex> будет принимать аргументы, которые можно разделить на следующие блоки:

{|
|1. <tex> x_{1}, ..., x_{i-1}</tex>
|{{---}} аргументы функции <tex>f</tex> до подставленного значения функции <tex>g</tex>
|-
|2. <tex> x_{i}, ..., x_{i+m-1} </tex>
|{{---}} используются как аргументы для вычисления значения функции <tex>g(y_{1}, ..., y_{m})</tex>
|-
|3. <tex> x_{i+m}, ..., x_{n+m-1} </tex>
|{{---}} аргументы функции <tex>f</tex> после подставленного значения функции <tex>g</tex>
|}

'''Пример:'''

Исходные функции:
#<tex> f(a,b) = a \vee b </tex>
#<tex> g(a) = \neg a </tex>

<tex> h(a,b) = f(a,g(b)) = a \vee \neg b </tex> {{---}} подстановка функции <tex>g</tex> вместо второго аргумента функции <tex>f</tex>. В данном примере при помощи подстановки мы получили функцию <tex>h(a,b)=a \leftarrow b</tex>.

=== Отождествление переменных ===
{{Определение
|definition=
'''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента:

<center><tex>h(x_{1}, ..., x_{j-1}, x_{j+1}, ..., x_{n}) = f(x_{1}, ..., x_{i}, ..., x_{j-1}, x_{i}, x_{j+1}, ..., x_{n})</tex></center>
}}

Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.

'''Пример:'''

<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция

<tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами

Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.

== Ранги суперпозиций ==
{{Определение
|definition =
'''Ранг суперпозиции''' (англ. ''rank of function composition'') {{---}} это минимальное число подстановок и отождествлений, за которое суперпозиция может быть получена из исходного множества функций.
Суперпозиция <tex>K</tex> ранга <tex>n</tex> обозначается как <tex>K^{n}</tex>
}}

== Источники информации ==
* Осипова В.А., Основы дискретной математики: Учебное пособие, М.: ФОРУМ: ИНФРА-М, 2006, стр 62-63
*[http://ru.wikipedia.org/wiki/Композиция_функций Композиция функций в математике]
*[http://mini-soft.ru/nstu/diskr/index.php Е.Л. Рабкин, Ю.Б. Фарфоровская, Дискретная математика, Глава 7: Суперпозиция функций. Замыкание набора функций. Замкнутые классы функций. Полные наборы. Базисы]

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

ДНФ

2017-01-05T16:17:35Z

Max 27: Добавил англ. терминов; поправил аббревиатуры; убрал скобки в формулировке теоремы; выделил жирным шрифтом в определениях то, что нужно.

== ДНФ ==
{{Определение
|definition =
'''Простой конъюнкцией''' (англ. ''inclusive conjunction'') или '''конъюнктом''' (англ. ''conjunct'') называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
}}
Простая конъюнкция
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно 1 раз;
* '''монотонная''', если она не содержит отрицаний переменных.

{{Определение
|definition =
'''Дизъюнктивная нормальная форма, ДНФ''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов.
}}
Пример ДНФ:
<tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>

== СДНФ ==
{{Определение
|definition =
'''Совершенная дизъюнктивная нормальная форма, СДНФ''' (англ. ''perfect disjunctive normal form, PDNF'') — это такая ДНФ, которая удовлетворяет условиям:
* в ней нет одинаковых простых конъюнкций
* каждая простая конъюнкция полная
}}
Пример СДНФ:
<tex>f(x,y,z) = (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>

{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec {x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая.
|proof =
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона'''.

<tex>f(\vec{x}) = \neg x_i \wedge f(x_1, \dots ,x_{i-1},0,x_{i+1}, \dots ,x_n) \vee
x_i \wedge f(x_1, \dots ,x_{i-1},1,x_{i+1}, \dots ,x_n)</tex>

Данное соотношение легко проверить подстановкой возможных значений <tex>x_i</tex> (<tex>0</tex> и <tex>1</tex>). Эта формула позволяет выносить <tex>x_i</tex> за знак функции. Последовательно вынося <tex>x_1</tex>, <tex>x_2</tex>,.., <tex>x_n</tex> за знак <tex>f(\vec{x})</tex>, получаем следующую формулу :
<tex> f(\vec{x}) = \neg x_1 \wedge \neg x_2 \wedge ...\wedge \neg x_{n-1} \wedge \neg x_n \wedge f(0,0,...,0,0)~\vee~</tex>

<tex>\neg x_1 \wedge \neg x_2 \wedge ... \wedge \neg x_{n-1} \wedge x_n \wedge f(0,0,...,0,1) ~\vee~ \\
\dots \\
~\vee~ x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge \neg x_n \wedge f(1,1,...,1,0) ~\vee~\\
x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge x_n \wedge f(1,1,...,1) </tex>

Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от <tex>n</tex> переменных мы имеем <tex>2^n</tex> конъюнктов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений <tex> n </tex> переменных. Если на некотором наборе <tex>f(\vec{x})=0</tex>, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})=1</tex>, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.
}}

== Алгоритм построения СДНФ по таблице истинности ==
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.
# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
# Все полученные конъюнкции связываем операциями дизъюнкции.

== Пример построения СДНФ для медианы==
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| x || y || z || <tex> \langle x,y,z \rangle </tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1
|}

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| x || y || z || <tex> \langle x,y,z \rangle </tex> ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || <tex>(\neg {x} \land y \land z)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || <tex>(x \land \neg {y} \land z)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || <tex>(x \land y \land \neg {z})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1 || <tex>(x \land y \land z)</tex>
|}

3. Все полученные конъюнкции связываем операциями дизъюнкции.

<tex> \langle x,y,z \rangle = (x \land y \land z) \lor (\neg {x} \land y \land z) \lor (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>

==Примеры СДНФ для некоторых функций==
Стрелка Пирса: <tex> x \downarrow y = (\neg {x} \land \neg {y})</tex>

Исключающее или: <tex> x \oplus y \oplus z = (\overline{x} \land \overline{y} \land z) \lor (\overline{x} \land y \land \overline{z}) \lor (x \land \overline{y} \land \overline{z}) \lor (x \land y \land z)</tex>

== Ссылки ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика]

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

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