Лабораторная ФКН: Интерактивный аналог теоремы Вольфа – Слепяна. Докладчик: Александр Козачинский, Лаборатория теоретической информатики

Козачинский Александр Николаевич

Международная лаборатория теоретической информатики: стажер-исследователь

 

В теории информации рассматривается следующая ситуация: отправителю (Алисе) надо передать некоторую информацию получателю (Бобу) по бесшумному каналу наиболее экономным способом. При этом возможны различные уточнения постановки задачи. Например, Боб может обладать или не обладать некоторой дополнительной информацией о входе Алисы. Рассматриваются различные ограничения на то, какими могут быть входы Алисы и Боба. В наиболее общем виде — это произвольные случайные величины. Кроме того, например, можно потребовать, чтобы входы брались из большого (стремящегося к бесконечности) числа независимых испытаний одной и той же случайной величины.

В теореме Вольфа – Слепяна рассматривается как раз это ограничение и устанавливается асимптотика длины оптимального кодирования (даже если у Боба есть вспомогательная информация). В докладе будет рассказано о том, что изменится, если из теоремы Вольфа – Слепяна убрать требование большого числа независимых испытаний. Основное отличие состоит в том, что придется разрешить Бобу посылать ответные сообщения Алисе, чтобы корректировать ее действия. Будет рассказано и о значении этой задачи для коммуникационной сложности.

 Афиша Лабораторной (PDF, 234 Кб)