244
правки
Изменения
Нет описания правки
# Дана формула в КНФ. Можно каждое вхождение переменной x заменить на её отрицание. Необходимо добиться, чтобы формула после этих преобразований оказалась в форме Хорна. Предложите алгоритм, который сводит эту задачу к задаче 2SAT.
# Свести 3SAT к проверке существования удовлетворяющего назначения для формулы, которая является конъюнкцией клозов, каждый из которых является либо клозом Хорна, либо клозом Крома
# Найдите в интернете частоты букв в английских текстах и постройте код Хаффмана для этих частот. Придумайте, как продемонстрировать результат и сравните получившийся код с кодом постоянной длины.
# Найдите в интернете частоты букв в русских текстах и постройте код Хаффмана для этих частот. Придумайте, как продемонстрировать результат и сравните получившийся код с кодом постоянной длины.
# Возьмите большой несжатый файл (например, изображение .bmp) и посчитайте частоты всех возможных 256 байтов в этом файле. Постройте код Хаффмана для этих частот
# Как выглядит дерево Хаффмана для частот символов $1, 2, ..., 2^{n-1}$ (степени двойки) ?
# Как выглядит дерево Хаффмана для частот символов $1, 1, 2, 3, ..., F_{n-1}$ (числа Фибоначчи)?
# Докажите, что если размер алфавита - степень двойки и частоты никаких двух символов не отличаются в 2 или более раз, то код Хаффмана не лучше кода постоянной длины
# Модифицируйте алгоритм Хаффмана, чтобы строить $k$-ичные префиксные коды (коды, использующие алфавит не из двух символов, а из $k \ge 2$). Докажите корректность.
# Укажите, как построить дерево Хаффмана за $O(n)$, если символы уже отсортированы по частоте
# Предложите способ хранения информации об оптимальном префиксном бинарном коде для n-символьного алфавита, использующий не более $2n - 1 + n \lceil\log_2(n)\rceil$ бит ($\lceil x\rceil$ - округление $x$ вверх)
# Приведите пример однозначно декодируемого бинарного кода оптимальной длины, который не является ни префиксным, ни развернутым префиксным (после разворота всех слов он тоже не становится префиксным)
# Для каких префиксных кодов существует строка, для которой он является кодом Хаффмана? Предложите алгоритм построения такой строки.
# Дан набор частот $p_1, p_2, \ldots, p_n$, $p_i \ge 0$, $\sum\limits_i p_i = 1$. Докажите, что существует префиксный код, где длина $i$-го кодового слова равна $\lceil \log_2 (\frac 1{p_i}) \rceil$.
# Обозначим $H(p_1, \ldots, p_n) = \sum\limits_{i=1}^n p_i \log_2 ( \frac 1{p_i} )$. Докажите, что длина кода из прошлой задачи (в этом контексте ее стоит понимать, как ""среднее количество бит, затраченное на случайный символ"") не превосходит $H(p_1, \ldots, p_n) + 1$.
# Пусть заданы пары $(u_i, v_i)$. Предложите полиномиальный алгоритм проверки, что существует код Хаффмана для некоторой строки, в котором $i$-е кодовое слово содержит $u_i$ нулей и $v_i$ единиц.
# Докажите, что если в коде Хаффмана для некоторой строки $i$-е кодовое слово содержит $u_i$ нулей и $v_i$ единиц, то для многочлена от двух переменных $f(x, y) = \sum_{i=1}^n x^{u_i}y^{v_i}$ выполнено $f(x, y) - 1 = (x + y - 1) g(x, y)$ для некоторого многочлена $g(x, y)$.
# Изучите коды Шеннона-Фано https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A8%D0%B5%D0%BD%D0%BD%D0%BE%D0%BD%D0%B0_%E2%80%94_%D0%A4%D0%B0%D0%BD%D0%BE. Приведите пример текста, для которого код Шеннона-Фано хуже кода Хаффмана.
# Предложите алгоритм проверки того, что заданный двоичный код является однозначно декодируемым. Алгоритм должен работать за полином от суммы длин кодовых слов.
# Обобщите алгоритм Хаффмана для ""сжатых"" алфавитов, заданных в следующем виде: дано $n$ пар $(k_i, f_i)$, означающих, что в алфавите присутствует $k_i$ символов с частотой $f_i$. Придумайте, как за полиномиальное время найти длину кода Хаффмана для такого алфавита и оцените время работы алгоритма.
