Измерение количества информации.

Ранее отмечалось, что информация в рамках информатики не определяется через другие, более простые, понятия. Более того, широкое трактование этого понятия позволяет определить информацию и информационные процессы, как все, что окружает человека: расположение материальных предметов, законы природы, социальные явления и др. Но говоря об информатике, как о науке о преобразовании информации с помощью технических средств, важнейшей проблемой становится измерение количества информации. При этом даже в бытовом обращении слово «информация» используется с такими глаголами, которые предполагают некоторую меру: собрать, запомнить, хранить, преобразовать, передать, получить и даже купить. Рассмотрим основные подходы к определению количества информации.

В 1928 году американским инженером Ральфом Хартли была предложена формула определения количества информации, содержащегося в сообщении длины n. Проиллюстрируем подход к определению количества информации, предложенный Хартли на примере задачи, связанной с угадыванием числа из некоторого интервала: кто-то загадывает число от 0 до 99, а другой должен отгадать его, получая лишь ответы «да» или «нет».

Для решения этой задачи воспользуемся методом деления пополам. Разделим заданный интервал пополам и зададим вопрос: «Число больше?» (можно спросить «Число меньше?»). Любой ответ («Да» и «Нет») сократит область поиска вдвое. Далее по той же схеме диапазон снова делится пополам. В конечном итоге, загаданное число будет найдено.

Посчитаем сколько вопросов надо задать, чтобы найти задуманное число x. Допустим загаданное число x = 79. Начали:

1. Число больше 49? Да

2. Число больше 74? Да

3. Число больше 87? Нет

4. Число больше 81? Нет

5. Число больше 78? Да

6. Число больше 80? Нет

7. Число больше 79? Нет

Если число больше 78 и не больше 79, то это 79.

Чтобы угадать методом «деления пополам» число от 0 до 99 потребовалось 7 вопросов. Может возникнуть сомнение: а почему именно так надо задавать вопросы? Ведь, например, можно просто спрашивать: это число 1? Это число 2? И т. д. Но тогда потребуется намного больше вопросов. Деление пополам самый короткий рациональный способ найти число.

Хартли рассматривал процесс получения информации как выбор одного сообщения из конечного, наперёд заданного, множества из N равновероятных сообщений, а количество информации I, содержащееся в выбранном сообщении, определял как двоичный логарифм N:

I = log ₂ N

Такое определение количества информации называют «формулой Хартли». Количество информации (I), необходимое для определения конкретного элемента, есть логарифм по основанию 2 общего количества элементов (N).

Если возможных событий два (N =2: «да» или «нет», «0» или «1» и др.), то количество информации, необходимое для определения одного из них:

I = log ₂ 2 = 1

По формуле Хартли можно вычислить, какое количество информации требуется для нахождения загаданного числа в задаче, приведенной выше. Всего может быть загадано 100 чисел, т. е. N = 100:

I = log ₂100 » 6,644

Таким образом, сообщение о верно угаданном числе содержит количество информации, приблизительно равное 6,644 единицы измерения информации. Почему же потребовалось задать 7 вопросов? Из житейского опыта понятно, что задать шесть с половиной вопросов невозможно, но есть и математическое объяснение.

Предположим существует некоторый алфавит А (множество А различных символов). Количество символов, используемых в алфавите (из которых составляется сообщение) обозначим m (в случае показанной задачи m = 2: «Да» или «Нет»). Тогда количество возможных вариантов различных сообщений можно определить как

N = mⁿ, где n – количество символов в сообщении.

Т. е. получив шесть двоичных ответов можно было бы однозначно определить одно из шестидесяти четырех (N = 2⁶ = 64) чисел (символов алфавита), чего недостаточно для решения задачи. А седьмой ответ позволяет расширить определяемый интервал до 128 (2⁷ = 128) различных чисел. Попробуйте самостоятельно угадать число от 0 до 127 методом деления пополам и убедиться, что будет достаточно тех же семи вопросов.

Формулу Хартли можно обобщить, используя понятия алфавит, символ и сообщение:

I = n log ₂ m,

где: n – количество символов в сообщении, m – количество символов в алфавите.

Рассматривая ту же задачу, определим количество информации, содержащееся в сообщении загаданного числа:

Количество символов алфавита m = 10 (цифры от 0 до 9), количество символов в сообщении n = 2 (это может быть «00», «01», …, «98», «99»). Подставив значения в формулу Хартли, получим:

