2015-03-22
2563
Для теоретической информатики информация играет такую же ль, как и эещество в физике. И подобно тому, как веществу можно описывать довольно большое количество характеристик: массу,
заряд, объем и т. д., так и для информации имеется пусть и не столь большой, но достаточно представительный набор характеристик. Как и для характеристик вещества, так и для характеристик информации имеются единицы измерения, что позволяет некоторой порции информации приписывать числа — количественные характеристики информации.
На сегодняшний день наиболее известны следующие способы измерения информации:
объемный,
энтропийный,
алгоритмический.
Объемный является самым простым и грубым способом измерения информации. Соответствующую количественную оценку информации естественно назвать объемом информации.
Объем информации в сообщении — это количество символов в сообщении. Поскольку, например, одно и то же число может быть записано многими разными способами (с использованием разных алфавитов):
«двадцать один»
XXI,
то этот способ чувствителен к форме представления (записи) сообщения. В вычислительной технике вся обрабатываемая и хра нимая информация вне зависимости от ее природы (число, текст, отображение) представлена в двоичной форме (с использованием алфавита, состоящего всего из двух символов 0 и 1). Такая стандартизация позволила ввести две стандартные единицы измерения: бит и байт. Байт — это восемь бит. Более подробно эти единицы измерения будут рассмотрены в разделе «Формы пред ставления и преобразования информации».
В теории информации и кодирования принят энтропийный подход к измерению информации. Этот способ измерения исходит из следующей модели. Получатель информации (сообщения) имеет определенные представления о возможных наступлениях некоторых событий. Эти представления в общем случае недостоверны и выражаются вероятностями, с которыми он ожидает то или иное
событие. Общая мера неопределенности (энтропия) характеризуется некоторой математической зависимостью от совокупности этих вероятностей. Количество информации в сообщении определяется тем, насколько уменьшится эта мера после получения сообщения.
Поясним эту идею на простом примере. Пусть имеется колода карт, содержащая 32 различные карты. Вероятность выбора одной карты из колоды равна 1/32. Априори (доопытно, до произведения выбора) естественно предположить, что наши шансы выбрать некоторую определенную карту одинаковы для всех карт колоды. Произведя выбор, мы устраняем эту априорную неопределенность. Нашу априорную неопределенность можно было бы охарактери зовать количеством возможных равновероятностных выборов. Если теперь определить количество информации как меру устраненной неопределенности, то и полученную в результате выбора инфор мацию можно охарактеризовать числом 32.
Однако в теории информации получила использование другая количественная оценка, а именно — логарифм от описанной выше оценки по основанию 2:
#=fog3m, (3.1)
где т — число возможных равновероятных выборов (при т = 2,Н=1).
То есть для выбора из колоды имеем следующую оценку количества информации, получаемую в результате выбора:
Я= Iog232 = 5.
Полученная оценка имеет интересную интерпретацию. Она характеризует число двоичных вопросов, ответы на которые позволяют выбрать либо «да», либо «нет». Для выбора дамы пик такими вопросами будут:
1. Карта красной масти? Ответ «нет» 0.
2. Трефы? Ответ «нет» 0.
3. Одна из четырех старших? Ответ «да» 1.
4. Одна из двух старших? < Ответ «нет» О,
5. Дама?. Ответ «да» 1.
Этот выбор можно описать последовательностью из пяти двоичных символов 00101 (0 — нет, 1—да).
На первый взгляд может показаться, что эта интерпретация не годится в случае, когда количество выборов не равно степени двойки, так как получается нецелое количество вопросов, к примеру, если
взять колоду из 36 карт (добавлены шестерки), то можно заметить, что для того, чтобы выяснить у участника «эксперимента», какую карту он выбрал, в ряде случаев понадобится 5 вопросов, как и в предыдущем случае, а в ряде случаев — и 6 вопросов. Усреднение по случаям и дает получаемую по формуле нецелую величину.
К. Шеннону принадлежит обобщение Н на случай, когда Н зависит не только от т, но и от вероятностей возможных выборов (для сообщения — вероятности выбора символов). Для количества собственной индивидуальной информации он предложил соотно шение
где fi - вероятность выоора z-ro символа алфавита.
Более удобно пользоваться средним значением количества информации, приходящимся на один символ алфавита:
При равновероятных выборах все Pt= \lm и получается прежняя формула Н = log т.
В алгоритмической теории информации (раздел теории алго ритмов) предлагается алгоритмический метод оценки информации в сообщении. Этот метод кратко можно охарактеризовать следующими рассуждениями.
Каждый согласится, что слово 0101...01 сложнее слова 00...О, а слово, где 0 и 1 выбираются из эксперимента — бросания монеты (где 0 — герб, 1 — решка), сложнее обоих предыдущих.
Компьютерная программа, производящая слово из одних нулей, крайне проста: печатать один и тот же символ. Для получения 0101...01 нужна чуть более сложная программа, печатающая символ, противоположный только что напечатанному. Случайная, не обла дающая ни какими закономерностями последовательность не может быть произведена никакой «короткой» программой. Длина прог раммы, производящей хаотичную последовательность, должна быть близка к длине последней.
Приведенные рассуждения позволяют предположить, что любому сообщению можно приписать количественную характеристику, отра жающую сложность (размер) программы, которая позволяет ее произвести.
Так как имеется много разных вычислительных машин и разных языков программирования (разных способов задания алгоритма), то для определенности задаются некоторой конкретной вычислительной машиной, например машиной Тьюринга (см. раздел «Теория алгоритмов»), а предполагаемая количественная характеристика — сложность слова (сообщения) определяется как минимальное число внутренних состояний машины Тьюринга, требующиеся для его воспроизведения. Так же в, алгоритмической теории информации используются и другие способы задания сложности.
