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

Разделы: Информатика

Материал разработан на 2 спаренных урока.

Цели уроков: Сформировать у учащихся понимание вероятности, равновероятных событий и событий с различными вероятностями. Научить находить количество информации, используя вероятностный подход. Создать в Excel информационную модель для автоматизации процесса вычислений в задачах на нахождение количества информации, используя формулу Шеннона.

Требования к знаниям и умениям:

Учащиеся должны знать:

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

Учащиеся должны уметь:

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

Оборудование: доска, компьютер, мультимедийный проектор, карточки с заданиями, карточки-памятки, справочный материал.

Урок 1. Вероятностный подход к определению количества информации. Формула Шеннона

Ход урока

I. Организационный момент.

II. Проверка домашнего задания.

III. Постановка цели урока.

Задача: Какое сообщение содержит большее количество информации?

• Отв.: 3 бит.)
• Вася получил за экзамен оценку 4 (по 5-бальной системе единицы не ставят). (Отв.: 2 бит.)
• Отв.: 1 бит.)
• Бабушка испекла 8 пирожков с капустой, 16 пирожков с повидлом. Маша съела один пирожок.

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

Сегодня на уроке мы должны ответить на вопрос: как вычислить количество информации в сообщении о неравновероятном событии.

IV. Объяснение нового материала.

Для вычисления количества информации в сообщении о неравновероятном событии используют следующую формулу: I= log 2 (1/ p)

где I – это количество информации, р – вероятность события.

Вероятность события выражается в долях единицы и вычисляется по формуле: р= K/ N,

где К – величина, показывающая сколько раз произошло интересующее нас событие, N – общее число возможных исходов какого-то процесса.

Вернемся к нашей задаче.

Пусть К 1 – это количество пирожков с повидлом, К 1 =24

К 2 – количество пирожков с капустой, К 2 =8

N – общее количество пирожков, N = К 1 +К 2 =24+8=32

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

Вероятность выбора пирожка с повидлом: р 1 =24/32=3/4=0,75.

Вероятность выбора пирожка с капустой: р 2 =8/32=1/4=0,25.

Обращаем внимание учащихся на то, что в сумме все вероятности дают 1.

Вычислим количество информации, содержащееся в сообщении, что Маша выбрала пирожок с повидлом: I 1 = log 2 (1/ p 1)= log 2 (1/0,75)= log 2 1,3=1,15470 бит.

Вычислим количество информации, содержащееся в сообщении, если был выбран пирожок с капустой: I 2 = log 2 (1/ p 2)= log 2 (1/0,25)= log 2 4=2 бит.

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

• Ответы давать примерные, задавая ученикам следующий вопрос: «В какую степень необходимо возвести число 2, чтобы получилось число, стоящее под знаком логарифма?».
• Применить таблицу из задачника-практикума под редакцией Семакина И.Г. и др.

Приложение 1. «Количество информации в сообщении об одном из N равновероятных событий: I= log 2 N». (Приложение вы можете получить у автора статьи. )

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

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

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

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

Если I -количество информации, N -количество возможных событий, р i - вероятности отдельных событий, где i принимает значения от 1 до N, то количество информации для событий с различными вероятностями можно определить по формуле:

можно расписать формулу в таком виде:

Рассмотрим формулу на нашем примере:

I = - (р 1 ∙log 2 p 1 + р 2 ∙log 2 p 2)= - (0,25∙ log 2 0,25+0,75∙ log 2 0,75)≈-(0,25∙(-2)+0,75∙(-0,42))=0,815 бит

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

1. В библиотеке 8 шкафов. Книга нашлась в 3-м шкафу; (Отв.: 3 бит.)
2. Вася получил за экзамен 3 балла (по 5-бальной системе единицы не ставят). (Отв.: 2 бит.)
3. Бабушка испекла 12 пирожков с капустой, 12 пирожков с повидлом. Маша съела один пирожок. (Отв.: 1 бит.)
4. Бабушка испекла 8 пирожков с капустой, 16 пирожков с повидлом. Маша съела один пирожок. (Отв.: 0,815 бит.)

Ответ : в 1 сообщении.

Обратите внимание на 3 и 4 задачу. Сравните количество информации.

Мы видим, что количество информации достигает максимального значения, если события равновероятны.

