Случайные события могут быть описаны с использованием понятия «вероятность». Соотношения теории вероятностей позволяют найти (вычислить) вероятности как одиночных случайных событий, так и сложных опытов, объединяющих несколько независимых или связанных между собой событий. Однако описать случайные события можно не только в терминах вероятностей.

То, что событие случайно, означает отсутствие полной уверенности в его наступлении, что, в свою очередь, создает неопределенность в исходах опытов, связанных с данным событием. Безусловно, степень неопределенности различна для разных ситуаций.

Например, если опыт состоит в определении возраста случайно выбранного студента 1-го курса дневного отделения вуза, то с большой долей уверенности можно утверждать, что он окажется менее 30 лет; хотя по положению на дневном отделении могут обучаться лица в возрасте до 35 лет, чаще всего очно учатся выпускники школ ближайших нескольких выпусков. Гораздо меньшую определенность имеет аналогичный опыт, если проверяется, будет ли возраст произвольно выбранного студента меньше 18 лет. Для практики важно иметь возможность произвести численную оценку неопределенности разных опытов. Попробуем ввести такую количественную меру неопределенности.

Начнем с простой ситуации, когда опыт имеет %%n%% равновероятных исходов. Очевидно, что неопределенность каждого из них зависит от n, т.е.

Мера неопределенности является функцией числа исходов %%f(n)%%.

Можно указать некоторые свойства этой функции:

1. %%f(1) = 0%%, поскольку при %%n = 1%% исход опыта не является случайным и, следовательно, неопределенность отсутствует;
2. %%f(n)%% возрастает с ростом %%n%%, поскольку чем больше число возможных исходов, тем более затруднительным становится предсказание результата опыта.

* Для обозначения опытов со случайными исходами будем использовать греческие буквы (%%α%%, %%β%% и т.д.), а для обозначения отдельных исходов опытов (событий) - латинские заглавные (%%А%%, %%В%% и т.д.).

Для определения явного вида функции %%f(n)%% рассмотрим два независимых опыта %%α%% и %%β*%% с количествами равновероятных исходов, соответственно %%n_α%% и %%n_β%%. Пусть имеет место сложный опыт, который состоит в одновременном выполнении опытов α и β; число возможных его исходов равно %%nα \cdot nβ%%, причем, все они равновероятны. Очевидно, неопределенность исхода такого сложного опыта %%α ^ β%% будет больше неопределенности опыта %%α%%, поскольку к ней добавляется неопределенность %%β%%; мера неопределенности сложного опыта равна %%f(n_α \cdot n_β)%%. С другой стороны, меры неопределенности отдельных %%α%% и %%β%% составляют, соответственно, %%f(n_α)%% и %%f(n_β)%%. В первом случае (сложный опыт) проявляется общая (суммарная) неопределенность совместных событий, во втором - неопределенность каждого из событий в отдельности. Однако из независимости %%α%% и %%β%% следует, что в сложном опыте они никак не могут повлиять друг на друга и, в частности, %%α%% не может оказать воздействия на неопределенность %%β%%, и наоборот. Следовательно, мера суммарной неопределенности должна быть равна сумме мер неопределенности каждого из опытов, т.е. мера неопределенности аддитивна:

$$f(n_α \cdot n_β)=f(n_α)+f(n_β)~~~~~~(2.1)$$

Теперь задумаемся о том, каким может быть явный вид функции %%f(n)%%, чтобы он удовлетворял свойствам (1) и (2) и соотношению (2.1)? Легко увидеть, что такому набору свойств удовлетворяет функция %%log(n)%%, причем можно доказать, что она единственная из всех существующих классов функций. Таким образом:

За меру неопределенности опыта с n равновероятными исходами можно принять число %%log(n)%%.

Следует заметить, что выбор основания логарифма в данном случае значения не имеет, поскольку в силу известной формулы преобразования логарифма от одного основания к другому.

$$log_b n=log_b а\cdot log_a n $$

переход к другому основанию состоит во введении одинакового для обеих частей выражения (2.1) постоянного множителя %%log_b а%%, что равносильно изменению масштаба (т.е. размера единицы) измерения неопределенности. Поскольку это так, имеется возможность выбрать удобное (из каких-то дополнительных соображений) основание логарифма. Таким удобным основанием оказывается 2, поскольку в этом случае за единицу измерения принимается неопределенность, содержащаяся в опыте, имеющем лишь два равновероятных исхода, которые можно обозначить, например, ИСТИНА (True) и ЛОЖЬ (False) и использовать для анализа таких событий аппарат математической логики.

Единица измерения неопределенности при двух возможных равновероятных исходах опыта называется бит .

