Содержание урока
Формула Хартли
Задачи
Информация и вероятность
Вопросы и задания
Задачи
Формула Шеннона
Вопросы и задания
Задачи
Формула Хартли
Вы знаете, что при выборе из двух возможных вариантов количество полученной информации равно 1 биту. Если количество вариантов N равно 2I, то количество информации при выборе одного из них равно I битов. А как вычислить количество информации, если количество вариантов не равно степени числа 2?
Ответить на этот вопрос стало возможно только после того, как вы изучили логарифмы в курсе математики. Из формулы
N = 2I
сразу следует, что I — это степень, в которую нужно возвести 2, чтобы получить N, т. е. логарифм:
I = log2 N.
Эта формула называется формулой Хартли в честь американского инженера Ральфа Хартли, который предложил её в 1928 г.
Пусть, например, на лётном поле стоят 10 самолётов (с номерами от 1 до 10) и известно, что один из них летит в Санкт-Петербург.
Сколько информации в сообщении «Самолёт № 2 летит в Санкт-Петербург»? У нас есть 10 вариантов, из которых выбирается один, поэтому по формуле Хартли количество информации равно
I = log2 10 ≈ 3,322 бита.
Обратите внимание, что для значений N, которые не равны целой степени числа 2, количество информации в битах — дробное число.
С помощью формулы Хартли можно вычислить теоретическое количество информации в сообщении. Предположим, что алфавит (полный набор допустимых символов) включает 50 символов (в этом случае говорят, что мощность алфавита равна 50). Тогда информация при получении каждого символа составляет
I = log2 50 ≈ 5,644 бита.
Если сообщение содержит 100 символов, его общий информационный объём примерно равен
5,644 • 100 = 564,4 бита.
В общем случае объём сообщения длиной L символов, использующего алфавит из N символов, равен I = L • log2 N.
Такой подход к определению количества информации называют алфавитным. Конечно, на практике невозможно использовать для кодирования символа нецелое число битов, поэтому используют первое целое число, которое больше теоретически рассчитанного значения. Например, при использовании алфавита из 50 символов каждый символ будет закодирован с помощью 6 битов (50 ≤ 26 = 64).
Сколько разных сообщений можно передать, если известен алфавит и длина сообщения? Предположим, что для кодирования сообщения используются 4 буквы, например «А», «Б», «В» и «Г», и сообщение состоит из двух символов. Поскольку каждый символ может быть выбран 4 разными способами, на каждый вариант выбора первого символа есть 4 варианта выбора второго. Поэтому общее число разных двухбуквенных сообщений вычисляется как 4 • 4 = 42 = 16. Если в сообщение добавить ещё один символ, то для каждой из 16 комбинаций первых двух символов третий можно выбрать четырьмя способами, так что число разных трёхсимвольных сообщений равно 4 • 4 • 4 = 43 = 64.
В общем случае, если используется алфавит из N символов, то количество разных возможных сообщений длиной L символов равно Q = NL.
Задачи
1. В русском лото 99 бочонков. Какое количество информации содержится в сообщении «Первым вытащили бочонок с номером 16»?
2. В классе 25 учеников. Какое количество информации содержится в сообщении «Сегодня дежурит Василий Иванов»?
3. В чём состоит алфавитный подход к оценке количества информации?
4. Оцените теоретическое количество информации в сообщении «Приеду в четверг». Используемый алфавит состоит из заглавных и строчных русских букв и пробела.
5. Каков будет фактический объём сообщения «Приеду в четверг», если при передаче каждый символ кодируется минимально возможным целым числом битов?
6. В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством битов, а каждый номер — одинаковым и минимально возможным количеством байтов. Определите объём памяти, необходимый для хранения 20 автомобильных номеров.
7. Объём сообщения, содержащего 4096 символов, равен 1/512 части мегабайта. Какова мощность алфавита, с помощью которого записано это сообщение?
8. Какое наименьшее число символов должно быть в алфавите, чтобы с помощью всевозможных трёхбуквенных слов, состоящих из символов данного алфавита, можно было передать не менее 9 различных сообщений?
Информация и вероятность
Всё, что написано в предыдущем пункте, верно только при одном уточнении: все события (символы алфавита) одинаково ожидаемы, т. е. нельзя заранее сказать, что какой-то символ встречается чаще, а какой-то — реже. В реальности это предположение не всегда верно. Например, в тексте на русском языке некоторые символы встречаются часто, а некоторые — очень редко. Числа во втором столбце табл. 1.1 означают относительную долю символа в больших текстах. Например, доля 0,175 для пробела означает, что примерно 17,5% всех символов в текстах на русском языке — пробелы.
Иногда среди всех возможных событий есть ожидаемые и неожиданные. Например, на вопрос «Идёт ли сейчас снег?» летом мы ожидаем услышать ответ «Нет». При этом ответ «Да» будет очень неожиданным, и после его получения наши дальнейшие планы могут сильно измениться. Это значит, что при таком ответе мы получаем гораздо больше информации. Как её измерить точно?
Сначала нужно разобраться с тем, что значит «менее ожидаемое» событие и «более ожидаемое». Математики в этом случае используют понятие «вероятность»: если событие более ожидаемое, то его вероятность (точнее, вероятность того, что оно произойдёт) больше.
Вероятность — это число в интервале от 0 до 1. В математике вероятность принято обозначать буквой р (от латинского probabi- lis — вероятный, возможный).
Сначала рассмотрим предельные случаи, когда вероятность равна 0 или 1. Пусть, например, х — некоторое неизвестное вещественное число, которое задумал ведущий. Вы знаете, что для любого вещественного х всегда х2 ≥ 0. В этом случае считают, что вероятность события х2 ≥ 0 равна 1 (событие х2 ≥ 0 обязательно произойдёт). Часто вероятность измеряют в процентах от 1, тогда вероятность события х2 ≥ 0 равна 100%. В то же время вероятность события х2 < 0 равна нулю, это значит, что событие х2 < 0 никогда не произойдёт.
Теперь предположим, что мы бросаем монету и смотрим, какой стороной она упала, «орлом» или «решкой». Если повторять этот опыт много раз, мы заметим, что количество «орлов» и «решек» примерно равно (конечно, если монета не имеет дефектов). При этом вероятность каждого из двух событий равна 0,5, или 50%. Скорее всего, вы слышали выражение «50 на 50», которое означает, что ни одному из двух вариантов нельзя отдать предпочтение — их вероятности равны.
Вероятность события можно определить с помощью большого количества испытаний. Если из N испытаний нужное нам событие случилось m раз, то вероятность такого события можно оценить как m/N. Например, классический игральный кубик имеет 6 граней; если кубик качественный, вероятность выпадения каждой грани равна 1/6. Вероятность выпадения чётного числа можно подсчитать так: среди чисел от 1 до 6 всего 3 чётных числа, поэтому при большом числе испытаний в половине случаев (в 3 из 6) будут выпадать чётные числа, т. е. вероятность равна 0,5. А вероятность выпадения числа, меньшего 3, равна 2/6 = = 1/3 ≈ 0,33, потому что только 2 из 6 чисел (1 и 2) удовлетворяют условию.
Теперь можно переходить к главному вопросу: как вычислить количество информации, если в сообщении получен символ, вероятность появления которого равна р. Попробуем сначала определить, какими свойствами должна обладать эта величина, исходя из «здравого смысла».
Во-первых, чем меньше вероятность, тем более неожидан символ и тем больше информации мы получили. Если вероятность события близка к нулю, количество информации должно стремиться к бесконечности (получение такого символа очень неожиданно).
Во-вторых, представим себе, что мы получаем символы только одного вида, например только буквы «А». Тогда вероятность появления символа «А» равна 1 и никакой новой информации в этом символе для нас нет — мы всё заранее знали. Следовательно, при р = 1 информация должна быть равна нулю.
В-третьих, «здравый смысл» подсказывает, что когда мы бросаем игральный кубик два (три, 102, 1002) раза, мы получаем информации в два (три, 102, 1002) раза больше, чем при однократном бросании кубика. Это свойство называют принципом аддитивности (сложения).
Математики доказали, что этими свойствами обладает только логарифмическая функция вида f(p) = -К • log2 p, где коэффициент К можно выбирать произвольно, как удобно в конкретной задаче. Если взять К = 1, мы получим количество информации в битах.
Если событие имеет вероятность р, то количество информации в битах, полученное в сообщении об этом событии, равно
Поскольку вероятность р не больше 1, количество информации не может быть меньше нуля. Легко проверить, что если вероятность равна 1, то количество полученной информации равно нулю. Если вероятность стремится к 0, величина log2p стремится к -∞, а количество информации — к ∞.
Третье свойство (аддитивность, сложение вероятностей) проверим на примере. Пусть есть два мешка, в каждом из которых лежат 8 шариков разного цвета. Вычислим, какое количество информации мы получили из сообщения «Из первого мешка вытащили (наугад) красный шарик, а из второго — зелёный». Из каждого мешка можно вытащить один из восьми шариков, т. е. вероятность вытащить какой-то определённый шарик равна 1/8. Следовательно, количество информации в сообщении «Из первого мешка вытащили красный шарик» равно
Точно такую же информацию, 3 бита, мы получаем из сообщения «Из второго мешка вытащили зелёный шарик».
Теперь посмотрим, какое количество информации несёт исходное полное сообщение «Из первого мешка вытащили (наугад) красный шарик, а из второго — зелёный». Какова вероятность именно этого исхода? Есть 8 способов вытащить шарик из каждого мешка, всего получаем 8 • 8 = 64 варианта, поэтому вероятность каждого из них равна 1/64. Тогда количество информации в сообщении равно
т. е. равно сумме количеств информации в двух отдельных сообщениях. Мы показали, что свойство аддитивности выполняется.
Возможно, вы уже заметили, что последний пример фактически свёлся к использованию формулы Хартли. Если все N вариантов имеют равные вероятности, то вероятность каждого варианта равна р = 1/N, следовательно, количество информации о любом из N возможных событий вычисляется как
Этот результат совпадает с формулой Хартли.
Однако формулу Хартли нельзя использовать, если вероятности событий разные. Пусть, например, детям раздают воздушные шарики разного цвета, причём 7 из каждых 10 шариков — зелёные. Какое количество информации содержится в сообщении «Маша получила зелёный шарик»? Здесь формула Хартли неприменима, однако можно использовать формулу (1). Вероятность того, что Маше достался зелёный шарик, равна 7/10, а количество информации вычисляется как
Величина под знаком двоичного логарифма не является степенью двойки. Как её вычислить? Для этого используется свойство логарифма, позволяющее переходить к другому основанию, например, к десятичным или натуральным логарифмам, которые умеют вычислять калькуляторы:
В данном случае получаем
Вопросы и задания
1. Как вы понимаете термин «вероятность события»?
2. В каких случаях вероятность равна 1? Когда она равна 0?
3. Что неправильно в сообщении: «"Спартак" выиграет с вероятностью 200%»?
Задачи
1. Вероятность появления символа @ в некотором тексте равна 0,125. Сколько битов информации несёт сообщение о том, что очередной символ текста — @?
2. В садке у рыбака сидят 2 окуня, 4 плотвы и 10 уклеек. Не смотря в садок, рыбак вытаскивает наугад одну рыбу. Какова вероятность того, что это будет плотва?
3. В пруду плавают 10 линей, 20 окуней и 70 карасей. Считаем, что они одинаково голодны и равномерно распределены по водоёму. Какова вероятность того, что первая рыба, пойманная рыбаком, будет линем? Окунем? Карасём?
4. Ученик задумал целое число от 1 до 100. Какова вероятность того, что это будет число в интервале от 21 до 30? От 31 до 55? Больше 25? Равно 25?
5. Ученик задумал целое число от -10 до 10. Какова вероятность того, что квадрат этого числа больше 25? Меньше 10? Равен 49?
6. В корзине лежат 8 чёрных шаров и 24 белых. Какова вероятность вытащить чёрный шар? Сколько битов информации несёт сообщение о том, что достали чёрный шар?
7. В корзине лежат 32 клубка шерсти, из них 4 красных. Сколько битов информации несёт сообщение о том, что достали клубок красной шерсти?
8. В коробке лежат 64 цветных карандаша. Сообщение о том, что достали белый карандаш, несёт 4 бита информации. Сколько белых карандашей было в коробке?
9. В ящике лежат чёрные и белые перчатки. Среди них 2 пары чёрных. Сообщение о том, что достали чёрные перчатки, несет 4 бита информации. Сколько всего пар перчаток было в ящике?
10. За контрольную работу в классе из 30 человек выставлено 6 пятёрок, 15 четвёрок, 8 троек и 1 двойка. Сколько битов информации несёт сообщение о том, что Иван Петров получил четвёрку?
11. В ящике лежат 20 шаров, из них 10 чёрных, 5 белых, 4 жёлтых и 1 красный. Сколько битов информации несёт сообщение о том, что достали белый шар?
12. За четверть ученик получил 20 оценок. Сообщение о том, что он вчера получил четвёрку, несёт 2 бита информации. Сколько четвёрок получил ученик за четверть?
13. В корзине лежат чёрные и белые шары. Среди них 18 чёрных шаров. Сообщение о том, что достали белый шар, несёт 2 бита информации. Сколько всего шаров было в корзине?
14. В алфавите языка племени тумба-юмба 4 буквы: гласные О и А, согласные Ш и Щ. Вероятности их появления в тексте: А — 0,35; О — 0,4; Ш — 0,1; Щ — 0,15. Сколько битов информации несёт сообщение о том, что очередной символ текста — согласная?
*15. Автобус № 25 ходит в 2 раза чаще, чем автобус № 13. Сообщение о том, что к остановке подошел автобус № 25, несет 4 бита информации. Сколько битов информации в сообщении «К остановке подошел автобус № 13»?
*16. В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян заболела. Сообщение «Заболела обезьяна из вольера А» содержит 4 бита информации. Сколько обезьян живут в вольере Б?
Формула Шеннона
Информация играет для нас важную роль потому, что наше знание всегда неполно, в нём есть неопределенность. Эта неопределённость мешает нам решать свои задачи, принимать правильные решения. Полученная информация уменьшает («снимает») неопределённость, полностью или частично. Поэтому количество полученной информации можно оценить по величине уменьшения неопределенности:
где ННАЧ — начальная неопределённость, а НКОН — конечная (после получения сообщения).
Если неопределённость полностью снимается, то НКОН = 0.
Чтобы оценить информацию с этой точки зрения, нужно как-то вычислить неопределённость, выразить её числом. Эту задачу решил в 1948 г. американский математик Клод Шеннон.
Пусть неопределённость состоит в том, что мы можем получить одно из N возможных сообщений, причём известно, что вероятность получения сообщения с номером i равна рi.
Неопределённость знания об источнике данных вычисляется по формуле Шеннона
Величина Н часто называется информационной энтропией. С точки зрения математики это среднее количество информации, которую мы получаем при полном снятии неопределённости (когда выбран один из возможных вариантов).
Когда неопределённость наибольшая? Зададим вопрос «Идёт ли сейчас снег?» зимой и летом. Летом неопределённость очень маленькая, так как, скорее всего, снега нет, ситуация ясна. Зимой же неопределённость велика, потому что снег может идти или не идти примерно с равной вероятностью.
Перейдём к числам. Будем считать, что вероятность снега зимой равна P1 = 0,5. Чему равна вероятность р2 того, что снега нет? «Здравый смысл» подсказывает, что р2 = 0,5 (остальные 50%). Математики говорят, что два события, «Снег идёт» и «Снега нет», составляют полную систему. Это значит, что обязательно случится какое-нибудь одно из этих событий, и при этом другое точно не произойдёт. Слово «обязательно» означает, что вероятность этих двух событий в сумме равна 1.
Сумма вероятностей всех событий, составляющих полную систему, равна 1.
Для «зимнего» случая количество информации при получении сообщений «Снег идёт» и «Снега нет» одинаковое, потому что их вероятности одинаковые:
Неопределённость, вычисленная по формуле Шеннона, также равна 1 биту:
Для лета будем считать вероятность выпадения снега равной р1 = 0,0001. Тогда вероятность того, что снега нет, равна р2 = 1 - 0,0001 = 0,9999. Сообщения «Снег идёт» и «Снега нет» несут разное количество информации:
а неопределённость (среднее количество информации) равна
Мы получили то, что ожидали: зимой неопределённость в ответе на вопрос «Идёт ли сейчас снег?» значительно больше, чем летом. Можно предположить (и это действительно так), что неопределённость наибольшая в том случае, когда вероятности всех событий равны.
Летом эта неопределённость очень близка к нулю, поэтому можно предположить (и это также верно), что она стремится к нулю, если вероятность одного из двух событий стремится к нулю.
На рисунке 1.1 построена зависимость величины неопределённое Н от вероятности первого события p1. При этом вероятность второго события определяется как р2 = 1 - p1, так как они составляют полную систему. Главный вывод этого примера таков:
Неопределённость наибольшая для случая, когда все события равновероятны.
Рис. 1.1
При этом вероятность каждого из N событий равна р = 1/N, поэтому по формуле Шеннона
Отсюда следует, что:
При равновероятных событиях неопределённость совпадает с количеством информации, вычисленной по формуле Хартли.
Вопросы и задания
1. В чём заключается неопределённость?
2. Как связана неопределённость с информацией, которую мы получаем при сообщении об отдельных событиях?
3. Что такое полная система событий?
4. Что можно сказать о вероятностях событий, входящих в полную систему?
5. В каком случае неопределённость наибольшая?
6. В каком случае неопределённость стремится к нулю?
7. В каком случае неопределённость совпадает с количеством информации, вычисленным по формуле Хартли?
Задачи
1. Из аэропорта Куково можно улететь на самолетах Ту-154, АН-148, Боинг-737. Вероятность полёта на самолёте Ту-154 равна 0,6; вероятность полёта на Боинге-737 равна 0,1. Чему равна вероятность полёта на АН-148?
2. В коробке 3 красных карандаша и 7 синих. Чему равна неопределённость при выборе наугад одного карандаша из коробки?
3. На улице Строителей из 20 домов 6 деревянных, 8 сделаны из кирпича, а оставшиеся — из железобетонных плит. Чему равна неопределённость ответа на вопрос «Из чего сделан дом № 16 на улице Строителей»?