Интересно, что рассматриваемые нами формулы классической теории информации первоначально были разработаны для технических систем связи, призванных служить обмену информацией между людьми. Работа этих систем определяется законами физики т.е. законами материального мира. Задача оптимизации работы таких систем требовала, прежде всего, решить вопрос о количестве информации, передаваемой по каналам связи. Поэтому вполне естественно, что первые шаги в этом направлении сделали сотрудники Bell Telephon Companie – X. Найквист, Р. Хартли и К. Шеннон. Приведенные формулы послужили К. Шеннону основанием для исчисления пропускной способности каналов связи и энтропии источников сообщений, для улучшения методов кодирования и декодирования сообщений, для выбора помехоустойчивых кодов, а также для решения ряда других задач, связанных с оптимизацией работы технических систем связи. Совокупность этих представлений, названная К. Шенноном “математической теорией связи”, и явилась основой классической теории информации. (Дополнительный материал можно найти на сайте http://polbu.ru/korogodin_information или прочитав книгу В.И. Корогодин, В.Л. Корогодина. Информация как основа жизни. Формула Шеннона. )

Можно ли применить формулу К. Шеннона для равновероятных событий?

Если p 1 =p 2 =..=p n =1/N, тогда формула принимает вид:

Мы видим, что формула Хартли является частным случаем формулы Шеннона.

V . Закрепление изучаемого материала.

Задача: В корзине лежат 32 клубка красной и черной шерсти. Среди них 4 клубка красной шерсти.

Сколько информации несет сообщение, что достали клубок красной шерсти? Сколько информации несет сообщение, что достали клубок шерсти любой окраски?

Дано: К к =4;N=32

Найти: I к, I

Решение:

Ответ : I к =3 бит; I=0,547 бит

VI . Подведение итогов урока.

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

Урок 2. Применение ЭТ Excel для решения задач на нахождение количества информации

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

Ход урока

I . Постановка целей урока

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

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

р i =K i /N; I i =log 2 (1/p i);

II . Решение задач.

Ученикам дается список задач, которые они должны решить.

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

Задача №1

В озере обитает 12500 окуней, 25000 пескарей, а карасей и щук по 6250. Какое количество информации несет сообщение о ловле рыбы каждого вида. Сколько информации мы получим, когда поймаем какую-нибудь рыбу?

Дано: К о =12500; К п =25000; К к = К щ =6250

Найти: I о , I п , I к , I щ , I

Решение:

1. Найдем общее количество рыбы: N = К о +К п +К к +К щ.
2. Найдем вероятность ловли каждого вида рыбы: p о = К о / N ; p п = К п / N ; p к = p щ = К к / N .
3. Найдем количество информации о ловле рыбы каждого вида: I о = log 2 (1/ p о ); I п = log 2 (1/ p п ); I к = I щ = log 2 (1/ p к )
4. Найдем количество информации о ловле рыбы любого вида: I = p о ∙ log 2 p о + p п ∙ log 2 p п + p к ∙ log 2 p к + p щ ∙ log 2 p щ

III . Объяснение нового материала.

Задается вопрос ученикам:

1. Какие трудности возникают при решении задач данного типа? (Отв. : Вычисление логарифмов).

2. Нельзя ли автоматизировать процесс решения данных задач? (Отв. : можно, т.к. алгоритм вычислений в этих задачах один и тот же).

3. Какие программы используются для автоматизации вычислительного процесса? (Отв.: ЭТ Excel).

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

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

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

Структура таблицы обсуждается с учениками. Роль учителя обобщить ответы учащихся.

При составлении таблицы мы должны учитывать:

1. Ввод данных (что дано в условии).
2. Подсчет общего количества числа возможных исходов (формула N=K 1 +K 2 +…+K i).
3. Подсчет вероятности каждого события (формула p i = К i /N).
4. Подсчет количества информации о каждом происходящем событии (формула I i = log 2 (1/p i)).
5. Подсчет количества информации для событий с различными вероятностями (формула Шеннона).

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

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

Рассмотрим заполнение таблицы на примере задачи №1.

Рис. 1. Режим отображения формул

Рис. 2. Отображение результатов вычислений

Результаты вычислений занести в тетрадь.

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

VI . Практическая работа .

1 . Сделать табличную модель для вычисления количества информации.

2 . Используя табличную модель, сделать вычисления к задаче №2 (рис.3), результат вычисления занести в тетрадь.

Рис. 3

3 . Используя таблицу-шаблон, решить задачи №3,4 (рис.4, рис.5), решение оформить в тетради.

Рис. 4

Задача №2

В классе 30 человек. За контрольную работу по информатике получено 15 пятерок, 6 четверок, 8 троек и 1 двойка. Какое количество информации несет сообщение о том, что Андреев получил пятерку?

Задача№3

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

Задача№4

В непрозрачном мешочке хранятся 10 белых, 20 красных, 30 синих и 40 зеленых шариков. Какое количество информации будет содержать зрительное сообщение о цвете вынутого шарика?

VII . Подведение итогов урока.

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

VIII. Домашняя работа.

1. Параграф учебника «Формула Шеннона», компьютерный практикум после параграфа.

2. Доказать, что формула Хартли – частный случай формулы Шеннона.

Литература:

1. Соколова О.Л. «Универсальные поурочные разработки по информатике. 10-й класс.» – М.: ВАКО, 2007.
2. Угринович Н.Д. «Информатика и ИКТ. Профильный уровень. 10 класс» - Бином, Лаборатория знаний, 2007 г.
3. Семакин И.Г., Хеннер Е.К. «Информатика. Задачник – практикум.» 1 том, - Бином, Лаборатория знаний, 2008 г.

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

Для дальнейшего изложения необходимо использовать некоторые понятия теории вероятности: случайное событие, опыт, вероятность события, случайная величина. В окружающем нас мире происходят различные события, причём мы можем интуитивно, основываясь на опыте, оценивать одни из них как более возможные, чем другие. Случайным называют событие, которое может наступить или не наступить в результате некоторого испытания, опыта или эксперимента. Будем обозначать события заглавными буквами A, B,Cи т.д. Количественная мера возможности наступления некоторого событияAназывается его вероятностью и обозначается какp(A),p– от английского probability. Чем более возможно наступление случайного события, тем больше его вероятность: еслиAболее возможно чемB, то p(A) > p(B). Вводится понятие достоверного события – событие, которое обязательно наступит. Это событие обозначаюти полагают, что его вероятностьp() = 1. Невозможным называют событие, которое никогда не произойдёт. Его обозначаюти полагают, что его вероятностьp() = 0. Для вероятностей всех остальных событий A выполняется неравенствоp() < p(A)

Для событий вводится понятие суммы и произведения. Сумма событий A+B – это событие, которое состоит в наступлении события A или В. Произведение событий A*B состоит в одновременном наступлении события A и B. События AиBнесовместны , если они не могут наступить вместе в результате одного испытания. Вероятность суммы несовместных событий равна сумме их вероятностей. Если А и В несовместные события, то p(A+B) = p(A) + p(B).

События A1, A2, A3, …Anобразуютполную группу , если в результате опыта обязательно наступит хотя бы одно из них. Если события A1, A2, A3, …Anпопарно несовместны и образуют полную группу, то сумма их вероятностей p1+p2+p3+ ….pn=1. Если они при этом ещё и равновероятны, то вероятность каждого равнаp= 1/n, гдеn– число событий.Вероятность события определяется как отношение числа благоприятных событию исходов опыта к общему числу исходов.Частота события – эмпирическое приближение его вероятности. Она вычисляется в результате проведения серии опытов как отношение числа опытов, в которых событие наступило к общему числу опытов. При большом числе опытов (испытаний) частота события стремится к его вероятности.

К. Шеннон, используя подход Р. Хартли, обратил внимание на то, что при передаче словесных сообщений частота (вероятность) использования различных букв алфавита не одинакова: некоторые буквы используются очень часто, другие - редко.

Рассмотрим алфавит A m состоящий изmсимволов. Обозначим черезp i вероятность (частоту) появления i-ого символа в любой позиции передаваемого сообщения, состоящего из n символов. Один i – ый символ алфавита несёт количество информации равное -Log 2 (p i). Перед логарифмом стоит «минус» потому, что количество информации величина неотрицательная, а Log 2 (x) <0 при 0

На месте каждого символа в сообщении может стоять любой символ алфавита A m ; количество информации, приходящееся на один символ сообщения, равно среднему значению информации по всем символам алфавита A m:

Общее количество информации, содержащееся в сообщении из n символов равно:

(3.2)

Если все символы алфавита A m появляются с равной вероятностью, то все p i = p. Так какр i = 1, то p = 1/m.

Формула (3.2) в случае, когда все символы алфавита равновероятны, принимает вид

Вывод: формула Шеннона (3.2) в случае, когда все символы алфавита равновероятны, переходит в формулу Хартли (2.2).

В общем случае количество энтропии Hпроизвольной системы X (случайной величины), которая может находиться в m различных состояниях x 1 ,x 2 , …x m cвероятностями p 1 ,p 2 , …p m , вычисленное по формуле Шеннона, равно

(3.3)

Напомним, что p 1 +p 2 + … +p m = 1. Если все p i одинаковы, то все состояния системы X равновероятны; в этом случае p i = 1/m, и формула (3.3) переходит в формулу Хартли (2.5):H(X) =Log 2 (m).

Замечание. Количество энтропии системы (случайной величины) Х не зависит от того, в каких конкретно состояниях x 1 ,x 2 , …x m может находиться система, но зависит от числаmэтих состояний и от вероятностей p 1 ,p 2 , …p m , с которыми система может находиться в этих состояниях. Это означает, что две системы, у которых число состояний одинаково, а вероятности этих состояний p 1 ,p 2 , …p m равны (с точностью до порядка перечисления), имеют равные энтропии.

Теорема. Максимум энтропии H(X) достигается в том случае, когда все состояния системы равновероятны. Это означает, что

(3.4)

Если система X может находиться только в одном состоянии (m=1), то её энтропия равна нулю. Рассмотрим систему, которая может принимать только два состояния x1 и x2 с вероятностями p1 иp2:

Количество энтропии такой системы равно

H(X) = - (1/2*Log 2 (1/2)+ 1/2*Log 2 (1/2)) = -Log 2 (1/2) = Log 2 (2) = 1

Это количество принимается за единицу измерения энтропии (информации) и называется 1 бит (1 bit).

Рассмотрим функцию

h(x) = -(x*log 2 (x) + (1-x)*log 2 (1-x)). (3.5)

Область её определения – интервал (0 ;1), Limh(x) = 0 приx0 или 1. График этой функции представлен на рисунке:

Рис. 4. График функции (3.5)

Если обозначить x через p 1 , а (1-x) через p 2 , тоp 1 +p 2 =1;p 1 ,p 2 (0;1), h(x) = H(p 1 ,p 2) = - (p 1 *log 2 (p 1) + (p 2)*log 2 (p 2)) – энтропия системы с двумя состояниями; максимум H достигается приp 1 =p 2 = 0.5.

График h(x) можно использовать при решении следующих задач:

Задача 1. Заданы три случайных величины X, Y, Z, каждая из которых принимает по два значения с вероятностями:

P(X=x1) = 0.5; P(X=x2) = 0.5;

P(Y=y1) = 0.2;P(Y=y2) = 0.8;

P(Z=z1) = 0.3; P(Z=z2) = 0.7 .

Запись P(X=x1) = 0.5 означает, что случайная величина X принимает значение x1 с вероятностью 0.5. Требуется расположить энтропии этих систем в порядке возрастания.

Решение. Энтропия H(X) равна 1 и будет наибольшей; энтропия H(Y) равна значению функции h(x), см. (3.5), приx= 0.2, т.е.H(Y)=h(0.2); энтропияH(Z) =h(0.3). По графику h(x) можно определить, что h(0.2) < h(0.3). Следовательно, H(Y) < H(Z) < H(X).

Замечание 1. Энтропия системы тем больше, чем менее отличаются вероятности её состояний друг от друга. На основании этого можно сделать вывод, что H(Y) < H(Z). Например, если для систем X и Y с тремя состояниями заданы вероятности: дляX{0.4; 0.3; 0.3}, дляY{0.1; 0.1; 0.8}, то очевидно, что неопределённость системыXбольше, чем неопределённость системыY: у последней, скорее всего, будет реализовано состояние, вероятность которого равна 0.8 .

Энтропия H(X) характеризует степень неопределённости системы. Чем больше объём полученных о системе сведений, тем больше будет информации о системе, и тем менее неопределённым будет её состояние для получателя информации.

Если энтропия системы после получения информации становится равной нулю, это означает, что неопределённость исчезла, вся энтропия «перешла» в информацию. В этом случае говорят, что была получена полная информацию о системе X.Количество информации, приобретаемое при полном выяснении состояния физической системы, равно энтропии этой системы.

Если после получения некоторого сообщения неопределённость системы Xстала меньше, но не исчезла совсем, то количество информации, содержащееся в сообщении, равно приращению энтропии:

I = H1(X) - H2(X), (3.6)

где H1(X) и H2(X) - энтропия системы до и после сообщения, соответственно. Если H2(X) = 0, то мера неопределённости системы равна нулю и была получена полная информация о системе.

Пример. Вы хотите угадать количество очков, которое выпадет на игральном кубике. Вы получили сообщение, что выпало чётное число очков. Какое количество информации содержит это сообщение?

Решение. Энтропия системы «игральный кубик» H1 равна Log 2 6, т.к. кубик может случайным образом принять шестьравновозможных состояний {1, 2, 3, 4, 5, 6}. Полученное сообщение уменьшает число возможных состояний до трёх: {2, 4, 6}, т.е. энтропия системы теперь равна H2= Log 2 3. Приращение энтропии равно количеству полученной информации I = H1 – H2 = Log 2 6 - Log 2 3 = Log 2 2 = 1bit.

На примере разобранной задачи можно пояснить одно из распространённых определений единицы измерения – 1 бит: 1 бит - количество информации, которое уменьшает неопределённость состояния системы в два раза. Неопределённость дискретной системы зависит от числа её состоянийN. Энтропия до получения информацииH1= Log 2 N. Если после получения информации неопределённость уменьшилась в два раза, то это означает, что число состояний стало равнымN/2, а энтропияH2 =Log 2 N/2. Количество полученной информацииI= H1 -H2 =Log 2 N-Log 2 N/2 =Log 2 2 = 1 бит.

Рассмотрим несколько задач на применение формулы Шеннона и Хартли.

Задача 2. Может ли энтропия системы, которая принимает случайным образом одно из 4-х состояний, равняться: а) 3; б) 2.1 в) 1.9 г) 1; д) 0.3? Ответ объяснить.