Название бит происходит от английского binary digit, что в дословном переводе означает «двоичный разряд» или «двоичная единица».

Таким образом, нами установлен явный вид функции, описывающей меру неопределенности опыта, имеющего %%n%% равновероятных исходов:

$$f(n)=log_2 n~~~~~~(2.2)$$

Эта величина получила название энтропия . В дальнейшем будем обозначать ее Н.

Вновь рассмотрим опыт с %%n%% равновероятными исходами. Поскольку каждый исход случаен, он вносит свой вклад в неопределенность всего опыта, но так как все %%n%% исходов равнозначны, разумно допустить, что и их неопределенности одинаковы. Из свойства аддитивности неопределенности, а также того, что согласно (2.2) общая неопределенность равна %%log_2 n%%, следует, что неопределенность, вносимая одним исходом составляет

$$\frac{1}{n}log_2 n = - \frac{1}{n}log_2 \frac{1}{n} = -p \cdot log_2 p $$

где %%р =\frac{1}{n}%% - вероятность любого из отдельных исходов.

Таким образом, неопределенность, вносимая каждым из равновероятных исходов, равна:

$$H=-p \cdot log_2 p~~~~~~~~~~~~(2.3)$$

Теперь попробуем обобщить формулу (2.3) на ситуацию, когда исходы опытов неравновероятны, например, %%p(A_1)%% и %%p(A_2)%%. Тогда:

$$H_1=-p(А_1) \cdot log_2 р(А_1)$$ $$H_2=-p(А_2) \cdot log_2 р(А_2)$$

$$H=H_1+H_2=-p(А_1) \cdot log_2 р(А_1)-p(А_2) \cdot log_2 р(А_2)$$

Обобщая это выражение на ситуацию, когда опыт %%α%% имеет %%n%% неравновероятных исходов %%А_1, А_2... А_n%%, получим:

$$H(α)=-\sum^{n}_{i=1} {p(А_i)}\cdot log_2 p(А_i)~~~~~~(2.4)$$

Введенная таким образом величина, как уже было сказано, называется энтропией опыта. Используя формулу для среднего значения дискретных случайных величин, можно записать:

$$H(α)\leqslant -log_2 p(A^α)$$

%%А^α%% - обозначает исходы, возможные в опыте α.

Энтропия является мерой неопределенности опыта, в котором проявляются случайные события, и равна средней неопределенности всех возможных его исходов.

Для практики формула (2.4) важна тем, что позволяет сравнить неопределенности различных опытов со случайными исходами.

Пример 2.1. Имеются два ящика, в каждом из которых по 12 шаров. В первом -3 белых, 3 черных и 6 красных; во втором - каждого цвета по 4. Опыты состоят в вытаскивании по одному шару из каждого ящика. Что можно сказать относительно неопределенностей исходов этих опытов?

Согласно (2.4) находим энтропии обоих опытов:

%%Н_α = -\frac{3}{12}log_2 \frac{3}{12}-\frac{3}{12}log_2 \frac{3}{12}-\frac{6}{12}log_2 \frac{6}{12}=1,50%% бит

%%Н_β = -\frac{4}{12}log_2 \frac{4}{12}-\frac{4}{12}log_2 \frac{4}{12}-\frac{4}{12}log_2 \frac{4}{12}=1,58%% бит

%%Н_β > Н_α%%, т.е. неопределенность результата в опыте β выше и, следовательно, предсказать его можно с меньшей долей уверенности, чем результат α.

Основоположник теории информации Клод Шеннон определил информацию , как снятую неопределенность . Точнее сказать, получение информации - необходимое условие для снятия неопределенности. Неопределенность возникает в ситуации выбора. Задача, которая решается в ходе снятия неопределенности – уменьшение количества рассматриваемых вариантов (уменьшение разнообразия), и в итоге выбор одного соответствующего ситуации варианта из числа возможных. Снятие неопределенности дает возможность принимать обоснованные решения и действовать. В этом управляющая роль информации.

Представьте, что вы зашли в магазин и попросили продать вам жевательную резинку. Продавщица, у которой, скажем, 16 сортов жевательной резинки, находится в состоянии неопределенности. Она не может выполнить вашу просьбу без получения дополнительной информации. Если вы уточнили, скажем, - «Orbit », и из 16 первоначальных вариантов продавщица рассматривает теперь только 8, вы уменьшили ее неопределенность в два раза (забегая вперед, скажем, что уменьшение неопределенности вдвое соответствует получению 1 бита информации). Если вы, не мудрствуя лукаво, просто указали пальцем на витрине, - «вот эту!», то неопределенность была снята полностью. Опять же, забегая вперед, скажем, что этим жестом в данном примере вы сообщили продавщице 4 бита информации.

