Понедельник, 10 декабря, 106. Начало в 14:30.
Докладчик: А.Х. Шень (LIRMM, ИППИ РАН).
Тема: Три подхода к определению понятия количества информации: увеличение сложности при случайном шуме.
Abstract
Первая статья Колмогорова 1965 года указывала "три подхода к определению количества информации" - комбинаторный (логарифм мощности), вероятностный (шенноновская энтропия) и алгоритмический (длина кратчайшего описания). Эта возможность перевода с одного языка на другой многократно оказывалась полезной: скажем, теорема Харпера о множестве с минимальной окрестностью в булевом кубе была переформулирована (Бюрман, Верещагин, Фортноу и др.) как возможность увеличить колмогоровскую сложность изменением некоторой доли битов. Мы делаем то же самое в вероятностной ситуации и выясняем, какова может быть типичная сложность данного слова
, если в нём каждый бит изменить с вероятностью
, получая неулучшаемую оценку для этой типичной сложности.
(по работе с Глебом Пособиным)
Приложение