Решение. Максимально возможное значение энтропия системы с 4-мя состояниями достигает в случае, когда все состояния равновероятны. Это значение по формуле Хартли равноLog 2 4 = 2 бита. Во всех других случаях энтропия системы с 4-мя состояниями будет меньше 2. Следовательно, возможными значениями энтропии из перечисленных выше, могут быть значения 1.9, 1, 0.3.

Задача 3. Задана функцияH(x)= -x*Log 2 (x) - (1-x)*Log 2 (1-x). Расположите в порядке возрастания следующие значения:H(0.9),H(0.85),H(0.45),H(0.2),H(0.15).

Решение. Используем график функции (3.5). Наибольшим значением будет H(0.45), наименьшим значением – H(0.9), затем по возрастанию идут значенияH(0.15) иH(0.85) = H(0.15); H(0.2). Ответ:H(0.9)

Задача 4. По линии связи переданы сообщения:a) «начало_в_10»;b) «лоанча_1_в0». Сравните количество информации в первом и втором сообщении.

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

Задача 5. Получены три различных сообщенияA,B,C:

A= «прибытие в десять часов»;B= «прибытие в десять часов ноль минут»;C= «прибытие ровно в десять часов». Используя энтропийный подход Шеннона, сравните количество информации, содержащееся в этих сообщениях.

Решение. Обозначим количество информации в сообщениях A, B, C черезI(A),I(B),I(C) соответственно. В смысле «содержания» эти сообщения совершенно одинаковы, но одинаковое содержание выражено с помощью разного количества символов. При этом все символы сообщения А содержатся в сообщении B и С, сообщение С = A + «ровно», В = A + «ноль минут»; в соответствии с подходом Шеннона получаем: I(A) < I(C) < I(B).

Вероятностный подход к определению количества информации 10 класс (профильный уровень)

РЕШЕНИЕ ЗАДАЧ, В УСЛОВИИ КОТОРЫХ СОБЫТИЯ НЕРАВНОВЕРОЯТНЫ

В корзине лежат 8 черных шаров и 24 белых. Сколько информации несет сообщение о том, что достали черный шар?

В коробке лежат 64 цветных карандаша. Сообщение о том, что достали белый карандаш, несет 4 бита информации. Сколько белых карандашей было в коробке?

В классе 30 человек. За контрольную работу по математике получено 15 пятерок, 6 четверок, 8 троек и 1 двойка. Какое количество информации в сообщении о том, что Андреев получил пятерку?

Известно, что в ящике лежат 20 шаров. Из них – 10 синих, 5 – зеленых, 4 – желтых и 1 красный. Какое количество информации несут сообщения о том, что из ящика случайным образом достали синий шар, зеленый шар, желтый шар, красный шар? Какое количество информации несет сообщение о том, что из ящика случайным образом достали шар любого цвета?

В течение четверти ученик получил 100 оценок. Сообщение о том, что он получил пятерку, несет 2 бита информации. Сколько пятерок ученик получил в течение четверти?