Ситуация максимальной неопределенности предполагает наличие нескольких равновероятных альтернатив (вариантов), т.е. ни один из вариантов не является более предпочтительным. Причем, чем больше равновероятных вариантов наблюдается, тем больше неопределенность, тем сложнее сделать однозначный выбор и тем больше информации требуется для этого получить. Для N вариантов эта ситуация описывается следующим распределением вероятностей: {1/N , 1/N , … 1/N }.

Минимальная неопределенность равна 0 , т.е. эта ситуация полной определенности , означающая что выбор сделан, и вся необходимая информация получена. Распределение вероятностей для ситуации полной определенности выглядит так: {1, 0, …0} .

Величина, характеризующая количество неопределенности в теории информации обозначается символом H и имеет название энтропия, точнее информационная энтропия .

Энтропия (H ) – мера неопределенности, выраженная в битах. Так же энтропию можно рассматривать как меру равномерности распределения случайной величины.

На рисунке 8. показано поведение энтропии для случая двух альтернатив, при изменении соотношения их вероятностей (p , (1-p )).

Максимального значения энтропия достигает в данном случае тогда, когда обе вероятности равны между собой и равны ½, нулевое значение энтропии соответствует случаям (p 0 =0, p 1 =1) и (p 0 =1, p 1 =0).

Количество информации I и энтропия H характеризуют одну и ту же ситуацию, но с качественно противоположенных сторон. I – это количество информации, которое требуется для снятия неопределенности H . По определению Леона Бриллюэна информация есть отрицательная энтропия (негэнтропия) .

Когда неопределенность снята полностью, количество полученной информации I равно изначально существовавшей неопределенности H .

При частичном снятии неопределенности, полученное количество информации и оставшаяся неснятой неопределенность составляют в сумме исходную неопределенность. H t + I t = H .

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

Чем больше первоначальная неопределенность знания, тем больше информации несет сообщение, снимающее эту неопределенность.

Приведем примеры, иллюстрирующие данное утверждение.

Ситуация 1. В ваш класс назначен новый учитель информатики; на вопрос «Это мужчина или женщина?» вам ответили: «Мужчина».

Ситуация 2. На чемпионате страны по футболу играли команды «Динамо» и «Зенит». Из спортивных новостей по радио вы узнаете, что игра закончилась победой «Зенита».

Ситуация 3. На выборах мэра города было представлено четыре кандидата. После подведения итогов голосования вы узнали, что избран Н. Н. Никитин.

Вопрос: в какой из трех ситуаций полученное сообщение несет больше информации?

Неопределенность знания - это количество возможных вариантов ответа на интересовавший вас вопрос. Еще можно сказать: возможных исходов события. Здесь событие - например, выборы мэра; исход - выбор, например, Н. Н. Никитина.

В первой ситуации 2 варианта ответа: мужчина, женщина; во второй ситуации 3 варианта: выиграл «Зенит», ничья, выиграло «Динамо»; в третьей ситуации - 4 варианта: 4 кандидата на пост мэра.

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

В 40-х годах XX века проблема измерения информации была решена американским ученым Клодом Шенноном (1916-2001) - основателем теории информации. Согласно Шеннону, информация - это снятая неопределенность знания человека об исходе какого-то события.

В теории информации единица измерения информации определяется следующим образом.

Согласно этому определению, сообщение в первой из описанных ситуаций несет 1 бит информации, поскольку из двух возможных вариантов ответа был выбран один.

Следовательно, количество информации, полученное во второй и в третьей ситуациях, больше, чем один бит. Но как измерить это количество?

Рассмотрим еще один пример.

Ученик написал контрольную по информатике и спрашивает учителя о полученной оценке. Оценка может оказаться любой: от 2 до 5. На что учитель отвечает: «Угадай оценку за два вопроса, ответом на которые может быть только "да" или "нет"». Подумав, ученик задал первый вопрос: «Оценка выше тройки?». «Да», - ответил учитель. Второй вопрос: «Это пятерка?». «Нет», - ответил учитель. Ученик понял, что он получил четверку. Какая бы ни была оценка, таким способом она будет угадана!

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

Узнав оценку (одну из четырех возможных), ученик получил 2 бита информации.

Рассмотрим еще один частный пример, а затем выведем общее правило.

Вы едете на электропоезде, в котором 8 вагонов, а на вокзале вас встречает товарищ. Товарищ позвонил вам по мобильному телефону и спросил, в каком вагоне вы едете. Вы предлагаете угадать номер вагона, задав наименьшее количество вопросов, ответами на которые могут быть только слова «да» или «нет».

Немного подумав, товарищ стал спрашивать:

