Урок №8. Подходы к измерению информации.
Клод Шеннон, разрабатывая теорию связи, предложил характеризовать информативность сообщения содержащейся в нём полезной информацией, т. е. той частью сообщения, которая снимает полностью или уменьшает существующую до её получения неопределённость какой-либо ситуации.
Клод Элвуд Шеннон (1916-2001) — американский инженер и математик. Является основателем теории информации, нашедшей применение в современных высокотехнологических системах связи. В 1948 году предложил использовать слово «бит» для обозначения наименьшей единицы информации.
Информация — это снятая неопределенность. Величина неопределённое™ некоторого события — это количество возможных результатов (исходов) данного события.
Сообщение, уменьшающее неопределённость знания в 2 раза, несёт 1 бит информации. Такой подход к измерению информации называют содержательным.
Пример 1. Допустим, вы подбрасываете монету, загадывая, что выпадет: «орёл» или «решка». Перед подбрасыванием монеты неопределённость знания о результате равна двум. Действительно, есть всего два возможных результата этого события (бросания монеты). Эти результаты мы считаем равновероятными, т. к. ни один из них не имеет преимущества перед другим.
После того как конкретный исход стал известен (например, подброшенная монета упала «орлом» вверх), неопределённость уменьшилась в 2 раза. Таким образом, сообщение о том, что подброшенная монета упала «орлом» вверх, несёт в себе 1 бит информации.
Пример 2. Предположим, в книжном шкафу восемь полок. Книга может быть поставлена на любую из них. Сколько бит информации несёт сообщение о том, что книга поставлена на третью полку?
Ответ на этот вопрос можно получить, если дополнить исходное сообщение ещё несколькими сообщениями так, чтобы каждое из них уменьшало неопределённость знания в 2 раза.
Итак, количество возможных результатов (исходов) события, состоящего в том, что книга поставлена в шкаф, равно восьми: 1, 2, 3, 4, 5, б, 7 и 8.
Сообщение «Книга поставлена на полку не выше четвёртой» уменьшает неопределённость знания о результате в два раза. Действительно, после такого сообщения остаётся всего четыре варианта: 1, 2, 3 и 4. Получен один бит информации.
Сообщение «Книга поставлена на полку выше второй» уменьшает неопределённость знания о результате в два раза: после этого сообщения остаётся всего два варианта: 3 и 4. Получен ещё один (второй) бит информации.
Сообщение «Книга поставлена на третью полку» также уменьшает неопределённость знания о результате в два раза. Получен третий бит информации.
Итак, мы построили цепочку сообщений, каждое из которых уменьшало неопределённость знания о результате в два раза, т. е. несло 1 бит информации. Всего было набрано 3 бита информации. Именно столько информации и содержится в сообщении «Книга поставлена на третью полку».
Подумайте, сколько информации содержится в сообщении о том, что книга поставлена на пятую полку. Обоснуйте свой ответ, построив соответствующую цепочку сообщений.
Метод поиска, на каждом шаге которого отбрасывается половина вариантов, называется методом половинного деления. Этот метод широко используется в компьютерных науках.
Пример 3. О результатах футбольного матча между клубами «Спартак» и «Динамо» известно, что больше трёх мячей никто не забил. Всего возможных вариантов счёта матча — 16:
Здесь первая цифра в каждой паре соответствует количеству мячей, забитых командой «Спартак», вторая — командой «Динамо».
Будем считать все варианты равновероятными и отгадывать счёт, задавая вопросы, на которые можно ответить только «да» или «нет». Вопросы будем формулировать так, чтобы количество возможных вариантов счёта каждый раз уменьшалось вдвое. Это позволит нам:
1) обойтись минимальным количеством вопросов;
2) подсчитать, сколько бит информации содержит сообщение о счёте матча.
Вопрос 1. «Спартак» забил больше одного мяча? Предположим, получен ответ «Нет». Такой ответ позволяет не рассматривать варианты, расположенные в нижней части таблицы, т. е. сокращает количество возможных исходов в 2 раза:
Вопрос 2. «Спартак» забил один мяч? Предположим, получен ответ «Да». Такой ответ позволяет не рассматривать варианты, расположенные в верхней строке таблицы, т. е. сокращает количество возможных исходов ещё в 2 раза:
Вопрос 3. «Спартак» пропустил больше одного мяча? Предположим, получен ответ «Нет». Можно отбросить ещё два варианта:
Вопрос 4. «Спартак» пропустил один мяч? Предположим, получен ответ «Да». Получаем единственный вариант:
Итак, нам удалось выяснить счёт матча, задав четыре вопроса, ответ на каждый из которых уменьшал неопределённость результата в два раза, т. е. нёс 1 бит информации. Сообщение о счёте матча несёт четыре бита информации.
Выясните, какому счёту матча будут соответствовать следующие цепочки ответов на поставленные выше вопросы:
1) Да — Да — Да — Да;
2) Нет — Нет — Нет — Нет;
3) Да — Нет — Да — Нет.
Попробуйте придумать такие вопросы, чтобы цепочка ответов
Нет — Да — Нет — Да приводила к счёту 2 : 3.
Вычислять количество информации, содержащееся в сообщении о том, что имел место один из множества равновероятных результатов некоторого события, с помощью метода половинного деления возможно, но затруднительно. Гораздо проще воспользоваться следующей закономерностью.
Количество информации i, содержащееся в сообщении об одном из N равновероятных результатов некоторого события, определяется из формулы:
2i = N.
При N, равном целой степени двойки (2, 4, 8, 16, 32 и т. д.), это уравнение легко решается в уме. Решать такие уравнения при других N вы научитесь чуть позже, в курсе математики 11 класса.
Пример 4. Петя и Вася заинтересовались игрой «Крестики- нолики» на поле п х п. Количество информации, полученное вторым игроком после первого хода первого игрока, составляет 6 бит. Требуется выяснить размеры поля, на котором играют Петя и Вася.
1 байт = 8 бит = 23 бит.
1 Кбайт (килобайт) = 1024 байта = 210 байт = 213 бит.
1 Мбайт (мегабайт) = 1024 Кбайт = 210 Кбайт = 220 байт = = 223 бит.
1 Гбайт (гигабайт) = 1024 Мбайт.
1 Тбайт (терабайт) = 1024 Гбайт.
1 Пбайт (петабайт) = 1024 Тбайт.
Представьте себе, что вы много раз бросаете монету и записываете результат очередного броска как 1 (если монета упала гербом) или 0 (если она упала «решкой»). В результате получится некоторое сообщение — цепочка нулей и единиц: 0101001101001110. Вы наверняка поняли, что здесь используется двоичное кодирование — это сообщение написано на языке, алфавит которого состоит из двух символов (знаков): 0 и 1. Как вы знаете, каждая двоичная цифра несёт 1 бит информации, поэтому полная информация в сообщении 0101001101001110 равна 16 бит.
Теперь представим себе, что нужно закодировать программу для Робота, который умеет выполнять команды «вперёд», «назад», «влево» и «вправо». Для этого можно использовать алфавит, состоящий из 4 символов: ↓↑→←. Сколько информации содержится в сообщении ↑←↑↑→↓↓↓↓→← ? Каждый полученный символ может быть любым из 4 символов алфавита, а для кодирования одного из 4 вариантов требуется уже 2 бита. Поэтому полное сообщение из 11 символов содержит 11 • 2 = 22 бита информации.
Алфавитный подход к оценке количества информации состоит в следующем:
1) определяем мощность алфавита М (количество символов в алфавите);
2) по таблице степеней числа 2 определяем минимальное количество бит информации i, приходящихся на каждый символ сообщения, так чтобы выполнилось условие 2i > М:
3) умножаем i на число символов в сообщении L, это и есть полное количество информации:
I = L • i.
Обратим внимание на две важные особенности алфавитного подхода.
При использовании алфавитного подхода не учитывается, что некоторые символы могут встречаться в сообщении чаще других. Считается, что каждый символ несёт одинаковое количество информации.
Алфавитный подход не учитывает также частоты появления сочетаний символов (например, после гласных букв никогда не встречается мягкий знак).
Кроме того, никак не учитывается смысл сообщения, оно представляет собой просто набор знаков, которые приёмник, возможно, даже не понимает.
При использовании алфавитного подхода смысл сообщения не учитывается. Количество информации определяется только длиной сообщения и мощностью алфавита.
Во многих задачах такой подход очень удобен. Например, для устройств, передающих информацию по сети, её содержание не имеет никакого значения, важен только объём. Почтальону всё равно, что написано в письмах, важно только их количество, которое влияет на вес сумки. Для компьютера все данные — это последовательности нулей и единиц, их смысла он не понимает.
Для вычисления информационного объёма текста чаще всего применяют именно алфавитный подход.
Задача 1. Найдите количество информации на 10 страницах текста (на каждой странице 32 строки по 64 символа) при использовании алфавита из 256 символов.
Решение. Сначала определим информационную ёмкость одного символа. Так как 256 = 28, один символ несёт i = 8 бит, или 1 байт информации.
Вычислим общее количество символов L. На одной странице содержится
32 • 64 = 25 • 26 = 211 символов,
тогда во всей книге — L = 10 • 211 символов. Информационный объём текста равен
I = L-i = 10 • 211 • 1 байт = 10 • 211 • (1/210 Кбайт) = 20 Кбайт.
Ответ: 20 Кбайт.
Задача 2. В некоторой стране автомобильный номер длиной 6 символов составляется из прописных букв (всего используется 12 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер — одинаковым и минимально возможным целым количеством байт. Сколько байт памяти необходимо для хранения 10 автомобильных номеров?
Решение. Для записи номера используется 12 различных букв и 10 цифр (0..9), так что алфавит состоит из 22 знаков. Для кодирования одного знака требуется не менее 5 бит (24 = 16 < 22 < 32 = 25), поэтому на весь номер необходимо 6 • 5 = 30 бит.
По условию на каждый номер выделяется целое число байт, поэтому берём ближайшее значение, которое содержит не менее 30 бит, это 4 байта (32 бита). Для хранения 10 номеров нужно выделить 10 • 4 = 40 байт.
Ответ: 40 байт.
Задача 3. Для регистрации на сайте некоторой страны пользователю требуется придумать пароль длиной не более 11 символов. В качестве символов используются десятичные цифры и 12 различных букв местного алфавита, причём все буквы используются в двух регистрах: как строчные, так и прописные (регистр буквы имеет значение!). Для хранения каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байт, при этом используется посимвольное кодирование, и все символы кодируются одинаковым и минимально возможным количеством бит. Сколько байт памяти необходимо для хранения 60 паролей?
Решение. По условию в пароле можно использовать 10 цифр (0..9) + 12 прописных букв местного алфавита + 12 строчных букв, всего 10 + 12 + 12 = 34 символа. Для кодирования одного из 34 символов нужно выделить 6 бит памяти, так как 25 = 32 < 34 < 26 = 64 (5 бит не хватает, а 6 — достаточно).
Для хранения всех 11 символов пароля нужно 11 • 6 = 66 бит. Поскольку пароль должен занимать целое число байт, берём ближайшее значение, содержащее не меньше, чем 66 бит: это 9 байт (72 бита). На 60 паролей нужен выделить 60 • 9 = 540 байт.
Ответ: 540 байт.