В ящике лежат перчатки (белые и черные). Среди них – 2 пары черных. Сообщение о том, что из ящика достали пару черных перчаток, несет 4 бита информации. Сколько пар белых перчаток было в ящике?

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

В корзине лежат белые и черные шары. Среди них 18 черных шаров. Сообщение о том, что из корзины достали белый шар, несет 2 бита информации. Сколько всего в корзине шаров?

На остановке останавливаются троллейбусы с разными номерами. Сообщение о том, что к остановке подошел троллейбус с номером N 1, несет 4 бита информации. Вероятность появления на остановке троллейбуса с номером N 2 в два раза меньше, чем вероятность появления троллейбуса с номером N 1. Сколько информации несет сообщение о появлении на остановке троллейбуса с номером N 2?

Просмотр содержимого документа
«Теория»

Урок на тему «Количество информации в сообщении о неравновероятном событии.

Формула Шеннона».

(10 класс, профильный уровень, по учебнику Н.Д.Угриновича)

Цель урока:

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

Задачи:

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

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

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

Используемые технологии: проблемного обучения.

Оборудование: интерактивная доска, проектор, презентация к уроку.

Ход урока

I. Постановка цели урока.

СЛАЙД 1. Учащимся предлагается устно решить задачу:

Задача :

Отв.: 3 бит.)

Вася получил за экзамен оценку 4 (по 5-бальной системе единицы не ставят). (Отв.: 2 бит.)

Отв.: 1 бит.)

(В четвертом варианте учащиеся сталкиваются с ситуацией, когда события не равновероятны) .

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

СЛАЙД 2. Как вы думаете, какова же тема сегодняшнего урока? А цель?(исходя из выше обозначенной проблемы учащиеся сами формулируют тему и цель урока )

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

I I . Объяснение нового материала.

СЛАЙД 3. Для вычисления количества информации в сообщении о неравновероятном событии используют следующую формулу:

I=log 2 (1/p), где

I – это количество информации,

р – вероятность события.

Вероятность события выражается в долях единицы и вычисляется по формуле:

р=K/N, где

К – величина, показывающая сколько раз произошло интересующее нас событие,

N – общее число возможных исходов какого-то процесса.

СЛАЙД 4. Вернемся к нашей задаче.

К 1 – это количество пирожков с повидлом, К 1 =24

К 2 – количество пирожков с капустой, К 2 =8

N – общее количество пирожков, N = К 1 +К 2, N =24+8=32

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

Вероятность выбора пирожка с повидлом: р 1 =24/32=3/4=0,75.

Вероятность выбора пирожка с капустой: р 2 =8/32=1/4=0,25.

Обращаем внимание учащихся на то, что в сумме все вероятности дают 1 .

Вычислим количество информации, содержащееся в сообщении, что Маша выбрала пирожок с повидлом:

I 1 =log 2 (1/p 1 ), I 1 = log 2 (1/0,75)= log 2 1,3=1,15470 бит.

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

I 2 =log 2 (1/p 2 ), I 2 = log 2 (1/0,25)= log 2 4=2 бит.

При сравнении результатов вычислений получается следующая ситуация:

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

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

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

СЛАЙД 5. Ответить на этот вопрос нам поможет формула вычисления количества информации для событий с различными вероятностями, которую предложил в 1948 г. американский инженер и математик Клод Элвуд Шеннон.

Если I -количество информации,

N -количество возможных событий,

р i - вероятности отдельных событий, где i принимает значения от 1 до N, то количество информации для событий с различными вероятностями можно определить по формуле:

СЛАЙД 6. можно расписать формулу в таком виде:

Знак минус в формуле не означает, что количество информации в сообщении – отрицательная величина. Объясняется это тем, что вероятность (р), согласно определению, 0. Т.к. Log числа, меньшего 1 (т.е. log p i ) – величина отрицательная, то произведение вероятности на логарифм числа будет положительным.

Рассмотрим формулу на нашем примере:

I = - (р 1 ∙log 2 p 1 + р 2 ∙log 2 p 2),

I = - (0,25∙ log 2 0,25+0,75∙ log 2 0,75)≈-(0,25∙(-2)+0,75∙(-0,42))=0,815 бит

СЛАЙД 7. Теперь ответьте на вопрос задачи, которая была поставлена в начале урока: Какое сообщение содержит большее количество информации?

В библиотеке 8 шкафов. Книга нашлась в 3-м шкафу; (Отв.: 3 бит.)

Вася получил за экзамен 3 балла (по 5-бальной системе единицы не ставят). (Отв.: 2 бит.)

Бабушка испекла 12 пирожков с капустой, 12 пирожков с повидлом. Маша съела один пирожок. (Отв.: 1 бит.)

Бабушка испекла 8 пирожков с капустой, 24 пирожка с повидлом. Маша съела один пирожок. (Отв.: 0,815 бит.)

Ответ : в 1 сообщении.

Обратите внимание на 3 и 4 задачу. Сравните количество информации.

Мы видим, что количество информации достигает максимального значения, если события равновероятны.

Можно ли применить формулу К. Шеннона для равновероятных событий?

Если p 1 =p 2 =..=p n =1/N, тогда формула принимает вид:

Мы видим, что формула Хартли является частным случаем формулы Шеннона.

III . Закрепление изучаемого материала.

СЛАЙД 8.

Задача №1: (объясняет учитель)

В корзине лежат 32 клубка красной и черной шерсти. Среди них 4 клубка красной шерсти.

Сколько информации несет сообщение, что достали клубок красной шерсти? Сколько информации несет сообщение, что достали клубок шерсти любой окраски?

Дано: К к =4;N=32

Найти: I к, I

Решение:

Найдем количество клубков черной шерсти:

К ч =N- К к; К ч =32-4=28

Найдем вероятность доставания клубка каждого вида:

p к = К к /N, p к =4/32=1/8;

p ч = К ч /N, p ч =28/32=7/8;

Найдем количество информации, которое несет сообщение, что достали клубок красной шерсти:

I к = log 2 (1/(1/ p к)), I к = log 2 (1/1/8)= log 2 8=3 бита

Найдем количество информации, которое несет сообщение, что достали клубок шерсти любой окраски:

Ответ : I к =3 бит; I=0,547 бит

(Задачи 2-4 учащиеся решают в парах с дальнейшей защитой решения у доски).

Задача №2:

Задача №3: В озере обитает 12500 окуней, 25000 пескарей, а карасей и щук по 6250. Какое количество информации несет сообщение о ловле рыбы каждого вида. Сколько информации мы получим, когда поймаем какую-нибудь рыбу?

Задача №4:

VI. Подведение итогов урока.

СЛАЙД 9. Ответьте на вопросы:

V . Домашнее задание.

СЛАЙД 10. §2.4 стр.111-113. Устно №2.3 стр.114-115. Письменно №2.3 стр.115

ИСТОЧНИКИ:

Н.Д.Угринович «Информатика и ИКТ». Учебник для10 класса, профильный уровень.

1. http://marknet.narod.ru/spr/list5.htm Информатика. Справочный материал. Количество информации. Формулы Хартли и Шеннона

Н.Д.Угринович, методическое пособие «Информатика и ИКТ 8 -11 класс»

Просмотр содержимого презентации
«Формула Шеннона»

Какое сообщение содержит большее количество информации?