Номер вагона больше четырех?

Номер вагона больше шести?

Это шестой вагон?

Ну теперь все ясно! Ты едешь в пятом вагоне!

Схематически поиск номера вагона выглядит так:

Каждый ответ уменьшал неопределенность знания в два раза. Всего было задано три вопроса. Значит, в сумме набрано 3 бита информации. То есть сообщение о том, что вы едете в пятом вагоне, несет 3 бита информации.

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

Заметим, что решение подобных проблем методом половинного деления наиболее рационально. Таким способом всегда можно угадать, например, любой из восьми вариантов за 3 вопроса. Если бы поиск производился последовательным перебором: «Ты едешь в первом вагоне?» «Нет», «Во втором вагоне?» «Нет» и т. д., то про пятый вагон вы смогли бы узнать после пяти вопросов, а про восьмой - после восьми.

«Главная формула» информатики

Сформулируем одно очень важное условие, относящееся к рассмотренным примерам. Во всех ситуациях предполагается, что все возможные исходы события равновероятны. Равновероятно, что учитель может быть мужчиной или женщиной; равновероятен любой исход футбольного матча, равновероятен выбор одного из четырех кандидатов в мэры города. То же относится и к примерам с оценками и вагонами.

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

• сообщение об одном из двух равновероятных исходов некоторого события несет 1 бит информации;
• сообщение об одном из четырех равновероятных исходов некоторого события несет 2 бита информации;
• сообщение об одном из восьми равновероятных исходов некоторого события несет 3 бита информации.

Обозначим буквой N количество возможных исходов события, или, как мы это еще называли, - неопределенность знания. Буквой i будем обозначать количество информации в сообщении об одном из N результатов.

В примере с учителем: N = 2, i = 1 бит;

в примере с оценками: N = 4, i = 2 бита;

в примере с вагонами: N = 8, i = 3 бита.

Нетрудно заметить, что связь между этими величинами выражается следующей формулой:

2 i = N. Действительно: 2 1 = 2 ; 2 2 = 4 ; 2 3 = 8.

С полученной формулой вы уже знакомы из курса информатики для 7 класса и еще не однажды с ней встретитесь. Значение этой формулы столь велико, что мы назвали ее главной формулой информатики. Если величина N известна, a i неизвестно, то данная формула становится уравнением для определения i. В математике такое уравнение называется показательным уравнением.

Пример. Вернемся к рассмотренному выше примеру с вагонами. Пусть в поезде не 8, а 16 вагонов. Чтобы ответить на вопрос, какое количество информации содержится в сообщении о номере искомого вагона, нужно решить уравнение:

Поскольку 16 = 2 4 , то i = 4 бита.

Пример. В кинозале 16 рядов, в каждом ряду 32 места. Какое количество информации несет сообщение о том, что вам купили билет на 12-й ряд, 10-е место?

Решение задачи: в кинозале всего 16 32 = 512 мест. Сообщение о купленном билете однозначно определяет выбор одного из этих мест. Из уравнения 2 i = 512 = 29 получаем: i = 9 битов.

Но эту же задачу можно решать иначе. Сообщение о номере ряда несет 4 бита информации, так как 2 4 = 16. Сообщение о номере места несет 5 битов информации, так как 2 5 = 32. В целом сообщение про ряд и место несет: 4 + 5 = 9 битов информации.

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

Сделаем одно важное замечание. С формулой 2 i = N мы уже встречались, обсуждая алфавитный подход к измерению информации (см. § 3). В этом случае N рассматривалось как мощность алфавита, a i - как информационный вес каждого символа алфавита. Если допустить, что все символы алфавита появляются в тексте с одинаковой частотой, т. е. равновероятно, то информационный вес символа i тождественен количеству информации в сообщении о появлении любого символа в тексте. При этом N - неопределенность знания о том, какой именно символ алфавита должен стоять в данной позиции текста. Данный факт демонстрирует связь между алфавитным и содержательным подходами к измерению информации.

Формула Хартли

Если значение N равно целой степени двойки (4, 8, 16, 32, 64 и т. д.), то показательное уравнение легко решить в уме, поскольку i будет целым числом. А чему равно количество информации в сообщении о результате матча «Динамо»-«Зенит»? В этой ситуации N = 3. Можно догадаться, что решение уравнения

будет дробным числом, лежащим между 1 и 2, поскольку 2 1 = 2 < 3, а 2 2 = 4 > 3. А как точнее узнать это число?

В математике существует функция, с помощью которой решается показательное уравнение. Эта функция называется логарифмом, и решение нашего уравнения записывается следующим образом:

Читается это так: «логарифм от N по основанию 2». Смысл очень простой: логарифм по основанию 2 от N - это степень, в которую нужно возвести 2, чтобы получить N. Например, вычисление уже известных вам значений можно представить так:

log 2 2 = 1, log 2 4 = 2, log 2 8 = 3.

Значения логарифмов находятся с помощью специальных логарифмических таблиц. Также можно использовать инженерный калькулятор или табличный процессор. Определим количество информации, полученной из сообщения об одном исходе события из трех равновероятных, с помощью электронной таблицы. На рисунке 1.4 представлены два режима электронной таблицы: режим отображения формул и режим отображения значений.

Рис. 1.4. Определение количества информации в электронных таблицах с помощью функции логарифма

В табличном процессоре Microsoft Excel функция логарифма имеет следующий вид: LOG(apryмент; основание). Аргумент - значение N находится в ячейке А2, а основание логарифма равно 2. В результате получаем с точностью до девяти знаков после запятой: i = log 2 3 = 1,584962501 (бита).

Формула для измерения количества информации: i = log 2 N была предложена американским ученым Ральфом Хартли (1888-1970) - одним из основоположников теории информации.

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

Система основных понятий

Вопросы и задания

1. Что такое неопределенность знания об исходе некоторого события?
2. Как определяется единица измерения количества информации в рамках содержательного подхода?
3. Придумайте несколько ситуаций, при которых сообщение несет 1 бит информации.
4. В каких случаях и по какой формуле можно вычислить количество информации, содержащейся в сообщении, используя содержательный подход?
5. Сколько битов информации несет сообщение о том, что из колоды в 32 карты достали «даму пик»?
6. При угадывании методом половинного деления целого числа из диапазона от 1 до N был получен 1 байт информации. Чему равно N?
7. Проводятся две лотереи: «4 из 32» и «5 из 64». Сообщение о результатах какой из лотерей несет больше информации?
8. Используя формулу Хартли и электронные таблицы, определите количество информации в сообщениях о равновероятных событиях:

   а) на шестигранном игральном кубике выпала цифра 3;

   б) в следующем году ремонт в школе начнется в феврале;

   в) я приобрел абонемент в бассейн на среду;

   г) из 30 учеников класса дежурить в школьной столовой назначили Дениса Скворцова.

9. Используя закон аддитивности количества информации, решите задачу о билете в кинотеатр со следующим дополнительным условием: в кинотеатре 4 зала. В билете указан номер зала, номер ряда и номер места. Какое количество информации заключено в билете?

Информация - это сведения или данные, не содержащая неопределённость для адресата. Если всё же информация содержит некоторую неопределённость, то её можно воспринять только с некоторой вероятностью. Поэтому, при наличии неопределённости, получатель информации каким-либо образом добивается свести к минимуму саму неопределённость. Если при этом удаётся получателю информации исключить неопределённость полностью, то он владеет информацией вполне. Вопросы о том, как это можно делать на практике, являются содержанием данной главы.

КОЛИЧЕСТВЕННАЯ МЕРА НЕОПРЕДЕЛЁННОСТИ

Для сравнения неопределённостей, рассмотрим следующие примеры или опыты a, b и g, содержащие неопределённости H(a), H(b) и H(g) соответственно:

1. Определить очередного чемпиона мира по шахматам (опыт a).

2. Определить номер лотерейного билета, на который выпадет наибольший выигрыш в предстоящем тираже лотереи (опыт b).

3. Определить следующего президента РФ (опыт g).

Очевидно, степень неопределённости каждого опыта отличается от двух других, причём скорее всего имеют место неравенства

H(b) > H(a) > H(g),

где H(a), H(b) и H(g) - количественные меры неопределённостей (или энтропии) опытов a, b и g соответственно. В частном случае, если для некоторого опыта d имеет место равенство H(d) = 0, то говорят, что опыт d достоверный, т.е. он не содержит неопределённости. Другими словами неоределённость опыта есть не что иное как недостача информации или отрицательная информация.

I. Формула Хартли. Пусть a - произвольный опыт с k равновероятными исходами А k

События А 1 А 2 . . . А k

Вероятности 1/ k 1/ k . . . 1/ k .

При k= 1 H(a) = 0, а при возрастании k H(a) также возрастает, т.е.

где f - некоторая функция от k. С другой стороны, если b независимый от a другой опыт с l равновероятными исходами В l , то для сложного опыта ab, состоящего в одновременном выполнении опытов a и b, естественно считать что степень неопределённости опыта ab равна сумме неопределённостей, характеризующих опыты a и b, т.е.

H(ab) = H(a) + H(b).

Таким образом, в качестве функции f можно выбрать логарифмическую функцию и считать, что