I = 2 × log ₂ 10» 6,644

Необходимо отметить, что формула Хартли справедлива только для равновероятных событий. Кроме загаданного числа, примерами таких событий могут быть: бросание монеты (выпадет «орел» или «решка»), количество букв на странице (четное или нечетное) и др. Однако чаще встречаются события, вероятности наступления которых не одинаковы: вероятность встретить некоторую букву в тексте (буква «о» встречается в русском языке гораздо чаще, чем буква «ы»). Приведем другие примеры не равновероятных событий.

Вы звоните на домашний телефон своему другу. Возьмет он трубку или нет, зависит от многих обстоятельств. Если звонить в то время, когда друг должен быть на работе, вероятность, что он ответит минимальна (но не равна нулю, т. к. он мог заболеть и остаться дома). Другими словами, если друг не ответит, Вы не удивитесь – такой результат вполне ожидаем и количество информации, полученной в ходе проведения такого опыта мало.

Или рассмотрим вероятность получения зачета «автоматом». Если студент пропускал занятия, не выполнял требования преподавателя, получал неудовлетворительные оценки за контрольные работы, то вероятность получения «автомата» практически равна нулю.

Для задач такого рода американский математик Клод Шеннон предложил в 1948 г. другую формулу определения количества информации, учитывающую возможную неодинаковую вероятность сообщений в наборе.

Исследуя проблему рациональной передачи информации через зашумлённый коммуникационный канал, Шеннон предложил революционный вероятностный подход к пониманию коммуникаций и создал первую, истинно математическую, теорию энтропии – меры неопределённости или непредсказуемости системы (неопределённости появления какого-либо символа первичного алфавита). Его идеи послужили основой разработки не только теории информации, которая использует понятие вероятности и эргодическую теорию для изучения статистических характеристик данных и коммуникационных систем, но и теории кодирования, в которой используются главным образом алгебраические и геометрические инструменты для разработки эффективных кодов.

Рассматривая кибернетический (предложенный Шенноном) подход к определению количества информации, приведем математическое определение энтропии. Энтропия для независимых случайных событий рассчитывается по формуле:

.

где p_i – вероятность наступление i -го события из N возможных. Эта величина также называется средней энтропией сообщения.

В качестве примера приведем опыт, связанный с бросанием правильной игральной кости, имеющей N граней, пронумерованных от 1 до N (самый распространенный случай N = 6). Несмотря на то, что вероятность выпадения каждой из граней одинакова, этот пример хорошо иллюстрирует идею Шеннона.

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

1. Готовимся бросить кость. Исход опыта неизвестен, т. е. имеется некоторая неопределенность. Обозначим ее H₁. Ее числовое значение можно найти по приведенной выше формуле, учитывая, что N = 6, а p ₁ = p ₂ = p ₃ = p ₄ = p ₅ = p ₆ = 1/6 (если, конечно, кость не шулерская).

2. Кость брошена. Информация об исходе данного опыта получена. Обозначим количество этой информации I.

3. Обозначим неопределенность исхода после проведения опыта H₂.

За количество информации, которое получено в ходе проведения опыта, принимается разность неопределенностей, имевших место до и после опыта:

I = H ₁ – H ₂

Очевидно, что в случае, когда получен конкретный результат, имевшаяся неопределенность полностью снята (H ₂ = 0), и количество полученной информации равно первоначальной энтропии. Другими словами, информация об исходе опыта совпадает с неопределенностью, заключенной в опыте. Заметим, что H ₂ могло быть отлично от нуля. Например, сообщим, что в результате проведения опыта выпала грань с цифрой больше трех. Четыре, пять или шесть? В этом случае рассчитаем H ₂ для N = 3, а p ₁ = p ₂ = p ₃ = 1/3.

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

I = – (p ₁ log ₂ p ₁ + p ₂ log ₂ p ₂ +... + p_N log ₂ p_N)

Не трудно заметить, что если вероятности p ₁,..., p_N равны, то каждая из них равна 1/ N, и формула Шеннона превращается в формулу Хартли.

В качестве единицы информации Клод Шеннон предложил принять один бит (англ. bit – binary digit – двоичная цифра). Это количество информации, связанное с проведением опыта, состоящего в получении одного из двух равновероятных исходов.

Пример. Сколько бит содержит произвольное трехзначное число?

