Понедельник, 10 декабря, 106. Начало в 14:30.
Докладчик: А.Х. Шень (LIRMM, ИППИ РАН).
Тема: Три подхода к определению понятия количества информации: увеличение сложности при случайном шуме.
Abstract
Первая статья Колмогорова 1965 года указывала "три подхода к определению количества информации" - комбинаторный (логарифм мощности), вероятностный (шенноновская энтропия) и алгоритмический (длина кратчайшего описания). Эта возможность перевода с одного языка на другой многократно оказывалась полезной: скажем, теорема Харпера о множестве с минимальной окрестностью в булевом кубе была переформулирована (Бюрман, Верещагин, Фортноу и др.) как возможность увеличить колмогоровскую сложность изменением некоторой доли битов. Мы делаем то же самое в вероятностной ситуации и выясняем, какова может быть типичная сложность данного слова
![$ x $](../../../sites/default/files/tex/33fe5a238412ce3cd054309829bfa5d804965124/index.png)
, если в нём каждый бит изменить с вероятностью
![$ p $](../../../sites/default/files/tex/81a85cd9ce8e28d72def1388ff73c11c76349c17/index.png)
, получая неулучшаемую оценку для этой типичной сложности.
(по работе с Глебом Пособиным)
Приложение