В середине 1960-х годов разным людям (Колмогоров, Соломонов, Левин, Чейтин) стало понятно, что можно определять количество информации (сложность) индивидуального объекта как минимальную длину программы, которая этот объект порождает (при естественных ограничениях на язык программирования). Возникла алгоритмическая теория информации, которая оказалась связанной с разными областями: от философских вопросов оснований теории вероятностей (когда мы отвергаем статистические гипотезы?) до комбинаторики (неравенства, связывающие размеры множеств и их проекций) и теории вычислимости.
Лекцию, которую мы выбрали для вас сегодня, читал на факультете компьютерных наук Вышки известный математик Александр Шень. Когда-то он под руководством Владимира Успенского, ученика Колмогорова, защитил диссертацию «Алгоритмические варианты понятия энтропии».
В лекции рассказывается об основных определениях и каких-то базовых результатах. Александр Шень окончил мехмат МГУ. Сейчас является сотрудником Института проблем передачи информации им. А.А. Харкевича РАН и Лаборатории Национального центра научных исследований Франции. Научные интересы: алгоритмы, колмогоровская сложность, логика, теория информации. Почти все книги, которые Александр Ханиевич написал о математике и программированию, находятся в свободном доступе.
Комментарии (5)
artemonster
06.07.2015 20:14Кстати, в качестве «альтернативной» теории советую почитать публикации R.Vigo Generalized Representational Information Theory (GRIT)
maxstroy
07.07.2015 09:37Спасибо! Мне в свое время помогло понимание того, что энтропия — есть мера нашего знания о внутреннем устройстве системы. И тогда не важно, из чего она состоит.
youngmysteriouslight
14.07.2015 14:32Не совсем понятно, почему колмогоровскую сложность нельзя считать программно.
С одной стороны понятно, что при наличии алгоритма, вычисляющего колмогоровскую энтропию всякой строки при фиксированном языке, получается противоречие.
С другой стороны, вручную для конкретного языка можно определить колмогоровскую сложность отдельных строк; стало быть, можно написать программу, которая для некоторых строк вычисляет их энтропию, а на остальных зависает или даёт сигнал, что не может их вычислить.
Можно ли сформировать максимальное перечислимое множество строк, для которой найдётся программа, считающая колмогоровскую сложность этих строк? Вопрос похож на заданный в видео: мы не можем определить энтропию всякой строки, но для некоторых же это сделать можно? Конечно, на такую программу хотелось бы накладывать ограничение, чтобы она сама знала, для каких строк она может посчитать, а для каких — нет.
kluwert
17.07.2015 14:58Понятие Шенноновской энтропии связано с больцмановской (физической) энтропией только огромным желанием связать оные самим Шенноном. Хотя надо отдать должное тов. Шеннону: ему посчастливилось с пользой сделать то, что не удаётся многим дуругим: более-менее содержательно притащить в свою науку кусок соседней. А то по тысячи статей в год выходит, где люди всякой фигнёй занимаются: то, «генетические» алгоритмы оптимизации выдумывают, то «нейроные» сети (якобы так же наш мозг работает, ха-ха!), то тут опять возобновились попытки (зачем-то) тензорную алгебру в обработку сигналов притащить за уши. Только всё впустую. И только шенноновская «энтропия» гордо возвышается над всем этим детским садом :)
tgx
Безусловно в теории информации разночтений нет и под энтропией все понимают шенноновскую энтропию. Хотя, для ресурса с уклоном на популяризацию стоит немного переформулировать первое предложение. Всё-таки понятие энтропии ввели в XIX веке из термодинамических соображений и это сделал Клаузиус. Собственно об этом и говорит сам Шеннон в своей работе A Mathematical Theory of Communication за 1938 год.