• В библиотеке 8 шкафов. Книга нашлась в 3-м шкафу;
• Вася получил за экзамен оценку 4;
• Бабушка испекла 12 пирожков с капустой, 12 пирожков с повидлом. Маша съела один пирожок;
• Бабушка испекла 8 пирожков с капустой, 24 пирожка с повидлом. Маша съела один пирожок.

Company Logo

I = log 2 (1/p) ,

I – количество информации

p – вероятность события

K – сколько раз произошло интересующее нас событие

N – общее число возможных исходов какого-то процесса

Company Logo

I 1 = log 2 (1/0 , 75) = log 2 1 ,3 = 1,15470 бит К-во информации в сообщении, что Маша выбрала пирожок с капустой: I 2 = log 2 (1/p 2) = I 2 = log 2 (1/0 ,2 5) = log 2 4 = 2 бита =1 Чем меньше вероятность некоторого события, тем больше информации содержит сообщение об этом событии Company Logo" width="640"

Вернемся к задаче №4:

Количество пирожков с повидлом: К 1 = 24 N = K 1 + K 2

Количество пирожков с капустой: К 2 = 8 N = 24 + 8 = 32

Вероятность выбора пирожка с повидлом: р 1 = 24/32 = 0,75

Вероятность выбора пирожка с капустой: р 2 = 8/32 = 0,25

К-во информации в сообщении, что Маша выбрала пирожок с повидлом: I 1 = log 2 (1/p 1 ) = I 1 = log 2 (1/0 , 75) = log 2 1 ,3 = 1,15470 бит

К-во информации в сообщении, что Маша выбрала пирожок с капустой: I 2 = log 2 (1/p 2 ) = I 2 = log 2 (1/0 ,2 5) = log 2 4 = 2 бита

Чем меньше вероятность некоторого события, тем больше информации содержит сообщение

об этом событии

Company Logo

Формула Шеннона

I – количество информации,

N – количество возможных событий

p i – вероятности отдельных событий

Клод Элвуд Шеннон ,

1916 – 2001 г.г.

Американский математик

и инженер

Company Logo

Формула Шеннона

Тогда, для нашей задачи:

I = - (р 1 ∙log 2 p 1 + р 2 ∙log 2 p 2 ),

I = - (0,25∙ log 2 0,25+0,75∙ log 2 0,75)≈ -(0,25∙(-2)+0,75∙(-0,42))=0,815 бит

Company Logo

Какое сообщение содержит большее количество информации?

Сообщение

Кол-во информации

В библиотеке 8 шкафов. Книга нашлась в 3-ем шкафу.

3 бита

Вася получил за экзамен 3 балла.

2 бита

Бабушка испекла 12 пирожков с капустой, 12 пирожков с повидлом. Маша съела один пирожок.

1 бит

Бабушка испекла 8 пирожков с капустой, 24 пирожка с повидлом. Маша съела один пирожок.

0,815 бит

Количество информации достигает

максимального значения, если события равновероятны .

Company Logo

Решить задачи:

• В корзине лежат 32 клубка красной и черной шерсти. Среди них 4 клубка красной шерсти. Сколько информации несет сообщение, что достали клубок красной шерсти? Сколько информации несет сообщение, что достали клубок шерсти любой окраски?
• В непрозрачном мешочке хранятся 10 белых, 20 красных, 30 синих и 40 зеленых шариков. Какое количество информации будет содержать зрительное сообщение о цвете вынутого шарика?
• В озере обитает 12500 окуней, 25000 пескарей, а карасей и щук по 6250. Какое количество информации несет сообщение о ловле рыбы каждого вида? Сколько информации мы получим, когда поймаем какую–нибудь рыбу?
• В коробке лежат кубики: 10 красных, 8 зеленых, 5 желтых, 12 синих. Вычислите вероятность доставания кубика каждого цвета и количество информации, которое при этом будет получено.

Company Logo

Ответьте на вопросы:

• Объясните на конкретных примерах отличие равновероятного события от неравновероятного?
• С помощью какой формулы вычисляется вероятность события?
• Объясните качественную связь между вероятностью события и количеством информации в сообщении об этом событии?
• В каких случаях применяется формула Шеннона для измерения количества информации?
• В каком случае количество информации о событии достигает максимального значения?

Company Logo

 Домашнее задание:

• §2.4 стр.111 – 113
• № 2.3 стр. 114 – 115 – устно
• № 2.3 стр. 115 - письменно

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

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

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

Случайным называют событие, которое может наступить или не наступить в результате некоторого испытания, опыта или эксперимента. Будем обозначать события заглавными буквами A, B, C и т.д.

Количественная мера возможности наступления некоторого события A называется его вероятностью и обозначается как p(A), p – от английского probability. Чем более возможно наступление случайного события, тем больше его вероятность: если A более возможно чем B , то p(A) > p(B).

Вводится понятие достоверного события – событие, которое обязательно наступит. Это событие обозначают Ω и полагают, что его вероятность p(Ω) = 1 .

Невозможным называют событие, которое никогда не произойдёт. Его обозначают « и полагают, что его вероятность p(Æ)= 0 . Для вероятностей всех остальных событий A выполняется неравенство p(Æ) < p(A) < p(Ω) , или 0 < p(A) < 1 .

Для событий вводится понятие суммы и произведения.

Сумма событий A+B – это событие, которое состоит в наступлении события A или В. Произведение событий A*B состоит в одновременном наступлении события A и B .

События A и B несовместны , если они не могут наступить вместе в результате одного испытания. Вероятность суммы несовместных событий равна сумме их вероятностей. Если А и В несовместные события, то p(A+B) = p(A) + p(B).

События A1, A2, A3, …An образуют полную группу , если в результате опыта обязательно наступит хотя бы одно из них.

Если события A1, A2, A3, …An попарно несовместны и образуют полную группу, то сумма их вероятностей p1+p2+p3+ …. pn =1.

Если они при этом ещё и равновероятны, то вероятность каждого равна p = 1/n , где n – число событий.

Вероятность события определяется как отношение числа благоприятных событию исходов опыта к общему числу исходов.

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

К. Шеннон, используя подход Р. Хартли, обратил внимание на то, что при передаче словесных сообщений частота (вероятность) использования различных букв алфавита не одинакова: некоторые буквы используются очень часто, другие - редко.

Рассмотрим алфавит A m состоящий из m символов. Обозначим через p i вероятность (частоту) появления i -ого символа в любой позиции передаваемого сообщения, состоящего из n символов.

Один i – ый символ алфавита несёт количество информации равное -Log 2 (p i) . Перед логарифмом стоит «минус» потому, что количество информации величина неотрицательная, а Log 2 (x) <0 при 0.

На месте каждого символа в сообщении может стоять любой символ алфавита A m ; количество информации, приходящееся на один символ сообщения, равно среднему значению информации по всем символам алфавита A m :

Общее количество информации, содержащееся в сообщении из n символов равно:

Если все символы алфавита A m появляются с равной вероятностью, то все p i = p . Так как ∑р i = 1 , то p = 1/m.

Формула в случае, когда все символы алфавита равновероятны, принимает вид

I = n *Log 2 (m ).

Вывод : формула Шеннона в случае, когда все символы алфавита равновероятны, переходит в формулу Хартли.

В общем случае количество энтропии H произвольной системы X (случайной величины), которая может находиться в m различных состояниях x 1 , x 2 , … x m c вероятностями p 1 , p 2 , … p m , вычисленное по формуле Шеннона, равно