H(a) = log 2 k .

Это есть формула Хартли и она представляет собой меру неопределённости относительно опыта a, содержащимся в опыте a и имеющим два равновероятных исхода (например,"да" или "нет"). Другими словами, H(a) это то количество информации (за единицей измерения количества информации считается бит), с помощью которого неопределённость опыта a превращается в достоверность.

Так, например, для угадывания задуманного числа в диапазоне от 1 до 8 необходимо максимум 3 бит информации, т.е. необходимо задать три вопроса.

II. Формула Шеннона. Пусть a - произвольный опыт с к неравновероятными исходами А к:

События А 1 А 2 . . . А k

Вероятности Р(А 1) Р(А 2) . . . Р(А k) .

H(a) = - å P(A i)log 2 P(A i)

Есть мера неопределённости опыта a по Шеннону. В частности, при Р(А i) = 1/ k , из формулы Шеннона следует формула Хартли.

3.1.1. Доказать, что H(ab) = H(a) + H(b).

3.1.2. Сколько вопросов необходимо задать студентам академической группы преподавателю, чтобы определить старосту этой группы (ответы на вопросы преподавателя могут быть либо "да" либо "нет").

3.1.3. Рассмотреть задачу 3.1.2. в случае одного вопроса.

3.1.4. Пусть х- элемент множества М мощности m. Какое количество

информации необходимо для определения элемента х?

3.1.5. Пусть х 1 и х 2 - два произвольных элемента множеств М 1 и М 2 мощностей m 1 и m 2 соответственно. Какое количество информации необходимо для одновременного определения элементов х 1 и х 2 ?

3.1.6. Пусть имеется 27 золотых монет, из которых одна фальшивая (легче настоящих), и весы с чашками. Сколько взвешиваний необходимо произвести, чтобы определить фальшивую монету?

3.1.7. Доказать, что любого опыта a H(a) ³ 0, причём H(a) = 0 тогда и только тогда, когда одна из вероятностей равна 1, а остальные равны 0.

3.1.8. Доказать, что H(a) ≤ log 2 k , где k - число исходов опыта a , причём равенство достигается лишь в случае, когда исходы равновероятны.

3.1.9. Какими свойствами обладает H(a) , если a имеет два исхода?

УСЛОВНАЯ НЕОПРЕДЕЛЁННОСТЬ.

КОЛИЧЕСТВО ИНФОРМАЦИИ

Пусть a и b - два произвольных опыта с k и l исходами А k , В l соответственно. Тогда если a и b независимы, то

H(ab) = H(a) + H(b) ,

а если же a и b зависимы, то

H(ab) = H(a) + H a (b) ,

где H a (b) - условная неопределённость опыта b при условии выполнения опыта a и определяется равенством k

H a (b) = å P(A i)H A i (b) .

Здесь H A i (b) - условная неопределённость опыта b при условии исхода A i и определяется формулой: l

H A i (b) = - å P A i (B j) log 2 P A i (B j) , i = 1 , k .

Очевидно, если a и b независимы, то H a (b) = H(b) , и H a (b) ≤ H(b) , если a и b зависимы.

Имеет место также равенство

Рассмотрим разность

I (a , b) = H(b) - H a (b) ,

которая указывает, насколько исход опыта a уменьшает неопределённость опыта b. Число I (a , b) называется количеством информации относительно опыта b, содержащимся в опыте a.

В частности, при a =b имеем I (a , a) = 0, что можно трактовать как количество информации об опыте a, содержащимся в самом себе. Если же a и b независимы, то

т.е. в целом

I (a , b) ≥ 0 ,

что можно трактовать примерно так: от всего, чему учат в университете, вреда не будет, а в худшем случае просто не будет пользы.

I (a , b) = I (b, a) ,

то I (a , b) можно назвать также взаимной информацией двух опытов a и b

H(ab) = H(a) + H a (b) ,

I (a , b) = H(a) + H(b) - H(ab) ,

следовательно, k l

I (a , b) = Σ Σ P(A i B j) log 2 P(A i B j) /(P(A i) P(B j)) .

Таким образом, мы получили окончательную формулу относительно количества информации I (a , b).

3.2.1. Доказать, что если a и b произвольные опыты, то;

а) H(ab) = H(a) + H a (b) ;

б) H(ab) ≤ H(a) + H(b) ;

в) 0 ≤ H a (b) ≤ H(b) ;

г) I (a , b) = I (b, a) ;

д) I (a , b) ≤ H(a) ;

3.2.2. Вывести формулу относительно I (a , b) .

