Пятница 26.04. Андрей Рыжиков (университет Пари-Эст Марн-ля-Вале, Франция): "О поиске коротких синхронизирующих слов для префиксных кодов"
PDMI seminars
Тема: О поиске коротких синхронизирующих слов для префиксных кодов
Место: ауд. 106
Время: 26.04.2019, 17:00
Докладчик: Андрей Рыжиков (университет Пари-Эст Марн-ля-Вале, Франция)
Abstract:
Префиксные коды -- это наиболее известный класс кодов переменной длины, широко используемый при сжатии и передаче информации. В общем случае коды переменной длины неустойчивы к ошибкам, так как одно удаление, добавление или замена символа способны десинхронизировать декодер, тем самым сделав весь дальнейший процесс декодирования некорректным. Тем не менее, для широкого класса кодов (называемых синхронизируемыми) возможно возвращение к корректному декодированию.
Мы изучаем задачу поиска кратчайшего синхронизирующего слова для заданного префиксного кода. Мы рассматриваем две ситуации: когда код задан произвольным детерминированным автоматом, распознающим его звезду, и когда код задан его буквальным декодером (число состояний которого полиномиально эквивалентно суммарной длине всех слов кода). Для произвольных декодеров мы показываем сложность аппроксимации задачи, в то время как для буквальных декодеров мы приводим эффективные приближённые алгоритмы.
Это совместная работа с Мареком Шикуа (университет Вроцлава, Польша), являющаяся усилением наших результатов с MFCS 2018.