Теория кодирования - важная часть дискретной математики и теоретической информатики, и кое-что там вполне можно понять и оценить, не углублясь в детали и почти без формул. Мы попробуем разобраться в самом простом и важном в этой науке.

План курса:

I Задача исправления ошибок. Вероятностная и невероятностная постановки (мы рассматриваем только вторую). Комбинаторная интерпретация: точки на расстоянии, упаковка шаров. Основная проблема теории кодирования. Исправление одной ошибки: код Хемминга. Нижние и верхние оценки (volume bound, Варшамов-Гильберт).

II Коды в большем алфавите. Код Рида-Соломона. Как декодировать код Рида-Соломона? Как построить код с линейным увеличением длины и постоянной долей исправляемых ошибок? Каскадные коды, полиномиальное декодирование. Код Адамара и его локальность. Многочлены от нескольких переменных. Кодирование и вероятностная проверка равенства.