Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English

Теория кодирования
Весна 2012, посмотреть все семестры

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

Since people transmit, process and store huge amount of information, and the hardware is always faulty, we need some means to protect the data against sporadic errors. This need gave birth to the branch of mathematics concerned with methods of reliable data transmission. This area is usually addressed to as \emph{coding theory}. A typical question in this theory is one of the following type: how to use a communication channel where \( 1\% \) of sent bits are lost or corrupted?

The methods developed in coding theory proved to be useful in many problems far beyond error correcting issues, e.g., in communication complexity, in secret sharing, in derandomization of probabilistic algorithms, etc.

In this course we study the basic concepts and classic theorems of coding theory and also discuss some recent achievements in this area. The course is targeted to advanced students studying computer science. We shall specially focus on algorithmic issues of coding theory. The prerequisites of this course are the basic university courses in probability and linear algebra.

Дата и время Название Место Материалы
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
Коды на графах, лекция ПОМИ РАН видео