Алгоритмический подход

Энтропийный подход в теории информации позволяет ответить на вопрос “Сколько информации содержит объект Y относительно объекта X?” В рамках другого подхода – алгоритмического – можно ответить и на вопрос “Сколько нужно информации, чтобы воссоздать (описать) объект X?”

Как показал Колмогоров, эту задачу можно строго сформулировать не только для стохастических объектов, но и для объектов, имеющих вид последовательности из нулей и единиц. В этом случае теория рекурсивных функций позволяет строго ввести понятие сложности объекта. На этой основе А. Н. Колмогоровым был разработан алгоритмический подход к определению количества информации.

Этот подход основан на теории алгоритмов и предполагает наличие априорной вероятностной меры на множестве сигналов. Пусть имеется слово W в алфавите X. Описанием слова W относительно способа описания f назовем такое слово α
в алфавите 0,1, что f(α)= W, и сложностью этого слова при данном способе f – длину кратчайшего описания. Оказывается, что среди алгоритмических способов описания есть оптимальный (дающий с точностью до константы более короткие описания, чем любой другой). Сложность относительно этого оптимального способа называется колмогоровской сложностью R(W)и определяет количество информации в слове W.

Комбинаторный подход

В алгоритмическом подходе количество информации, содержащейся в слове (последовательности нулей и единиц), по существу, измеряется минимальной длиной программы, необходимой для воспроизведения этого слова (последовательности). Возможно иное измерение количества информации, содержащейся в слове (последовательности из нулей и единиц). Комбинаторный подход, развиваемый В. Гоппа, приводит к “алгебраической теории информации”. Количество информации в последовательности определяется степенью её асимметрии. Пусть имеется алфавит X словадлины n в этом алфавите. На словах действует группа перестановок. Тогда логарифм числа перестановок, переводящий слово в себя, называется θ-информацией этого слова. Чем меньше симметрий в слове, тем больше θ-информации в нем.