Первый вариант решения. Всего таких чисел 900: от 100 до 999. Значит, I=log₂900 = 9.82 (бит).

Второй вариант. Первая цифра трехзначного числа имеет 9 различных состояний: от 1 до 9, вторая и третья цифры по 10 значений: от 0 до 9. Значит,
I = log₂9 + 2·log₂10 = 3.18+6.64 = 9.82 (бит).

Клод Шеннон является одним из основоположников кибернетики, а развитый им подход к измерению количества информации называют кибернетическим. Далее рассмотрим объемный подход, к которому привели работы по созданию первых ЭВМ.

С точки зрения технического устройства, будь то компьютер или канал связи, измерять количество информации достаточно просто. Информацией считается любая хранящаяся, обрабатываемая или передаваемая последовательность знаков, сигналов и т. д. Объемный подход к измерению количества информации заключается в подсчете числа символов в сообщении.

Аппаратная реализация ЭВМ предусматривает двоичное представление и данных, и команд их обработки, и адресов памяти. Это связано с тем, что в техническом устройстве наиболее просто реализовать некоторый физический элемент, имеющий два различных состояния, например: ферритовое колечко намагничено в одном направлении или в другом, диод открыт или закрыт, конденсатор заряжен или не заряжен и т. п. Очевидно, бит является наименьшей возможной и неделимой единицей информации (в отличие от кибернетического подхода, где количество информации может выражаться любым вещественным числом).

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

Для реализации этой возможности принято использование двоичных слов, состоящих из восьми символов (8 бит) и называемых байтами. С помощью одного байта можно закодировать 2⁸ = 256 различных символов.

Все IBM-совместимые компьютеры используют стандартную таблицу ASCII (American Standard Code for Information Interchange), в которой каждой букве алфавита, цифре или другому символу присвоен определенный цифровой код. Кодированию текстовой и числовой информации будет уделено особое внимание. В рамках текущего занятия подчеркнем, что для представления любого символа естественного алфавита используется 1 байт, состоящий из восьми бит.

Учитывая факт, что на страницу формата А4 умещается около 2000 символов, становится очевидной необходимость использования кратных величин для представления информации. Рассмотрим эти величины в порядке возрастания.

1024 байта образуют килобайт (Кб). Ввиду использования двоичной системы счисления было выбрано число, являющееся степенью цифры два, наиболее близкое к тысяче (2¹⁰ = 1024).

Аналогично:

1024 Кб = 1 мегабайт (Мб)

1024 Мб = 1 гигабайт (Гб)

1024 Гб = 1 терабайт (Тб)

1024 Тб = 1 петабайт (Пб)

1024 Пб = 1 экзабайт (Эб)

3 Мб = 3 × 1024 × 1024 × 8 = 25165824 бит

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

· 2 Кбайт – машинописная страница;

· 100 Кбайт – фотография с низким разрешением;

· 1 Мбайт – небольшой роман или один флоппи-диск;

· 2-4 Мбайт – фотография с высоким разрешением;

· 5 Мбайт – собрание работ Шекспира;

· 10 Мбайт – минута аудиозаписи высокого качества;

· 100 Мбайт – полка книг длиной 1 метр;

· 700 Мбайт – CD-ROM;

· 1 Гбайт – грузовик книг;

· 20 Гбайт – запись всех сочинений Бетховена;

· 100 Гбайт – библиотечное собрание академических журналов;

· 1 Тбайт – текст, который может быть напечатан на бумаге, на которую пошло 50 тыс. деревьев;

· 2 Тбайт – крупная академическая библиотека;

· 10 Тбайт – печатные материалы библиотеки Конгресса США;

· 400 Тбайт – база данных Национального климатического центра США;

· 2 Пбайт – все академические библиотеки США;

· 20 Пбайт – емкость всех жестких дисков, выпущенных в 1995 году;

· 200 Пбайт – все когда-либо напечатанные материалы;

· 2 Эбайт – общее количество данных, произведенное в 1999 году;

· 5 Эбайт – количество слов, высказанное человечеством за все время его существования.

Аналитики из Калифорнийского университета утверждают, что человечеству потребовалось 300 тысяч лет, чтобы создать первые 12 экзабайт информации, зато вторые 12 экзабайт были созданы всего за два года

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

В прикладной информатике практически всегда количество информации понимается в объемном смысле.

Не нашли, что искали? Воспользуйтесь поиском: