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

Классы NC и AC

2012-06-05T06:50:50Z

217.66.152.146:

Предположим у нас есть компьютер с <tex>poly(n)</tex> процессоров. Тогда актуально распараллелить полиномиальные вычисления, чтобы выполнять их не за <tex>poly(n)</tex> времени, а за <tex>poly(\log(n))</tex>. В качестве модели вычислений будем использовать логические схемы, но так как схема способна обрабатывать лишь входы заданной длины, то будем рассматривать семейства схем — по одной для каждой длины входа. Также потребуем, чтобы такую схему можно было эффективно построить на машине Тьюринга. Введем определения таких семейств, и соотнесем их с параллельными вычислениями.

==Определения==
{{Определение
|definition=
<tex>\mathrm{NC^i}</tex> — множество языков, распознаваемых семейством логических схем полиномиального от <tex>n</tex> размера, глубиной <tex>O(\log ^i (n))</tex> и со степенью входа каждого элемента не более 2, причем существует детерминированная машина Тьюринга, принимающая на вход <tex>1^n</tex> и строящая соответствующую схему используя <tex>O(\log (n))</tex> ячеек памяти, где <tex>n</tex> — длина входа.
}}

{{Определение
|definition=
<tex>\mathrm{AC^i}</tex> определяется аналогично <tex>\mathrm{NC^i}</tex>, за исключением того, что степень входа элемента может быть неограничена, то есть элементы <tex>\mathrm{OR}</tex> и <tex>\mathrm{AND}</tex> могут иметь более двух входов.
}}

{{Определение
|definition=
<tex>\mathrm{NC} = \bigcup \limits_{i = 0}^{\infty} \mathrm{NC^i}</tex>.
}}

{{Определение
|definition=
<tex>\mathrm{AC} = \bigcup \limits_{i = 0}^{\infty} \mathrm{AC^i}</tex>.
}}

==Теоремы==
{{Теорема
|statement=<tex>\mathrm{NC^i} \subset \mathrm{AC^i} \subset \mathrm{NC^{i+1}}</tex>.
|proof=
*<tex>\mathrm{NC^i} \subset \mathrm{AC^i}</tex> <br/>
Это понятно из определения <tex>\mathrm{NC^i}</tex> и <tex>\mathrm{AC^i}</tex>. <br/>
*<tex>\mathrm{AC^i} \subset \mathrm{NC^{i+1}}</tex> <br/>
Пусть <tex>L \in \mathrm{AC^i}</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex> полиномиального размера. Степень входа каждого элемента схемы <tex>C_n</tex> не превосходит полинома от <tex>n</tex>, поскольку степень входа не может превосходить число элементов в схеме. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более 2 следующим образом:

[[Файл:AndCircuit.png|500px|center]]

При такой замене глубина схемы увеличится не более чем в <tex>\log_2 r(n) = O(\log(n))</tex> раз, а так как изначально глубина схемы была <tex>O(\log^i(n))</tex>, то после замены всех элементов она станет <tex>O(\log^i(n)) \cdot O(\log(n)) = O(\log^{i+1}(n))</tex>.<br/>
При замене одного элемента будет добавлено не более <tex>r(n)</tex> элементов, потому, поскольку изначальный размер схемы был полиномиальным и каждый элемент мы заменили полиномиальным числом элементов, после всех замен размер схемы останется полиномиальным.
}}
'''Следствие:''' <tex>\mathrm{NC} = \mathrm{AC}</tex>.

{{Теорема
|statement=<tex>\mathrm{NC} \subseteq \mathrm{P}</tex>.
|proof =
Пусть <tex>L \in \mathrm{NC}</tex>. Тогда <tex>L</tex> распознается некоторым семейством схем <tex>C_n</tex> таких, что существует детерминированная машина Тьюринга, строящая схему по <tex>1^n</tex>, используя <tex>O(\log (n))</tex> ячеек памяти. Конфигурация МТ задается положением головки и состоянием ячеек памяти, то есть у МТ может быть <tex>n \cdot 2^{O(\log (n))} = O(n^2)</tex> конфигураций. При построении схемы конфигурации не могут повторяться, иначе МТ зациклится, следовательно схема будет построена за полиномиальное от <tex>n</tex> время. Построим для данного входа схему и вычислим её. На вычисление схемы будет затрачено полиномиальное время, так как размер схемы полиномиален.}}
Равенство <tex>\mathrm{NC}</tex> и <tex>\mathrm{P}</tex> — неразрешенная на данный момент задача.

{{Утверждение
|about=тезис о связи <tex>\mathbf{NC}</tex> с параллельными алгоритмами
|statement=
<tex>L</tex> распознается параллельным компьютером с <tex>O(poly(n))</tex> процессоров за время <tex>O(poly(\log (n))</tex> тогда и только тогда, когда <tex>L \in \mathrm{NC}</tex>.
|proof=
''(набросок доказательства)''

Пусть <tex>L \in \mathrm{NC}</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex>, где <tex>C_n</tex> размера <tex>N=O(poly(n))</tex> и имеет глубину <tex>O(\log^d n)</tex>. Возьмем параллельный компьютер с <tex>N</tex> процессорами, где каждый из них будет играть роль одного элемента схемы. Так как компьютер параллельный, то вычисления на каждом уровне схемы будут выполняться параллельно. Тогда получаем, что всего потребуется <tex>O(\log^d(n))</tex> времени.

Пусть <tex>L</tex> распознается параллельным компьютером с <tex>N=O(poly(n))</tex> процессоров за время <tex>D=O(\log^d n)</tex>. Построим схему глубины <tex>D</tex>, на каждом уровне которой будет по <tex>N</tex> элементов, таких, что <tex>i</tex>-й элемент на уровне <tex>t</tex> выполняет вычисления, производимые <tex>i</tex>-м процессором в момент времени <tex>t</tex>. Всего в схеме будет <tex>N \cdot D = O(poly(n)) \cdot O(\log^d n) = O(poly(n))</tex> элементов.
}}

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

Алгоритм Хаффмана

2012-02-28T17:02:43Z

217.66.152.146: Переделано доказательство второй леммы

'''''Алгоритм Хаффмана''''' — алгоритм оптимального префиксного кодирования алфавита. Это один из классических алгоритмов, известных с 60-х годов. Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко — цепочку большей длины.

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

{{Определение
|definition=
Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex>, такой, что:

1. <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>

2. Сумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot c_{i}</tex> минимальна. (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>)

называется '''кодом Хаффмана'''.
}}
== Алгоритм ==

Построение кода Хаффмана сводится к построению соответствующего бинарного дерева по следующему алгоритму:

1. Составим список кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента, весом, равным частоте появления символа в тексте.

2. Из списка выберем два узла с наименьшим весом.

3. Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве дочерних.

4. Добавим к списку только что сформированный узел.

5. Если в списке больше одного узла, то повторить пункты со второго по пятый.

== Пример ==

[[Файл:Mississippi.png|400px|thumb|right|Дерево Хаффмана для слова ''"Миссисипи"'']]

Для примера возьмём слово ''"Миссисипи"''. Тогда алфавит будет <tex>A= \{</tex> ''и, м, п, с'' <tex>\} </tex>, а набор весов <tex>W=\{4, 1, 1, 3\}</tex>:

{| class="wikitable"
! Узел || и || м || п || с
|-
| Вес || 4 || 1 || 1 || 3
|}

По алгоритму возьмем два символа с наименьшей частотой - это ''м'' и ''п''. Сформируем из них новый узел ''мп'' весом 2 и добавим его к списку узлов:

{| class="wikitable"
! Узел || и || мп || с
|-
| Вес || 4 || 2 || 3
|}

Затем объединим в один узел узлы ''мп'' и ''c'':

{| class="wikitable"
! Узел || и || мпс
|-
| Вес || 4 || 5
|}

И, наконец, объединяем два узла ''и'' и ''мпс''. Итак, мы получили дерево Хаффмана и соответствующую ему таблицу кодов:

{| class="wikitable"
! Символ || и || м || п || с
|-
| Код || 0 || 100 || 101 || 11
|}

Таким образом, закодированное слово ''"миссисипи"'' будет выглядеть как ''"1000111101101010"''. Длина закодированного слова - 16 бит. Стоит заметить, что если бы мы использовали для кодирования каждого символа из четырёх по 2 бита, длина закодированного слова составила бы 18 бит.

== Корректность алгоритма Хаффмана ==

Чтобы доказать корректность алгоритма Хаффмана, покажем, что в задаче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора.

{{Лемма
|id=lemma1
|about=1
|statement=
Пусть <tex>C</tex> — алфавит, каждый символ <tex>c \in C</tex> которого встречается с частотой <tex>f[c]</tex>. Пусть <tex>x</tex> и <tex>y</tex> — два символа алфавита <tex>C</tex> с самыми низкими частотами.

Тогда для алфавита <tex>C</tex> существует оптимальный префиксный код, кодовые слова символов <tex>x</tex> и <tex>y</tex> в котором имеют одинаковую максимальную длину и отличаются лишь последним битом.
|proof=
Возьмем дерево <tex>T</tex>, представляющее произвольный оптимальный префиксный код для алфавита <tex>C</tex>. Преобразуем его в дерево, представляющее другой оптимальный префиксный код, в котором символы <tex>x</tex> и <tex>y</tex> - листья с общим родительским узлом, находящиеся на максимальной глубине.

Пусть символы <tex>a</tex> и <tex>b</tex> имеют общий родительский узел и находятся на максимальной глубине дерева <tex>T</tex>. Предположим, что <tex>f[a] \le f[b]</tex> и <tex>f[x] \le f[y]</tex>. Так как <tex>f[x]</tex> и <tex>f[y]</tex> - две наименьшие частоты, а <tex>f[a]</tex> и <tex>f[b]</tex> - две произвольные частоты, то выполняются отношения <tex>f[x] \le f[a]</tex> и <tex>f[y] \le f[b]</tex>. Пусть дерево <tex>T'</tex> - дерево, полученное из <tex>T</tex> путем перестановки листьев <tex>a</tex> и <tex>x</tex>, а дерево <tex>T''</tex> - дерево полученное из <tex>T'</tex> перестановкой листьев <tex>b</tex> и <tex>y</tex>. Разность стоимостей деревьев <tex>T</tex> и <tex>T'</tex> равна:

<tex>B(T) - B(T') = \sum\limits_{c \in C} f(c)d_T(c) - \sum\limits_{c \in C} f(c)d_{T'}(c) = (f[a] - f[x])(d_T(a) - d_T(x)),</tex>

что больше либо равно <tex>0</tex>, так как величины <tex>f[a] - f[x]</tex> и <tex>d_T(a) - d_T(x)</tex> неотрицательны. Величина <tex>f[a] - f[x]</tex> неотрицательна, потому что <tex>x</tex> - лист с минимальной частотой, а величина <tex>d_T(a) - d_T(x)</tex> является неотрицательной, так как лист <tex>a</tex> находится на максимальной глубине в дереве <tex>T</tex>. Точно так же перестановка листьев <tex>y</tex> и <tex>b</tex> не будет приводить к увеличению стоимости. Таким образом, разность <tex>B(T') - B(T'')</tex> тоже будет неотрицательной.

Таким образом, выполняется неравенство <tex>B(T'') \le B(T)</tex>. С другой стороны, <tex>T</tex> - оптимальное дерево, поэтому должно выполняться неравенство <tex>B(T) \le B(T'')</tex>. Отсюда следует, что <tex>B(T) = B(T'')</tex>. Значит, <tex>T''</tex> - дерево, представляющее оптимальный префиксный код, в котором символы <tex>x</tex> и <tex>y</tex> имеют одинаковую максимальную длину, что и доказывает лемму.
}}

{{Лемма
|id=lemma2
|about=2
|statement=Пусть дан алфавит <tex>C</tex>, в котором для каждого символа <tex>c \in C</tex> определены частоты <tex>f[c]</tex>. Пусть <tex>x</tex> и <tex>y</tex> — два символа из алфавита <tex>C</tex> с минимальными частотами. Пусть <tex>C'</tex> — алфавит, полученный из алфавита <tex>C</tex> путем удаления символов <tex>x</tex> и <tex>y</tex> и добавления нового символа <tex>z</tex>, так что <tex>C' = C \backslash \{ x, y \} \cup {z}</tex>. По определению частоты <tex>f</tex> в алфавите <tex>C'</tex> совпадают с частотами в алфавите <tex>C</tex>, за исключением частоты <tex>f[z] = f[x] + f[y]</tex>. Пусть <tex>T'</tex> — произвольное дерево, представляющее оптимальный префиксный код для алфавита <tex>C'</tex> Тогда дерево <tex>T</tex>, полученное из дерева <tex>T'</tex> путем замены листа <tex>z</tex> внутренним узлом с дочерними элементами <tex>x</tex> и <tex>y</tex>, представляет оптимальный префиксный код для алфавита <tex>C</tex>.
|proof=
Сначала покажем, что стоимость <tex>B(T)</tex> дерева <tex>T</tex> может быть выражена через стоимость <tex>B(T')</tex> дерева <tex>T'</tex>. Для каждого символа <tex>c \in C \backslash \{x, y \}</tex> верно <tex>d_T(C) = d_{T'}</tex>, значит, <tex>f[c]d_T(c) = f[c]d_{T'}(c)</tex>. Так как <tex>d_T(x) = d_T(y) = d_{T'} (z) + 1</tex>, то

<tex>f[x]d_T(x) + f[y]d_T(y) = (f[x] + f[y])(d_{T'}(z) + 1) = f[z]d_{T'}(z) + (f[x] + f[y])</tex>

из чего следует, что

<tex> B(T) = B(T') + f[x] + f[y] </tex>

или

<tex> B(T') = B(T) - f[x] - f[y] </tex>

Докажем лемму от противного. Предположим, что дерево <tex>T</tex> не представляет оптимальный префиксный код для алфавита <tex>C</tex>. Тогда существует дерево <tex>T''</tex> такое, что <tex>B(T'') < B(T)</tex>. Согласно лемме (1), элементы <tex>x</tex> и <tex>y</tex> можно считать дочерними элементами одного узла. Пусть дерево <tex>T'''</tex> получено из дерева <tex>T''</tex> заменой элементов <tex>x</tex> и <tex>y</tex> листом <tex>z</tex> с частотой <tex>f[z] = f[x] + f[y]</tex>. Тогда

<tex>B(T''') = B(T'') - f[x] - f[y] < B(T) - f[x] - f[y] = B(T')</tex>,

что противоречит предположению о том, что дерево <tex>T'</tex> представляет оптимальный префиксный код для алфавита <tex>C'</tex>. Значит, наше предположение о том, что дерево <tex>T</tex> не представляет оптимальный префиксный код для алфавита <tex>C</tex>, неверно, что и доказывает лемму.
}}

{{Теорема
|id=th1
|statement=
Алгоритм Хаффмана дает оптимальный префиксный код.
|proof=
Справедливость теоремы непосредственно следует из лемм (1) и (2)
}}

== Литература ==
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4

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

[[Категория: Алгоритмы сжатия ]]