Напомним, что p 1 + p 2 + … +p m = 1. Если все p i одинаковы, то все состояния системы X равновероятны; в этом случае p i = 1/m , и формула переходит в формулу Хартли: H(X) = Log 2 (m).

Замечание. Количество энтропии системы (случайной величины) Х не зависит от того, в каких конкретно состояниях x 1 , x 2 , … x m может находиться система, но зависит от числа m этих состояний и от вероятностей p 1 , p 2 , … p m , с которыми система может находиться в этих состояниях. Это означает, что две системы, у которых число состояний одинаково, а вероятности этих состояний p 1 , p 2 , … p m равны (с точностью до порядка перечисления), имеют равные энтропии.

Теорема. Максимум энтропии H(X) достигается в том случае, когда все состояния системы равновероятны. Это означает, что

Если система X может находиться только в одном состоянии (m=1 ), то её энтропия равна нулю .

Рассмотрим систему, которая может принимать только два состояния x1 и x2 с вероятностями p1 и p2 :

Количество энтропии такой системы равно

H(X) = - (1/2*Log 2 (1/2)+ 1/2*Log 2 (1/2)) = -Log 2 (1/2) = Log 2 (2) = 1

Это количество принимается за единицу измерения энтропии (информации) и называется 1 бит (1 bit).

Рассмотрим функцию

h(x) = -(x*log 2 (x) + (l-x)*log 2 (l-x))

Область её определения - интервал (0 ;1) , Lim h(x) = 0 при х -> 0или х -> 1.

График этой функции представлен на рисунке:

График функции h(x) = -(x*log 2 (x) + (l-x)*log 2 (l-x))

Если обозначить x через p 1 , а (1-x) через p 2 , то p 1 + p 2 =1 ; p 1 , p 2 Î(0;1) , h(x) = H(p 1 , p 2) = - (p 1 *log 2 (p 1) + (p 2)*log 2 (p 2)) – энтропия системы с двумя состояниями; максимум H достигается при p 1 = p 2 = 0.5 .

График h(x) можно использовать при решении следующих задач:

Задача 1. Заданы три случайных величины X, Y, Z, каждая из которых принимает по два значения с вероятностями:

1. P(X = x1) = 0.5; P(X = x2) = 0.5;

2. P(Y = y1) = 0.2; P(Y = y2) = 0.8;

3. P(Z = z1) = 0.3; P(Z = z2) = 0.7 .

Запись P(X = x1) = 0.5 означает, что случайная величина X принимает значение x1 с вероятностью 0.5. Требуется расположить энтропии этих систем в порядке возрастания.

Решение .

Энтропия H(X) равна 1 и будет наибольшей;

Энтропия H(Y) равна значению функции h(x), ()при x = 0.2, т.е. H(Y)=h(0.2);

Энтропия H(Z) = h(0.3). По графику h(x) можно определить, что h(0.2) < h(0.3). Следовательно, H(Y) < H(Z) < H(X).

Замечание 1. Энтропия системы тем больше, чем менее отличаются вероятности её состояний друг от друга.

На основании этого можно сделать вывод, что H(Y) < H(Z).

Например, если для систем X и Y с тремя состояниями заданы вероятности: для X {0.4; 0.3; 0.3}, для Y {0.1; 0.1; 0.8}, то очевидно, что неопределённость системы X больше, чем неопределённость системы Y: у последней, скорее всего, будет реализовано состояние, вероятность которого равна 0.8 .

Энтропия H(X) характеризует степень неопределённости системы. Чем больше объём полученных о системе сведений, тем больше будет информации о системе, и тем менее неопределённым будет её состояние для получателя информации.

Если энтропия системы после получения информации становится равной нулю, это означает, что неопределённость исчезла, вся энтропия «перешла» в информацию. В этом случае говорят, что была получена полная информацию о системе X. Количество информации, приобретаемое при полном выяснении состояния физической системы, равно энтропии этой системы.

Если после получения некоторого сообщения неопределённость системы X стала меньше, но не исчезла совсем, то количество информации, содержащееся в сообщении, равно приращению энтропии:

I = H1(X) - H2(X),

где H1(X) и H2(X) - энтропия системы до и после сообщения, соответственно. Если H2(X) = 0, то мера неопределённости системы равна нулю и была получена полная информация о системе.

Пример . Вы хотите угадать количество очков, которое выпадет на игральном кубике. Вы получили сообщение, что выпало чётное число очков. Какое количество информации содержит это сообщение?

Решение . Энтропия системы «игральный кубик» H1 равна Log 2 6 , т.к. кубик может случайным образом принять шесть равновозможных состояний {1, 2, 3, 4, 5, 6}. Полученное сообщение уменьшает число возможных состояний до трёх: {2, 4, 6}, т.е. энтропия системы теперь равна H2= Log 2 3 . Приращение энтропии равно количеству полученной информации I = H1 – H2 = Log 2 6 - Log 2 3 = Log 2 2 = 1 bit.

На примере разобранной задачи можно пояснить одно из распространённых определений единицы измерения – 1 бит: 1 бит -количество информации, которое уменьшает неопределённость состояния системы в два раза.

Неопределённость дискретной системы зависит от числа её состояний N.

Энтропия до получения информации H1= Log 2 N . Если после получения информации неопределённость уменьшилась в два раза, то это означает, что число состояний стало равным N/2, а энтропия H2 = Log 2 N/2. Количество полученной информации I= H1 -H2 = Log 2 N - Log 2 N/2 = Log 2 2 = 1 бит.

Рассмотрим несколько задач на применение формулы Шеннона и Хартли.

Задача 2. Может ли энтропия системы, которая принимает случайным образом одно из 4-х состояний, равняться: а) 3; б) 2.1 в) 1.9 г) 1; д) 0.3? Ответ объяснить.

Решение. Максимально возможное значение энтропия системы с 4-мя состояниями достигает в случае, когда все состояния равновероятны. Это значение по формуле Хартли равно Log 2 4 = 2 бита. Во всех других случаях энтропия системы с 4-мя состояниями будет меньше 2. Следовательно, возможными значениями энтропии из перечисленных выше, могут быть значения 1.9, 1, 0.3.

Задача 3. Задана функция H(x)= -x*Log 2 (x) - (1-x)*Log 2 (1-x). Расположите в порядке возрастания следующие значения: H(0.9), H(0.85), H(0.45), H(0.2), H(0.15).

Решение. Используем график функции (3.5). Наибольшим значением будет H(0.45), наименьшим значением – H(0.9), затем по возрастанию идут значения H(0.15) и H(0.85) = H(0.15); H(0.2). Ответ: H(0.9) < H(0.15)=H(0.85)< H(0.2) < H(0.45). É

Задача 4. По линии связи переданы сообщения: a) «начало_в_10»; b) «лоанча_1_в0». Сравните количество информации в первом и втором сообщении.

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

Задача 5. Получены три различных сообщения A, B, C:

A= «прибытие в десять часов»; B= «прибытие в десять часов ноль минут»; C= «прибытие ровно в десять часов». Используя энтропийный подход Шеннона, сравните количество информации, содержащееся в этих сообщениях.

