City: Saint-Petersburg Kazan Language: Русский English

Variable Length Codes: Synchronization, Decomposition, and Beyond
Saint-Petersburg / spring 2019, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

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

Date and time Class|Name Venue|short Materials
27 April
17:15–18:45
Лекция 1, lecture Таймс No