Теория кодирования - важная часть дискретной математики и теоретической информатики, и кое-что там вполне можно понять и оценить, не углублясь в детали и почти без формул. Мы попробуем разобраться в самом простом и важном в этой науке.
План курса:
I Задача исправления ошибок. Вероятностная и невероятностная постановки (мы рассматриваем только вторую). Комбинаторная интерпретация: точки на расстоянии, упаковка шаров. Основная проблема теории кодирования. Исправление одной ошибки: код Хемминга. Нижние и верхние оценки (volume bound, Варшамов-Гильберт).
II Коды в большем алфавите. Код Рида-Соломона. Как декодировать код Рида-Соломона? Как построить код с линейным увеличением длины и постоянной долей исправляемых ошибок? Каскадные коды, полиномиальное декодирование. Код Адамара и его локальность. Многочлены от нескольких переменных. Кодирование и вероятностная проверка равенства.
Semester | Branch |
---|---|
autumn 2017 | Saint Petersburg |