Решение. Обозначим количество информации в сообщениях A, B, C через I(A), I(B), I(C) соответственно. В смысле «содержания» эти сообщения совершенно одинаковы, но одинаковое содержание выражено с помощью разного количества символов. При этом все символы сообщения А содержатся в сообщении B и С, сообщение С = A + «ровно», В = A + «ноль минут»; в соответствии с подходом Шеннона получаем: I(A) < I(C) < I(B).

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

Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии n {\displaystyle n} -го порядка, см. ) встречаются очень редко, то неопределённость уменьшается еще сильнее.

Формальные определения

Информационная двоичная энтропия для независимых случайных событий x {\displaystyle x} с n {\displaystyle n} возможными состояниями, распределённых с вероятностями ( i = 1 , . . . , n {\displaystyle i=1,...,n} ), рассчитывается по формуле

H (x) = − ∑ i = 1 n p i log 2 ⁡ p i . {\displaystyle H(x)=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}.}

Эта величина также называется средней энтропией сообщения . Величина H i = − log 2 ⁡ p i {\displaystyle H_{i}=-\log _{2}{p_{i}}} называется частной энтропией , характеризующей только i {\displaystyle i} -e состояние. В общем случае основание логарифма в определении энтропии может быть любым, большим 1; его выбор определяет единицу измерения энтропии. Так, зачастую (например, в задачах математической статистики) более удобным может оказаться применение натурального логарифма.

Таким образом, энтропия системы x {\displaystyle x} является суммой с противоположным знаком всех относительных частот появления состояния (события) с номером i {\displaystyle i} , умноженных на их же двоичные логарифмы . Это определение для дискретных случайных событий можно формально расширить для непрерывных распределений, заданных плотностью распределения вероятностей , однако полученный функционал будет обладать несколько иными свойствами (см. дифференциальная энтропия).

Определение по Шеннону

Определение энтропии Шеннона связано с понятием термодинамической энтропии . Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.

Определение с помощью собственной информации

Также можно определить энтропию случайной величины, введя предварительно понятия распределения случайной величины X {\displaystyle X} , имеющей конечное число значений:

P X (x i) = p i , p i ⩾ 0 , i = 1 , 2 , … , n {\displaystyle P_{X}(x_{i})=p_{i},\quad p_{i}\geqslant 0,\;i=1,\;2,\;\ldots ,\;n} ∑ i = 1 n p i = 1 {\displaystyle \sum _{i=1}^{n}p_{i}=1} I (X) = − log ⁡ P X (X) . {\displaystyle I(X)=-\log P_{X}(X).}

Тогда энтропия определяется как:

H (X) = E (I (X)) = − ∑ i = 1 n p (i) log ⁡ p (i) . {\displaystyle H(X)=E(I(X))=-\sum _{i=1}^{n}p(i)\log p(i).}

Единицы измерения информационной энтропии

От основания логарифма зависит единица измерения количества информации и энтропии: бит , нат , трит или хартли .

Свойства

Энтропия является количеством, определённым в контексте вероятностной модели для . Например, кидание монеты имеет энтропию:

− 2 (1 2 log 2 ⁡ 1 2) = − log 2 ⁡ 1 2 = log 2 ⁡ 2 = 1 {\displaystyle -2\left({\frac {1}{2}}\log _{2}{\frac {1}{2}}\right)=-\log _{2}{\frac {1}{2}}=\log _{2}2=1} бит на одно кидание (при условии его независимости), а количество возможных состояний равно: 2 1 = 2 {\displaystyle 2^{1}=2} возможных состояния (значения) ("орёл" и "решка ").

У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: − ∑ i = 1 ∞ log 2 ⁡ 1 = 0 {\displaystyle -\sum _{i=1}^{\infty }\log _{2}1=0} , а количество возможных состояний равно: 2 0 = 1 {\displaystyle 2^{0}=1} возможное состояние (значение) («А») и от основания логарифма не зависит.
Это тоже информация, которую тоже надо учитывать. Примером запоминающих устройств в которых используются разряды с энтропией равной нулю, но с количеством информации равным 1 возможному состоянию , т.е. не равным нулю, являются разряды данных записанных в ПЗУ , в которых каждый разряд имеет только одно возможное состояние .

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

1. Некоторые биты данных могут не нести информации. Например, структуры данных часто хранят избыточную информацию, или имеют идентичные секции независимо от информации в структуре данных.
2. Количество энтропии не всегда выражается целым числом битов.

Математические свойства

1. Неотрицательность : H (X) ⩾ 0 {\displaystyle H(X)\geqslant 0} .
2. Ограниченность : H (X) = − E (log 2 ⁡ p i) = ∑ i = 1 n p i log 2 ⁡ 1 p i = ∑ i = 1 n p i f (g i) ⩽ f (∑ i = 1 n p i g i) = log 2 ⁡ n {\displaystyle H(X)=-E(\log _{2}p_{i})=\sum _{i=1}^{n}p_{i}\log _{2}{\frac {1}{p_{i}}}=\sum _{i=1}^{n}p_{i}f(g_{i})\leqslant f\left(\sum _{i=1}^{n}p_{i}g_{i}\right)=\log _{2}n} , что вытекает из неравенства Йенсена для вогнутой функции f (g i) = log 2 ⁡ g i {\displaystyle f(g_{i})=\log _{2}g_{i}} и g i = 1 p i {\displaystyle g_{i}={\frac {1}{p_{i}}}} . Если все n {\displaystyle n} элементов из X {\displaystyle X} равновероятны, H (X) = log 2 ⁡ n {\displaystyle H(X)=\log _{2}n} .
3. Если независимы, то H (X ⋅ Y) = H (X) + H (Y) {\displaystyle H(X\cdot Y)=H(X)+H(Y)} .
4. Энтропия - выпуклая вверх функция распределения вероятностей элементов.
5. Если X , Y {\displaystyle X,\;Y} имеют одинаковое распределение вероятностей элементов, то H (X) = H (Y) {\displaystyle H(X)=H(Y)} .

Эффективность

Алфавит может иметь вероятностное распределение далекое от равномерного . Если исходный алфавит содержит n {\displaystyle n} символов, тогда его можно сравнить с «оптимизированным алфавитом», вероятностное распределение которого равномерное. Соотношение энтропии исходного и оптимизированного алфавита - это эффективность исходного алфавита, которая может быть выражена в процентах. Эффективность исходного алфавита с n {\displaystyle n} символами может быть также определена как его n {\displaystyle n} -арная энтропия.

Энтропия ограничивает максимально возможное сжатие без потерь (или почти без потерь), которое может быть реализовано при использовании теоретически - типичного набора или, на практике, - кодирования Хаффмана , кодирования Лемпеля - Зива - Велча или арифметического кодирования .

Вариации и обобщения

b -арная энтропия

В общем случае b -арная энтропия (где b равно 2, 3, …) источника S = (S , P) {\displaystyle {\mathcal {S}}=(S,\;P)} с исходным алфавитом S = { a 1 , … , a n } {\displaystyle S=\{a_{1},\;\ldots ,\;a_{n}\}} и дискретным распределением вероятности P = { p 1 , … , p n } , {\displaystyle P=\{p_{1},\;\ldots ,\;p_{n}\},} где p i {\displaystyle p_{i}} является вероятностью ( p i = p (a i) {\displaystyle p_{i}=p(a_{i})} ), определяется формулой:

H b (S) = − ∑ i = 1 n p i log b ⁡ p i . {\displaystyle H_{b}({\mathcal {S}})=-\sum _{i=1}^{n}p_{i}\log _{b}p_{i}.}

