244
правки
Изменения
Нет описания правки
# Предложите реализацию преобразования Move to Front за $O(n \log n)$.
# Предложите реализацию преобразования Move to Front за $O(n)$.
# Докажите, что при оптимальном кодировании с помощью LZ не выгодно делать повтор блока, который можно увеличить вправо
# Разработайте алгоритм оптимального кодирования текста с помощью LZ, если на символ уходит $c$ бит, а на блок повтора $d$ бит
# Предложите семейство строк $S_1, S_2, \ldots, S_n, \ldots$, где $S_i$ имеет длину $i$, таких, что при их кодировании с помощью LZW длина строки увеличивается. Начальный алфавит $\{0, 1\}$.
# Изучите фонетический алфавит ИКАО. Какое среднее взвешенное число символов при передаче одной буквы (вероятности символов считали в позапрошлом ДЗ).
# Какое минимальное расстояние Хемминга между двумя последовательностями звуков русского языка для символа в фонетическом алфавите ИКАО (при сравнении слов разной длины считайте, что символы более длинного слова с номерами большими длины более короткого дают вклад +1). Хороший ли показатель в данном случае расстояние Хемминга? Какая самая неудачная пара слов в фонетическом алфавите ИКАО?
# Изучите коды ISBN-10 и ISBN-13. Докажите, что они находят одну ошибку в десятичной системе счисления.
# Разработайте оптимальный код исправляющий одну ошибку при пересылке 3 битов
# Разработайте код, исправляющий две ошибки, использующий асимптотически не более $2n$ бит для кодирования $2^n$ символьного алфавита (для $n>n_0$)
# Испорченный символ. Пусть вместо замены на противополжный символ портится, то есть при приеме вместо некоторых символов принимается неопределенность ""?"". Как изменятся определения и параметры кодов обнаруживающих и исправляющих $d$ ошибок в этом случае?
# Разработайте оптимальный код, исправляющий одну ошибку при пересылке сообщения из 3 битов, где возможны следующие ошибки: удаление одного бита, замена одного бита на противоположный. Таким образом, при отправке сообщения длины $l$ может быть получено либо сообщение длины $l$, в котором не более одного бита исправлено на противоположный, либо сообщение длины $l - 1$, в котором все биты верные, но одного бита, неизвестно, какого, не хватает.
# Разработайте оптимальный код, исправляющий одну ошибку при пересылке сообщения из 3 битов, где возможны следующие ошибки: добавление одного бита, замена одного бита на противоположный. Таким образом, при отправке сообщения длины $l$ может быть получено либо сообщение длины $l$, в котором не более одного бита исправлено на противоположный, либо сообщение длины $l + 1$, в котором все биты верные, а также добавлен еще один, неизвестно, какой, бит.
# Разработайте оптимальный код, исправляющий одну ошибку при пересылке сообщения из 3 битов, где возможны следующие ошибки: обмен местами двух соседних битов.
# Кодирование с ошибками. Пусть разрешается при декодировании неверно раскодировать не более одного бита. Можно ли каждую непустую двоичную строку длиной не больше $n$ сжать, чтобы её размер уменьшился хотя бы на один символ?
# Кодирование с ошибками. Пусть разрешается при декодировании неверно раскодировать не более одного бита. Можно ли каждую двоичную строку длиной от 2 до $n$ сжать, чтобы её размер уменьшился хотя бы на два символа?
# Линейность кода Хемминга. Зафиксируем количество информационных битов $n$. Докажите, что множество векторов, которые являются корректными кодами Хемминга образуют множество решений системы линейных уравнений $Ax=0$ для некоторой матрицы $A$, все вычисления происходят по модулю $2$.
# Получение кода Хемминда умножением на матрицу. Зафиксируем количество информационных битов $n$. Докажите, что существует матрица $A$, такая что если $y$ это код Хемминга для строки $x$, то $y=Ax$.
