Понедельник 10.12. А.Х. Шень (LIRMM, ИППИ РАН): "Три подхода к определению понятия количества информации: увеличение сложности при случайном шуме"

Понедельник 10.12. А.Х. Шень (LIRMM, ИППИ РАН): "Три подхода к определению понятия количества информации: увеличение сложности при случайном шуме"

Speaker:

А.Х. Шень

Date:

Monday, December 10, 2018 - 14:30

Abstract:

Первая статья Колмогорова 1965 года указывала "три подхода к определению количества информации" - комбинаторный (логарифм мощности), вероятностный (шенноновская энтропия) и алгоритмический (длина кратчайшего описания). Эта возможность перевода с одного языка на другой многократно оказывалась полезной: скажем, теорема Харпера о множестве с минимальной окрестностью в булевом кубе была переформулирована (Бюрман, Верещагин, Фортноу и др.) как возможность увеличить колмогоровскую сложность изменением некоторой доли битов. Мы делаем то же самое в вероятностной ситуации и выясняем, какова может быть типичная сложность данного слова $x$, если в нём каждый бит изменить с вероятностью $p$, получая неулучшаемую оценку для этой типичной сложности.