Изменения
Нет описания правки
# При арифметическом кодировании можно учитывать, что с учетом уже потраченных символов соотношения символов становятся другими и отрезок надо делить в другой пропорции. Всегда ли кодирование с таким уточнением лучше классического арифметического кодирования?
# При арифметическом кодировании трудным моментом является деление отрезка в пропорциях, не являющихся степенями двойки. Рассмотрим модификацию арифметического кодирования, когда соотношения между символами приближаются дробями со знаменателями - степенями двойки. Что можно сказать про получившийся алгоритм?
# Проанализируйте время работы алгоритма арифиметического кодирования
# Докажите, что для любого $c > 1$ существует распределение частот $p_1, p_2, .., p_n$, что арифметическое кодирование в $c$ раз лучше Хаффмана
# Докажите, что при оптимальном кодирование с помощью LZ77 не выгодно делать повтор блока, который можно увеличить вправо
# Верно ли утверждение из предыдущего задания при кодировании с помощью L78?
# Разработайте алгоритм оптимального кодирования текста с помощью LZ77, если на символ уходит $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)$.
# Докажите, что $n$-битный код, исправляющий одну ошибку содержит не более, чем $2^n/(n+1)$ кодовое слово.
# Обобщите оценку из предыдущего задания на код, исправляющий $k$ ошибок.
# Разработайте оптимальный код исправляющий одну ошибку при пересылке 2 битов
# Разработайте оптимальный код исправляющий одну ошибку при пересылке 3 битов
# Разработайте оптимальный код исправляющий одну ошибку при пересылке 4 битов
# Разработайте код, исправляющий две ошибки, использующий асимптотически не более $2n$ бит для кодирования $2^n$ символьного алфавита (для $n > n_0$)
= ЭТО НЕ КОНЕЦ, ЭТО ЕЩЕ ТОЛЬКО НАЧАЛО =