В частности, при b = 2 {\displaystyle b=2} , мы получаем обычную двоичную энтропию, измеряемую в битах . При b = 3 {\displaystyle b=3} , мы получаем тринарную энтропию, измеряемую в тритах (один трит имеет источник информации с тремя равновероятными состояниями). При b = e {\displaystyle b=e} , мы получаем информацию измеряемую в натах .

Условная энтропия

Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а, следовательно, и энтропия), очевидно, меньше. Для учёта таких фактов используется условная энтропия.

Условной энтропией первого порядка (аналогично для Марковской модели первого порядка) называется энтропия для алфавита, где известны вероятности появления одной буквы после другой (то есть, вероятности двухбуквенных сочетаний):

H 1 (S) = − ∑ i p i ∑ j p i (j) log 2 ⁡ p i (j) , {\displaystyle H_{1}({\mathcal {S}})=-\sum _{i}p_{i}\sum _{j}p_{i}(j)\log _{2}p_{i}(j),}

где i {\displaystyle i} - это состояние, зависящее от предшествующего символа, и p i (j) {\displaystyle p_{i}(j)} - это вероятность j {\displaystyle j} при условии, что i {\displaystyle i} был предыдущим символом.

Например, для русского языка без буквы «ё» H 0 = 5 , H 1 = 4,358 , H 2 = 3 , 52 , H 3 = 3 , 01 {\displaystyle H_{0}=5,\;H_{1}=4{,}358,\;H_{2}=3{,}52,\;H_{3}=3{,}01} .

Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются так называемые канальные матрицы . Для описания потерь со стороны источника (то есть известен посланный сигнал) рассматривают условную вероятность получения приёмником символа при условии, что был отправлен символ a i {\displaystyle a_{i}} . При этом канальная матрица имеет следующий вид:

	b 1 {\displaystyle b_{1}}	b 2 {\displaystyle b_{2}}	…	b j {\displaystyle b_{j}}	…	b m {\displaystyle b_{m}}
a 1 {\displaystyle a_{1}}	p (b 1 ∣ a 1) {\displaystyle p(b_{1}\mid a_{1})}	p (b 2 ∣ a 1) {\displaystyle p(b_{2}\mid a_{1})}	…	p (b j ∣ a 1) {\displaystyle p(b_{j}\mid a_{1})}	…	p (b m ∣ a 1) {\displaystyle p(b_{m}\mid a_{1})}
a 2 {\displaystyle a_{2}}	p (b 1 ∣ a 2) {\displaystyle p(b_{1}\mid a_{2})}	p (b 2 ∣ a 2) {\displaystyle p(b_{2}\mid a_{2})}	…	p (b j ∣ a 2) {\displaystyle p(b_{j}\mid a_{2})}	…	p (b m ∣ a 2) {\displaystyle p(b_{m}\mid a_{2})}
…	…	…	…	…	…	…
a i {\displaystyle a_{i}}	p (b 1 ∣ a i) {\displaystyle p(b_{1}\mid a_{i})}	p (b 2 ∣ a i) {\displaystyle p(b_{2}\mid a_{i})}	…	p (b j ∣ a i) {\displaystyle p(b_{j}\mid a_{i})}	…	p (b m ∣ a i) {\displaystyle p(b_{m}\mid a_{i})}
…	…	…	…	…	…	…
a m {\displaystyle a_{m}}	p (b 1 ∣ a m) {\displaystyle p(b_{1}\mid a_{m})}	p (b 2 ∣ a m) {\displaystyle p(b_{2}\mid a_{m})}	…	p (b j ∣ a m) {\displaystyle p(b_{j}\mid a_{m})}	…	p (b m ∣ a m) {\displaystyle p(b_{m}\mid a_{m})}

Очевидно, вероятности, расположенные по диагонали, описывают вероятность правильного приёма, а сумма всех элементов любой строки даёт 1. Потери, приходящиеся на передаваемый сигнал a i {\displaystyle a_{i}} , описываются через частную условную энтропию:

H (B ∣ a i) = − ∑ j = 1 m p (b j ∣ a i) log 2 ⁡ p (b j ∣ a i) . {\displaystyle H(B\mid a_{i})=-\sum _{j=1}^{m}p(b_{j}\mid a_{i})\log _{2}p(b_{j}\mid a_{i}).}

Для вычисления потерь при передаче всех сигналов используется общая условная энтропия:

H (B ∣ A) = ∑ i p (a i) H (B ∣ a i) . {\displaystyle H(B\mid A)=\sum _{i}p(a_{i})H(B\mid a_{i}).}

H (B ∣ A) {\displaystyle H(B\mid A)} означает энтропию со стороны источника, аналогично рассматривается H (A ∣ B) {\displaystyle H(A\mid B)} - энтропия со стороны приёмника: вместо p (b j ∣ a i) {\displaystyle p(b_{j}\mid a_{i})} всюду указывается p (a i ∣ b j) {\displaystyle p(a_{i}\mid b_{j})} (суммируя элементы строки можно получить , а элементы диагонали означают вероятность того, что был отправлен именно тот символ, который получен, то есть вероятность правильной передачи).

Взаимная энтропия

Взаимная энтропия или энтропия объединения предназначена для расчёта энтропии взаимосвязанных систем (энтропии совместного появления статистически зависимых сообщений) и обозначается H (A B) {\displaystyle H(AB)} , где A {\displaystyle A} характеризует передатчик, а B {\displaystyle B} - приёмник.

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

p (a 1 b 1) {\displaystyle p(a_{1}b_{1})}	p (a 1 b 2) {\displaystyle p(a_{1}b_{2})}	…	p (a 1 b j) {\displaystyle p(a_{1}b_{j})}	…	p (a 1 b m) {\displaystyle p(a_{1}b_{m})}
p (a 2 b 1) {\displaystyle p(a_{2}b_{1})}	p (a 2 b 2) {\displaystyle p(a_{2}b_{2})}	…	p (a 2 b j) {\displaystyle p(a_{2}b_{j})}	…	p (a 2 b m) {\displaystyle p(a_{2}b_{m})}
…	…	…	…	…	…
p (a i b 1) {\displaystyle p(a_{i}b_{1})}	p (a i b 2) {\displaystyle p(a_{i}b_{2})}	…	p (a i b j) {\displaystyle p(a_{i}b_{j})}	…	p (a i b m) {\displaystyle p(a_{i}b_{m})}
…	…	…	…	…	…
p (a m b 1) {\displaystyle p(a_{m}b_{1})}	p (a m b 2) {\displaystyle p(a_{m}b_{2})}	…	p (a m b j) {\displaystyle p(a_{m}b_{j})}	…	p (a m b m) {\displaystyle p(a_{m}b_{m})}

Для более общего случая, когда описывается не канал, а в целом взаимодействующие системы, матрица необязательно должна быть квадратной. Очевидно, сумма всех элементов столбца с номером j {\displaystyle j} даёт p (b j) {\displaystyle p(b_{j})} , сумма строки с номером i {\displaystyle i} есть p (a i) {\displaystyle p(a_{i})} , а сумма всех элементов матрицы равна 1. Совместная вероятность p (a i b j) {\displaystyle p(a_{i}b_{j})} событий a i {\displaystyle a_{i}} и b j {\displaystyle b_{j}} вычисляется как произведение исходной и условной вероятности.