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

Коды переменной длины: сихронизация, декомпозиция и другое
Санкт-Петербург / весна 2019, посмотреть все семестры

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

Коды переменной длины, используемые для сжатия информации, имеют много примечательных свойств. Одно из самых интересных -- умение большинства кодов восстанавливаться после ошибок передачи. Несмотря на то, что даже одна ошибка может сделать декодирование полностью некорректным, в большинстве ситуаций возврат к корректному декодированию происходит довольно быстро. Этот эффект возникает благодаря появлению в потоке символов сихронизирующих слов. Код, для которого существует такое слово, называют синхронизирующимся.

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

Никакие предварительные знания не потребуются.

Дата и время Название Место Материалы
27 апреля
17:15–20:30
Лекция 1, лекция ПОМИ РАН видео
28 апреля
11:15–12:45
Лекция 2, лекция ПОМИ РАН видео
28 апреля
13:00–14:30
Лекция 3, лекция ПОМИ РАН видео