Изменения
Нет описания правки
# Предложите алгоритм проверки того, что заданный двоичный код является однозначно декодируемым. Алгоритм должен работать за полином от суммы длин кодовых слов.
# Обобщите алгоритм Хаффмана для "сжатых" алфавитов, заданных в следующем виде: дано $n$ пар $(k_i, f_i)$, означающих, что в алфавите присутствует $k_i$ символов с частотой $f_i$. Придумайте, как за полиномиальное время найти длину кода Хаффмана для такого алфавита и оцените время работы алгоритма.
# Верно ли, что если длины кодовых слов некоторого кода удовлетворяют неравенству Крафта-МакМиллана, то это код является однозначно декодируемым?
# Петя утверждает, что он разработал однозначно декодируемый код $c$, в котором для каждой строки $x$ длина её кода $c(x)$ не больше длины $x$, а хотя бы для одной длина кода строго меньше. Прокомментируйте результат Пети.
# Вася утверждает, что он разработал однозначно декодируемый код $c$, в котором для некоторого $n$ хотя бы для половины строк $x$ длины не больше $n$ длина кода $c(x)$ строго меньше длины $x$. Прокомментируйте результат Васи.
# Пусть вероятности символов упорядочены по убыванию ($p_1 \ge p_2 \ge \ldots \ge p_n$) и являются дробями, у которых знаменатель - степень двойки. Что можно сказать про арифметическое кодирование в этом случае?
# Докажите, что для любого $c > 1$ существует распределение частот $p_1, p_2, .., p_n$, что арифметическое кодирование в среднем тратит в $c$ раз меньше бит на символ строки, чем код Хаффмана.
# Докажите, что при оптимальном кодировании с помощью LZ не выгодно делать повтор блока, который можно увеличить вправо
# Разработайте алгоритм оптимального кодирования текста с помощью LZ, если на символ уходит $c$ бит, а на блок повтора $d$ бит
# Предложите семейство строк $S_1, S_2, \ldots, S_n, \ldots$, где $S_i$ имеет длину $i$, таких, что при их кодировании с помощью LZW длина строки увеличивается. Начальный алфавит $\{0, 1\}$.
# Предложите алгоритм декодирования кода Барроуза-Уиллера.
# Предложите алгоритм декодирования кода Барроуза-Уиллера за $O(n)$.
# Предложите реализацию преобразования Move to Front за $O(n \log n)$.
# Предложите реализацию преобразования Move to Front за $O(n)$.
# Разработайте оптимальный код исправляющий одну ошибку при пересылке 3 битов
# Разработайте код, исправляющий две ошибки, использующий асимптотически не более $2n$ бит для кодирования $2n$ символьного алфавита (для $n>n_0$)
# Разработайте оптимальный код, исправляющий одну ошибку при пересылке сообщения из 3 битов, где возможны следующие ошибки: удаление одного бита, замена одного бита на противоположный. Таким образом, при отправке сообщения длины $l$ может быть получено либо сообщение длины $l$, в котором не более одного бита исправлено на противоположный, либо сообщение длины $l - 1$, в котором все биты верные, но одного бита, неизвестно, какого, не хватает.
# Разработайте оптимальный код, исправляющий одну ошибку при пересылке сообщения из 3 битов, где возможны следующие ошибки: добавление одного бита, замена одного бита на противоположный. Таким образом, при отправке сообщения длины $l$ может быть получено либо сообщение длины $l$, в котором не более одного бита исправлено на противоположный, либо сообщение длины $l + 1$, в котором все биты верные, а также добавлен еще один, неизвестно, какой, бит.
# Кодирование с ошибками. Пусть разрешается при декодировании неверно раскодировать не более одного бита. Можно ли каждую непустую двоичную строку длиной не больше $n$ сжать, чтобы её размер уменьшился хотя бы на один символ?
# Кодирование с ошибками. Пусть разрешается при декодировании неверно раскодировать не более одного бита. Можно ли каждую двоичную строку длиной от 2 до $n$ сжать, чтобы её размер уменьшился хотя бы на два символа?
