Коды переменной длины

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

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

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