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

Вероятностное пространство, элементарный исход, событие

2017-05-21T00:17:40Z

94.242.26.14: /* Примеры вероятностных пространств */

==Основные определения==
{{Определение | definition =
'''Дискретным вероятностным пространством''' (англ. ''discrete probability space'') называется пара из некоторого (не более, чем счетного) множества <tex>\Omega</tex> и функции <tex>p\colon \Omega \to \mathbb R_+ </tex> ( <tex>\Omega</tex> называется '''множеством элементарных исходов''' (англ. ''sample space''), <tex>\omega \in \Omega</tex> {{---}} '''элементарным исходом''' (англ. ''elementary outcome''), такая, что <tex>\sum_{\omega \in \Omega}\limits {p(\omega)} = 1</tex>.
}}

<tex>p</tex> называют '''дискретной вероятностной мерой''' (англ. ''discrete probability measure''), или '''дискретной плотностью вероятности''' (англ. ''discrete probability density'').
 

<tex>p(\omega)</tex> {{---}} вероятность элементарного исхода.
 

{{Определение | definition =
Множество <tex>A \subset \Omega</tex> называется '''событием''' (англ. ''event'').
}}

<tex>p(A)= \sum_{a \in A}\limits {p(a)}</tex>, то есть вероятность события равна сумме вероятностей входящих в него элементарных исходов.

{{Определение | definition = '''Прямым произведением вероятностных пространств''' (англ. ''direct product of probability spaces'') <tex>X=\langle\Omega_{1},p{}_{1}\rangle</tex> и <tex>Y=\langle\Omega_{2},p{}_{2}\rangle</tex> называется такое вероятностное пространство <tex>Z\:\langle\Omega,p\rangle \: = X\times Y</tex>, что 
<tex>\Omega=\Omega_{1}\times\Omega_{2}</tex> <tex> p(\omega_{1},\omega_{2}) = p(\omega_{1})\cdot p(\omega_{2})</tex>
}}

Другими словами, <tex>\Omega</tex> {{---}} множество всех пар элементарных исходов из <tex>X</tex> и <tex>Y</tex> (т.е. декартово произведение этих множеств).

==Примеры вероятностных пространств==
# '''Конечные вероятностные пространства'''
## '''Честная монета''' Множество исходов <tex>\Omega = \left\{0,1\right\}</tex>, где <tex>0</tex> {{---}} выпадает орел, <tex>1</tex> {{---}} выпадает решка. <tex> p(0)=p(1)=0,5.</tex>. Рассмотрим все возможные события и их вероятности для этого пространства. <tex>\varnothing </tex>: <tex> p(\varnothing)=0</tex>. То есть вероятность того, что не выпадет ничего, равна нулю. <tex>\left\{0\right\} </tex>: <tex> p(0)=0,5</tex>. Вероятность того, что выпадет орел, равна одной второй. <tex>\left\{1\right\} </tex>: <tex> p(1)=0,5</tex>. Вероятность того, что выпадет решка, равна одной второй. <tex>\left\{0,1\right\} </tex>: <tex> p(\left\{0,1\right\})=1</tex>. Действительно, вероятность того, что выпадет орел или решка, равна единице.
## '''Нечестная монета''' Множество исходов здесь такое же, как и в предыдущем пространстве, однако <tex>p(0)=x, p(1) = 1 - x=y</tex>, где <tex>x,y \in \left[ 0,1 \right ]</tex>.
## '''Игральная кость''' Множество исходов <tex>\Omega = \left\{1,2,3,4,5,6\right\}</tex>. <tex> p(i)= \dfrac {1}{6}</tex>. Рассмотрим некоторые события этого пространства. <tex>A=\left\{1,2,3 \right\}</tex> : <tex>p(A)=\dfrac {1}{6}+\dfrac{1}{6}+\dfrac{1}{6}=\dfrac{3}{6}=\dfrac{1}{2}</tex>. Вероятность выпадения одного из трех чисел {{---}} <tex>1, 2, 3</tex> {{---}} равна одной второй. <tex>B=\left\{2,4 \right\}</tex> : <tex>p(B)=\dfrac {1}{6}+\dfrac{1}{6}=\dfrac{2}{6}=\dfrac{1}{3}</tex>. Числа <tex>2</tex> или <tex>4</tex> выпадут с вероятностью одна треть.
## '''Колода карт''' <tex>\Omega = \left\{\left \langle i,j\right \rangle| i \in \left\{1..4\right\}; j \in \left\{1..13\right\} \right\}</tex>. Здесь <tex>i</tex> {{---}} масть, <tex>j</tex> {{---}} достоинство карты. Вероятность элементарного исхода этого пространства <tex>p(\left \langle i,j\right \rangle)=\dfrac {1}{52}</tex>.
# '''Бесконечное вероятностное пространство''' Пусть задано множество следующих элементарных исходов: выпадение орла на <tex>i</tex>-ом подбрасывании честной монеты в первый раз. Тогда вероятность исхода с номером <tex>i</tex> равна: <tex> p(A_{i}) = \dfrac {1}{2^{i} } </tex>. Очевидно, что вероятности этих событий образовывают убывающую геометрическую прогрессию с знаменателем прогрессии равным <tex> \dfrac {1}{2} </tex>. Найдем сумму этой прогрессии: <tex> \sum \limits_{i=1}^{\infty} p(A_{i}) = \dfrac { b_{1} } { 1 - q } = \dfrac { \dfrac{1}{2} }{ 1 -\dfrac{1}{2} } = 1</tex>. Так как сумма всех элементарных исходов равна <tex>1</tex>, то это множество является вероятностым пространством.

==См. так же==
1.[http://ru.wikipedia.org/wiki/Вероятностное_пространство Вероятностное пространство]
 
2.[http://www.machinelearning.ru/wiki/index.php?title=%D0%92%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%BE Дискретное вероятностное пространство]

==Литература==
1. ''Ширяев А.Н.'' Вероятность. — М.: МЦНМО, 2004.

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

[[Категория: Теория вероятности ]]

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

2017-01-07T20:07:10Z

94.242.26.14: /* Предподсчёт */

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

=== Предподсчёт ===
Рассмотрим [[Задача о наибольшей общей подпоследовательности|задачу о наибольшей общей подпоследовательности]] для двух последовательностей одинаковой длины. Тогда таблица динамического программирования имеет размер <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>. Тогда предподсчитанные квадраты, которые понадобятся для дальнейшего вычисления НОП, выглядят так:

{|
|
{|class="wikitable" style="background-color:#FFF; text-align:center; "
| colspan="2" rowspan="2" |
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
|-
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>0</tex>
|<tex>1</tex>
|<tex>1</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
|<tex>1</tex>
|<tex>1</tex>
|<tex>1</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>1</tex>
|<tex>2</tex>
|<tex>2</tex>
|}
| || || || || || || 
|
{|class="wikitable" style="background-color:#FFF; text-align:center; "
| colspan="2" rowspan="2" |
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
|-
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>1</tex>
|<tex>1</tex>
|<tex>1</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
|<tex>2</tex>
|<tex>2</tex>
|<tex>2</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>2</tex>
|<tex>3</tex>
|<tex>3</tex>
|}
|}

{|
|
{|class="wikitable" style="background-color:#FFF; text-align:center; "
| colspan="2" rowspan="2" |
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
|-
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
|<tex>1</tex>
|<tex>2</tex>
|<tex>2</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>1</tex>
|<tex>2</tex>
|<tex>3</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>1</tex>
|<tex>2</tex>
|<tex>3</tex>
|}
| || || || || || || 
|
{|class="wikitable" style="background-color:#FFF; text-align:center; "
| colspan="2" rowspan="2" |
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>
|-
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
|<tex>1</tex>
|<tex>1</tex>
|<tex>2</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>1</tex>
|<tex>2</tex>
|<tex>2</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>1</tex>
|<tex>2</tex>
|<tex>2</tex>
|}
|}

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

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

{| style=" border-collapse:collapse; text-align: center"
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 0 0 1px"|
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 0 0 0"|
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>
|-
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 0 0 0 1px"|
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
|-
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>0</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px;border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
|-
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
|-
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
|-
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>
|-
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>
|-
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>
|}

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

=== Время работы ===
При предподсчёте перебирается <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-07T20:05:05Z

94.242.26.14: /* Вычисление НОП на сжатой матрице */

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

=== Предподсчёт ===
Рассмотрим [[Задача о наибольшей общей подпоследовательности|задачу о наибольшей общей подпоследовательности]] для двух последовательностей одинаковой длины. Тогда таблица динамического программирования имеет размер <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>. Тогда предподсчитанные квадраты, которые понадобятся для дальнейшего вычисления НОП, выглядят так:

{|
|
{|class="wikitable" style="background-color:#FFF; text-align:center; "
| colspan="2" rowspan="2" |
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
|-
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>0</tex>
|<tex>1</tex>
|<tex>1</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
|<tex>1</tex>
|<tex>1</tex>
|<tex>1</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>1</tex>
|<tex>2</tex>
|<tex>2</tex>
|}
| || || || || || || || 
|
{|class="wikitable" style="background-color:#FFF; text-align:center; "
| colspan="2" rowspan="2" |
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
|-
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>1</tex>
|<tex>1</tex>
|<tex>1</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
|<tex>2</tex>
|<tex>2</tex>
|<tex>2</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>2</tex>
|<tex>3</tex>
|<tex>3</tex>
|}
|}

{|
|
{|class="wikitable" style="background-color:#FFF; text-align:center; "
| colspan="2" rowspan="2" |
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
|-
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
|<tex>1</tex>
|<tex>2</tex>
|<tex>2</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>1</tex>
|<tex>2</tex>
|<tex>3</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>1</tex>
|<tex>2</tex>
|<tex>3</tex>
|}
| || || || || || || || 
|
{|class="wikitable" style="background-color:#FFF; text-align:center; "
| colspan="2" rowspan="2" |
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>
|-
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>
|<tex>1</tex>
|<tex>1</tex>
|<tex>2</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>1</tex>
|<tex>2</tex>
|<tex>2</tex>
|-
! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>
! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>
|<tex>1</tex>
|<tex>2</tex>
|<tex>2</tex>
|}
|}

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

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

{| style=" border-collapse:collapse; text-align: center"
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 0 0 1px"|
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 0 0 0"|
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>
|-
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 0 0 0 1px"|
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
|-
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>0</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px;border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
|-
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
|-
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
|-
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>
|-
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>
|-
| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>
| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>
|}

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

=== Время работы ===
При предподсчёте перебирается <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-06T23:46:45Z

94.242.26.14: /* Источники информации */

{{Определение
|definition=
'''Транзитивным остовом''' (''transitive reduction'') [[Определение отношения|отношения]] <tex> R </tex> на множестве <tex> X </tex> называется минимальное отношение <tex> R^- </tex> на <tex> X </tex> такое, что [[транзитивное замыкание]] <tex> R^- </tex> равно транзитивному замыканию <tex> R </tex>.
}}

__TOC__
== Алгоритм для антисимметричных отношений ==
Для удобства представим отношение в виде графа: <tex> G = \left < V, E \right > </tex>. Его транзитивным остовом будет граф <tex> G^- = \left < V, E^- \right > </tex>.

Введём несколько обозначений:
* <tex> u \underset{G}{\to} v </tex> — в графе <tex> G </tex> есть ребро из вершины <tex> u </tex> в <tex> v </tex>;
* <tex> u \underset{G}{\leadsto} v </tex> — в графе <tex> G </tex> есть путь (возможно, рёберно пустой) из вершины <tex> u </tex> в <tex> v </tex>;
* <tex> u \underset{G}{\overset{+}{\leadsto}} v </tex> — в графе <tex> G </tex> есть рёберно непустой путь из вершины <tex> u </tex> в <tex> v </tex>.

Также введём определение транзитивного замыкания в терминах теории графов:
{{Определение
|definition=
'''Транзитивным замыканием''' графа <tex> G = \left < V, E \right > </tex> называется граф <tex> G^* = \left < V, E^* \right > </tex>, где <tex> E^* = \left \{ (i, j) \in V \times V | i \underset{G}{\leadsto} j \right \} </tex>.
}}

Так как отношение антисимметрично, то граф ацикличен, то есть в нём выполняется следующее: <tex> \forall i, j \in V: i \underset{G}{\overset{+}{\leadsto}} j \Longrightarrow i \neq j </tex>.

Докажем теорему, из которой следует алгоритм.

{{Теорема
|statement=
Пусть <tex> G^- = \left < V, E^- \right > </tex>. Тогда <tex> E^- = \left \{ k \underset{G}{\to} m \ | \ \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} </tex>
|proof=
Докажем, что <tex> E^- \subseteq \left \{ k \underset{G}{\to} m \ | \ \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \}</tex>:

Пусть <tex> G^- </tex> уже построен. Пусть <tex> k \underset{G^-}{\to} m </tex>. Тогда <tex> k \neq m </tex> (так как иначе удаление ребра <tex> (k, m) </tex> из <tex> E^- </tex> приведёт к образованию меньшего графа с тем же транзитивным замыканием, что нарушает условие минимальности транзитивного остова). Поэтому по определению транзитивного остова <tex> k \underset{G}{\overset{+}{\leadsto}} m </tex>.

Пусть <tex> l </tex> — вершина, для которой выполняется <tex> k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m </tex>. Докажем, что <tex> k = l </tex>, от противного. Пусть <tex> k \neq l </tex>. <tex> G </tex> ацикличен, поэтому <tex> l \neq m </tex>. Поскольку <tex> G^* = (G^-)^* </tex>, верно <tex> k \underset{G^-}{\overset{+}{\leadsto}} l \wedge l \underset{G^-}{\overset{+}{\leadsto}} m </tex>. Поскольку <tex> G^- </tex> ацикличен, путь из <tex> k </tex> в <tex> l </tex> не может содержать ребра <tex> (k, m) </tex>, аналогично путь из <tex> l </tex> в <tex> m </tex> не может содержать <tex> (k, m) </tex>. Поэтому в <tex> G^- </tex> существует путь из <tex> k </tex> в <tex> m </tex>, не содержащий в себе ребро <tex> (k, m) </tex>, значит, удаление <tex> (k, m) </tex> из <tex> E^- </tex> не изменит транзитивное замыкание, что противоречит условию минимальности <tex> E^- </tex>. Поэтому <tex> \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] </tex>. Поскольку <tex> k \underset{G}{\overset{+}{\leadsto}} m </tex>, существует такая вершина <tex> l </tex>, что <tex> k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m </tex>, что приводит к выводу, что <tex> k \underset{G}{\to} m </tex>.

Докажем, что <tex> \left \{ k \underset{G}{\to} m \ | \ \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} \subseteq E^- </tex>:

Предположим, что <tex> k \underset{G}{\to} m </tex> и <tex> \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] </tex>. Докажем, что <tex> k G^- m </tex>, от противного. Предположим, что <tex> (k, m) \notin E^- </tex>. Поскольку <tex> G </tex> ацикличен, <tex> k \neq m </tex> и поэтому <tex> k \underset{G^-}{\overset{+}{\leadsto}} m </tex>. Поскольку <tex> (k, m) \notin E^- </tex>, существует вершина <tex> l </tex> такая, что <tex> k \underset{G^-}{\leadsto} l \wedge l \underset{G^-}{\leadsto} m </tex> и <tex> k \neq l \neq m </tex>, поэтому <tex> k \underset{G}{\overset{+}{\leadsto}} l \wedge l \underset{G}{\overset{+}{\leadsto}} m </tex>. Поскольку <tex> G </tex> ацикличен, существует вершина <tex> l' \neq k </tex>, для которой выполняется <tex> k \underset{G}{\overset{+}{\leadsto}} l' \wedge l' \underset{G}{\to} m </tex>, что противоречит нашему предположению.

Так как множества <tex> E^- </tex> и <tex> \left \{ k \underset{G}{\to} m \ | \ \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} </tex> включены друг в друга, они совпадают, что и требовалось доказать.
}}

=== Псевдокод ===
<tex> R^- </tex> = <tex> R </tex>
foreach <tex> a </tex> in <tex> X </tex>
foreach <tex> b </tex> in <tex> X </tex>
foreach <tex> c </tex> in <tex> X </tex>
if <tex> aRb </tex> and <tex> bRc </tex> and <tex> aRc </tex>
<tex> R^- </tex>.delete(pair(<tex> a </tex>, <tex> c </tex>))

== Источники информации ==
* [http://en.wikipedia.org/wiki/Transitive_reduction Wikipedia: Transitive reduction]
* [http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-1987/1987-25.pdf J.A. La Poutré and J. van Leeuwen. «Maintenance of transitive closures and transitive reductions of graphs», 1987]

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

Транзитивный остов

2017-01-06T23:38:50Z

94.242.26.14: /* Источники */

Теорема Кэли

2017-01-06T23:13:11Z

94.242.26.14:

{{
Теорема
|author=Кэли(''Cayley'')
|about=о вложении любой конечной группы в группу перестановок
|statement=
Любая конечная группа <tex>G</tex> изоморфна некоторой подгруппе группы перестановок (симметрической группе).

|proof=
Пусть <tex>\circ</tex> {{---}} бинарная операция в группе <tex>G</tex>.
Рассмотрим некоторый элемент <tex>g \in G</tex> и функцию <tex>f_g : G \rightarrow G, f_g(x) = g \circ x</tex>.
<tex>f_g</tex> {{---}} перестановка, так как

# Для любых <tex>x, y</tex> таких, что <tex>x \neq y</tex> верно, что <tex>g \circ x \neq g \circ y</tex> <tex>\Rightarrow f_g</tex> {{---}} инъекция.
# Мощность <tex>G</tex> {{---}} конечна <tex>\Rightarrow f_g</tex> {{---}} биективно, и является перестановкой.

Пусть <tex>\circ</tex> {{---}} композиция двух перестановок.
Если <tex>f_g</tex> {{---}} перестановка, то <tex>f_{g^{-1}}</tex> {{---}} обратная перестановка, где <tex>g^{-1}</tex> {{---}} обратный элемент <tex>g</tex>, так как <tex> (f_{g^{-1}} \circ f_g) (x) = f_{g^{-1}}(f_g (x)) =g^{-1} \circ g \circ x = x </tex>.
Если <tex>e</tex> {{---}} нейтральный элемент в группе, то <tex>f_e</tex> {{---}} тождественная перестановка.
Таким образом множество всех функций <tex>K = \{f_g : g \in G\}</tex> {{---}} подгруппа симметрической группы, так как композиция двух функций из <tex>K</tex> не выводит из <tex>K</tex>, потому что <tex>(f_a \circ f_b)(x) = f_a(f_b(x)) = a \circ b \circ x = f_{a \circ b}(x) = f_c(x) </tex>, где <tex>c = a \circ b </tex>, значит <tex>f_a \circ f_b \in K</tex>

Рассмотрим множество <tex>K</tex>. По доказанному выше, оно является подгруппой симметрической группы. Осталось доказать, что <tex>G</tex> и <tex>K</tex> изоморфны. Для этого рассмотрим функцию <tex>T : G \rightarrow K,\, T(x) = f_x</tex>. Заметим, что для всех <tex>x \in G \quad(f_g \circ f_h)(x) = f_{(g \circ h)}(x)</tex>, то есть <tex>T(g)\circ T(h) = T(g \circ h)</tex>.

Значит <tex>T</tex> {{---}} гомоморфизм.

#<tex>T</tex> {{---}} инъекция, потому что <tex>f_g(x) = f_{g'}(x) \Rightarrow g = f_g(x) \circ x^{-1} = f_{g'}(x) \circ x^{-1} = g'</tex>.
#Сюрьективность <tex>T</tex> очевидна из определения <tex>K</tex>.

То есть <tex>T</tex> {{---}} гомоморфизм и биекция, а значит изоморфизм <tex>G</tex> и <tex>K</tex> установлен.
}}
==Примеры==
Примером и иллюстрацией для данной теоремы является группа <tex> \mathbb Z_3</tex> {{---}} группа остатков по модулю 3, с операцией сложения.

Пусть <tex>\ \varphi :\mathbb{Z}_3\rightarrow S_3</tex>

<tex> \varphi(0)=\begin{bmatrix} 0 & 1 & 2 \\ 0 & 1 & 2 \end{bmatrix} </tex>

<tex> \varphi(1)=\begin{bmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \end{bmatrix} </tex>

<tex> \varphi(2)=\begin{bmatrix} 0 & 1 & 2 \\ 2 & 0 & 1 \end{bmatrix} </tex>

==Источники==
* [http://en.wikipedia.org/wiki/Cayley's_theorem Cayley's theorem - Wikipedia, the free encyclopedia]

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