Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Теория кодирования
Санкт-Петербург / весна 2012, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

С появлением технической возможности хранить и пересылать большие объёмы данных немедленно появилась необходимость бороться со спорадически возникающимися в этих данных ошибками. Эта практическая потребность дала рождение теории кодирования — науке о надежном хранении и передаче информации. Типичный вопрос, изучаемый этой наукой: как передавать по каналу связи полезную информацию, если один процент пересылаемых битов теряется или искажается?

Методы, развитые в теории кодирования, оказываются эффективны в задачах, не связанных непосредственно с защитой сообщений от шума (например, в теории коммуникационной сложности, в схемах разделения секрета, при дерандомизации вероятностных алгоритмов, и т.д.).

В этом курсе мы изучим базовые результаты теории кодирования, а также рассмотрим некоторые недавние достижения этой науки. Курс будет ориентирован на студентов, изучающих computer science; особое внимание будет уделено алгоритмическим задачам теории кодирования.

Для понимания курса полезно знакомство с основами теории вероятностей и линейной алгебры.

Дата и время Занятие Место Материалы
24 марта
17:20–18:55
Комбинаторная модель канала с шумом. Базовые определения и простейшие оценки, Лекция ПОМИ РАН видео
24 марта
19:05–20:40
Классические линейные коды: код Хэмминга и код Рида-Соломона, Лекция ПОМИ РАН видео
25 марта
11:15–12:50
Каскадные коды, явная конструкция асимптотически хорошего кода, Лекция ПОМИ РАН видео
25 марта
13:00–14:35
Декодирование списком, Лекция ПОМИ РАН видео
25 марта
15:35–17:10
Вероятностная модель канала с шумом и классические теоремы Шеннона, Лекция ПОМИ РАН видео
31 марта
17:20–18:55
Вычислительная трудность декодирования линейного кода, Лекция ПОМИ РАН видео
31 марта
19:05–20:40
Декодирование списком и генераторы псевдослучайных битов, Лекция ПОМИ РАН видео
01 апреля
11:15–12:50
От декодирования списком и к однозначному декодированию, Лекция ПОМИ РАН видео
01 апреля
13:00–14:35
Псевдослучайные перестановки и случайное кодирование, Лекция ПОМИ РАН видео
01 апреля
15:35–17:10
Коды на графах, Лекция ПОМИ РАН видео