Алгоритмическая теория информации и случайность индивидуальных объектов06.07.2015 15:04

В середине 1960-х годов разным людям (Колмогоров, Соломонов, Левин, Чейтин) стало понятно, что можно определять количество информации (сложность) индивидуального объекта как минимальную длину программы, которая этот объект порождает (при естественных ограничениях на язык программирования). Возникла алгоритмическая теория информации, которая оказалась связанной с разными областями: от философских вопросов оснований теории вероятностей (когда мы отвергаем статистические гипотезы?) до комбинаторики (неравенства, связывающие размеры множеств и их проекций) и теории вычислимости.

Лекцию, которую мы выбрали для вас сегодня, читал на факультете компьютерных наук Вышки известный математик Александр Шень. Когда-то он под руководством Владимира Успенского, ученика Колмогорова, защитил диссертацию «Алгоритмические варианты понятия энтропии».
В лекции рассказывается об основных определениях и каких-то базовых результатах. Александр Шень окончил мехмат МГУ. Сейчас является сотрудником Института проблем передачи информации им. А.А. Харкевича РАН и Лаборатории Национального центра научных исследований Франции. Научные интересы: алгоритмы, колмогоровская сложность, логика, теория информации. Почти все книги, которые Александр Ханиевич написал о математике и программированию, находятся в свободном доступе.