Количественная оценка

Однако в теории информации получила использование другая количественная оценка.

где т—число возможных равновероятных выборов (при т=2, Н=1).

То есть для выбора из колоды имеем следующую оценку количества информации, получаемую в результате выбора:

H= 1оg2 32 = 5.

Полученная оценка имеет интересную интерпретацию. Она характеризует число двоичных вопросов, ответы на которые позволяют выбрать либо «да», либо «нет». Для выбора дамы пик такими вопросами будут:

1.Карта красной масти? Ответ «нет» 0.

2.Трефы? Ответ «нет» 0.

3.Одна из четырех старших? Ответ «да» 1.

4.Одна из двух старших? Ответ «нет» 0.

5.Дама? Ответ «да» 1.

Этот выбор можно описать последовательностью из пяти двоичных символов 00101 (0 — нет, 1 — да).

На первый взгляд может показаться, что эта интерпретация не годится в случае, когда количество выборов не равно степени двойки, так как получается нецелое количество вопросов, к примеру, если взять колоду из 36 карт (добавлены шестерки), то можно заметить, что для того, чтобы выяснить у участника «эксперимента», какую карту он выбрал, в ряде случаев понадобится 5 вопросов, как и в предыдущем случае, а в ряде случаев — и 6 вопросов. Усреднение по случаям и дает получаемую по формуле нецелую величину.

где Р_i — вероятность выбора i-го символа алфавита.

В алгоритмической теории информации (раздел теории алго­ритмов) предлагается алгоритмический метод оценки информации в сообщении. Этот метод кратко можно охарактеризовать следующими рассуждениями.

Каждый согласится, что слово 0101…01 сложнее слова 00…0, а слово, где 0 и 1 выбираются из эксперимента — бросания монеты (где 0 — герб, 1 — решка), сложнее обоих предыдущих.

Компьютерная программа, производящая слово из одних нулей, крайне проста: печатать один и тот же символ. Для получения 0101…01 нужна чуть более сложная программа, печатающая символ, противоположный только что напечатанному. Случайная, не обла­дающая ни какими закономерностями последовательность не может быть произведена никакой «короткой» программой. Длина прог­раммы, производящей хаотичную последовательность, должна быть близка к длине последней.

Приведенные рассуждения позволяют предположить, что любому сообщению можно приписать количественную характеристику, отра­жающую сложность (размер) программы, которая позволяет ее произвести. Так как имеется много разных вычислительных машин и разных языков программирования (разных способов задания алгоритма), то для определенности задаются некоторой конкретной вычислительной машиной, например машиной Тьюринга, а предполагаемая количественная характеристика — сложность слова (сообщения) определяется как минимальное число внутренних состояний машины Тьюринга, требующиеся для его воспроизведения. Так же в алгоритмической теории информации используются и другие способы задания сложности.