Курс "Теория кодирования" на опенэду

Программа

1. Алфавитное кодирование. Достаточные условия однозначности декодирования: равномерность, префиксность, суффиксность. Распознавание однозначности: критерий Маркова. Оценка длины неоднозначно декодируемого слова.
2. Неравенство Крафта—Макмиллана; существование префиксного кода с заданным набором длин слов; следствие об универсальности префиксных кодов.
3. Коды с минимальной избыточностью: постановка задачи, теорема Хаффмана о редукции.
4. Задача исправления и обнаружения ошибок. Геометрическая интерпретация. Типы ошибок. Метрики Хемминга и Левенштейна. Кодовое расстояние. Основные задачи теории кодов, исправляющих ошибки.
5. Коды Варшамова—Тененгольца, алгоритмы исправления одиночных ошибок выпадения и вставки символов.
6. Простейшие границы для параметров кодов, исправляющих ошибки замещения: границы сферической упаковки, Синглтона, Плоткина.
7. Вложение метрических пространств. Лемма о числе векторов в евклидовом пространстве. Граница Элайеса—Бассалыго.
8. Линейные коды. Определения. Порождающая и проверочная матрицы. Связь кодового расстояния с проверочной матрицей. Граница Варшамова—Гилберта. Систематическое кодирование. Декодирование по синдрому. Коды Хемминга.
9. Остаточный код. Граница Грайсмера—Соломона—Штиффлера.
10. Сложность задачи декодирования линейных кодов: задача NCP (задачи о ближайшем кодовом слове).
11. Коды Рида—Соломона. Алгоритм декодирования Берлекэмпа—Велча.
12. Коды Рида—Маллера: кодовое расстояние, алгоритм мажоритарного декодирования.
13. Варианты обобщений конструкции Рида—Маллера. Лемма Липтона—ДеМилло—Шварца—Зиппеля. Понятие об алгеброгеометрических кодах.
14. Графы-расширители. Вероятностное доказательство существования расширителей. Коды на основе двудольных графов. Кодовое расстояние кодов на основе расширителей. Алгоритм декодирования Сипсера—Спилмана.
15. Теоремы Шеннона для вероятностной модели канали.
16. Приложения кодов, исправляющих ошибки. Рандомизированный протокол в коммуникационной сложности. Криптосхема Мак-Элиса. Однородные (псевдослучайные) множества на основе кодов, их приложения к дерандомизации в задаче MAX-SAT.