3.2.3. Пусть опыт b состоит в извлечении одного шара из урны, содержащий m чёрных и n белых шаров, опыт a k - в предварительном извлечении из той же урны (без возвращения обратно) k шаров. Чему равна неопределённость опыта b и информация об опыте, содержащаяся в опытах a 6,

3.2.4. Пусть из партий в n деталей, изготовленных на конвейере, для выборочного контроля изъяты m деталей. Обозначим через a процент брака всей партии, а через b - процент брака в выборке. Определить I (a , b).

3.2.5. (О городах лжецов и честных людей). Пусть известно, что жители некоторого города А всегда говорят правду, а жители соседнего города Б всегда обманывают. Наблюдатель Н знает, что он находится в одном из этих двух городов, но не знает, в каком именно. Путём опроса встречного ему требуется определить, в каком городе он находится, или в каком городе живёт его собеседник (жители А могут заходить в Б и обратно), или то и другое вместе. Спрашивается, каково наименьшее число вопросов, которые должен задать Н (на все вопросы Н встречный отвечает лишь "да" или "нет").

ПЕРЕДАЧА ИНФОРМАЦИИ

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

В частности, если х и х" - переданное и искажённое сообщения соответственно, то определим количество информации I(x" , x) - выхода канала относительно его входа как:

