Понятие энтропии в середине XX века ввёл [Клод Шеннон][1]. Её можно интуитивно описать как «среднее количестве битов информации в одном значении случайной величины». Но её нельзя применить к индивидуальным объектам (скажем, к тексту романа или ДНК) — где нет ансамбля многих однородных объектов, нет и случайных величин.




В середине 1960-х годов разным людям (Колмогоров, Соломонов, Левин, Чейтин) стало понятно, что можно определять количество информации (сложность) индивидуального объекта как минимальную длину программы, которая этот объект порождает (при естественных ограничениях на язык программирования). Возникла алгоритмическая теория информации, которая оказалась связанной с разными областями: от философских вопросов оснований теории вероятностей (когда мы отвергаем статистические гипотезы?) до комбинаторики (неравенства, связывающие размеры множеств и их проекций) и теории вычислимости. Лекцию, которую мы выбрали для вас сегодня, читал на факультете компьютерных наук Вышки известный математик [Александр Шень][2]. Когда-то он под руководством [Владимира Успенского][3], ученика Колмогорова, защитил диссертацию «Алгоритмические варианты понятия энтропии». [Читать дальше →][4]

[1]: https://en.wikipedia.org/wiki/Claude_Shannon
[2]: https://ru.wikipedia.org/wiki/Шень,_Александр_Ханиевич
[3]: https://en.wikipedia.org/wiki/Vladimir_Andreyevich_Uspensky
[4]: http://habrahabr.ru/post/261761/#habracut