I(x" , x) = Н(х) - Н х " (х) ,

где Н(х), Н(х") энтропии сообщений х и х" соответственно.

Значение

C = max I(x" , x)

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

Теорема 1 .(о кодировании). Для любого числа R, меньшего пропускной способности С канала, и любого e>0 существует способ блоковой передачи со скоростью, не меньшей R, и вероятностью ошибки Р(е), не превосходящей e.

В то же время всякий способ передачи информации со скоростью, большей пропускной способности, приводит к тому, что вероятность ошибки будет больше некоторой фиксированной величины.

Теорема 2. (обращение теоремы кодирования). Если величина R превосходит пропускную способность канала С, то найдётся константа e 0 (зависящая от R и C) такая, что при любом способе блоковой передачи информации со скоростью, не меньшей R, выполнено неравенство

Р(е)³ e 0 .

Обозначим через I(a i) количество информации, содержащееся в символе a i и определим его как:

I(a i) = - log 2 P(a i) ,

где P(a i) - вероятность появления символа a i в самом тексте сообщения.

Если же текст сообщений записан на некотором естественном языке

(а его можно рассматривать как естественный код, обнаруживающий и исправляющий ошибки), то каждая буква этого языка имеет свою частоту встречаемости в тексте (так, например, в русском языке буквы о, е, ё гораздо чаще встречаются (Р о = 0.09 , Р е,ё = 0.07) , чем буквы э и ф (Р э = 0.003, Р ф = 0.002)) и поэтому неопределённость H L естественного языка определяется как m

H L = - å P(a i) log 2 P(a i) ,

а избыточность С L соответственно как

С L = 1 - H L / log 2 m ,

где m - количество букв естественного языка.

Очевидно, что 0 ≤ С L ≤ 1, следовательно, при оптимальном кодировании часть текста можно без ущерба для понимания опустить.

Так, например, С L = 0.5 для литературного английского языка, а избыточность других языков несколько меньше.

Отметим, что избыточность языка не является недостатком, а скорее преимуществом, так как, например, если С L = 50% , то это означает что по половине искажённого текста можно восстановить весь текст.

3.3.1. Определить пропускную способность ДСК.

3.3.2. Найти I(x" , x) для ДСК.

3.3.3. Определить избыточность и неопределённость русского языка.

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

3.3.5. Доказать теоремы Шеннона для блочных кодов.

3.3.6. Восстановить текст:

а) С??зд ц?ли??м? п?лн???ью од??ри? м??опр??т?я ц? пар??? ?о??рьб? ? ?а?о?ом;

б) ?об?ка?ае? ка?ав?н???ает.

Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3

1. Алфавит дискретных устройств. Конечные поля. . . . . . . . . . 4

1.1. Простое поле Галуа GF(P) . . . . . . . . . . . . . . . . . . . . . 4

1.2. Составное поле Галуа GF(P n) . . . . . . . . . . . . . . . . . . . 6

2. Кодирование информации. . . . . . . . . . . . . . . . . . . . . . .9

2.1. Основные понятия. Примеры кодов. . . . . . . . . . . . . . . 9

2.2. Линейные коды. Способы их задания. . . . . . . . . . . . 15

2.3. Свойства линейного кода. Коды Хэмминга. . . . . . . . . . 22

2.4. Циклические коды. . . . . . . . . . . . . . . . . . . . . . . . 27

2.5. Коды БЧХ, исправляющие две ошибки. . . . . . . . . . . . .32

2.6. Нелинейные коды. Коды Адамара. . . . . . . . . . . . . . . .36

2.7. Границы мощности кодов. . . . . . . . . . . . . . . . . . . . 40

3. Информация и неопределённость. . . . . . . . . . . . . . . . . . 44

3.1. Количественная мера неопределённости. . . . . . . . . . . .45

3.2. Условная неопределённость. Количество информации. . . . .47

3.3. Передача информации. . . . . . . . . . . . . . . . . . . . . .50

Осипян Валерий Осипович

ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕДАЧИ ИНФОРМАЦИИ

Редактор Т.В.Шилова

Технический редактор И.А. Зиновская

Корректор М.Е. Шулепова

ЛР № 200378 от 22.01.97

Подписано в печать 29.01.97.

Формат 60´84 1 /16. Бумага тип. № 3.

Печать трафаретная. Усл. печ. л. 2,75.

Уч.-изд. л. 2,7. Тираж 300 экз. Заказ №

Кубанский государственный университет

Количество информации как мера уменьшения неопределенности знаний

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

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

Рис. 1.1 Знание и незнание

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

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

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

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

Пусть у нас имеется монета, которую мы бросаем на ровную поверхность. С равной вероятностью произойдет одно из двух возможных событий - монета окажется в одном из двух положений: "орел" или "решка".

Можно говорить, что события равновероятны, если при возрастающем числе опытов количества выпадений "орла" и "решки" постепенно сближаются. Например, если мы бросим монету 10 раз, то "орел" может выпасть 7 раз, а решка - 3 раза, если бросим монету 100 раз, то "орел" может выпасть 60 раз, а "решка" - 40 раз, если бросим монету 1000 раз, то "орел" может выпасть 520 раз, а "решка" - 480 и так далее.

В итоге при очень большой серии опытов количества выпадений "орла" и "решки" практически сравняются.

Перед броском существует неопределенность наших знаний (возможны два события), и, как упадет монета, предсказать невозможно. После броска наступает полная определенность, так как мы видим (получаем зрительное сообщение), что монета в данный момент находится в определенном положении (например, "орел"). Это сообщение приводит к уменьшению неопределенности наших знаний в два раза, так как до броска мы имели два вероятных события, а после броска - только одно, то есть в два раза меньше (рис. 1.2).

Рис. 1.2 Возможные и произошедшее события

В окружающей действительности достаточно часто встречаются ситуации, когда может произойти некоторое количество равновероятных событий. Так, при бросании равносторонней четырехгранной пирамиды существуют 4 равновероятных события, а при бросании шестигранного игрального кубика - 6 равновероятных событий.

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

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

За единицу количества информации принимается такое количество информации, которое содержит сообщение, уменьшающее неопределенность в два раза. Такая единица названа "бит" .

Если вернуться к опыту с бросанием монеты, то здесь неопределенность как раз уменьшается в два раза и, следовательно, полученное количество информации равно 1 биту.

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

1 байт = 2 3 бит = 8 бит

В информатике система образования кратных единиц измерения количества информации несколько отличается от принятых в большинстве наук. Традиционные метрические системы единиц, например Международная система единиц СИ, в качестве множителей кратных единиц используют коэффициент 10n, где п = 3, 6, 9 и так далее, что соответствует десятичным приставкам Кило (10 3), Мега (10 6), Гига (10 9) и так далее.

Компьютер оперирует числами не в десятичной, а в двоичной системе счисления, поэтому в кратных единицах измерения количества информации используется коэффициент 2 n .

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

1 Кбайт = 2 10 байт = 1024 байт;
1 Мбайт = 2 10 Кбайт = 1024 Кбайт;
1 Гбайт = 2 10 Мбайт = 1024 Мбайт.

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

N=2 I

(2.1)

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

Наоборот, для определения количества информации, если известно количество событий, необходимо решить показательное уравнение относительно /. Например, в игре "Крестики-нолики" на поле 8x8 перед первым ходом существует 64 возможных события (64 различных варианта расположения "крестика"), тогда уравнение принимает вид:

Так как 64 = 2 6 , то получим:

Таким образом, I = 6 битов, то есть количество информации, полученное вторым игроком после первого хода первого игрока, составляет 6 битов.

Вопросы для размышления

1. Приведите примеры уменьшения неопределенности знаний после получения информации о произошедшем событии.

2. В чем состоит неопределенность знаний в опыте по бросанию монеты?

3. Как зависит количество информации от количества возможных событий?

Задания

1.1. Какое количество информации получит второй игрок после первого хода первого игрока в игре в "Крестики-нолики" на поле размером 4x4?

1.2. Каково было количество возможных событий, если после реализации одного из них мы получили количество информации, равное 3 битам? 7 битам?