Измерение количества информации формула шеннона. Вероятностный подход к оценке количества информации. Формула Шеннона. Просмотр содержимого презентации «Формула Шеннона»

Вероятностный подход к определению количества информации 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 класса, профильный уровень.

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 - письменно

1928 год американский инженер Ральф Хартли рассматривает процесс получения информации как выбор одного сообщения из конечного заданного множества N равновероятных событий.

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

где К - количество информации, N -число равновероятных событий.

Формула Хартли может быть записана и так: N=2k

Так как наступление каждого из N событий имеет одинаковую вероятность P, то:

где P- вероятность наступления события.

Тогда, формулу можно записать иначе:

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

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

K = - (p1 *log2 p1+ p2 *log 2p 2 + p 3 *log 2p 3 +…+ pi * log2 pi),

где pi вероятность того, что именно i-е сообщение выделено в наборе из N сообщений.

Также эту формулу записывают:

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

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

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

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

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

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

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

Объемный подход.

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

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

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

Энтропийный (вероятностный) подход.

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

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

Подход Р. Хартли основан на фундаментальных теоретико-множественных, по существу комбинаторных основаниях, а также нескольких интуитивно ясных и вполне очевидных предположениях.

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

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

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

Чем больше элементов в множестве, тем больше неопределенность выбора, тем больше информации.

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

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

Клод Шеннон предположил, что прирост информации равен утраченной неопределённости, и задал требования к её измерению:

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

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

определена и непрерывна для всех,

где для всех и. (Нетрудно видеть, что эта функция зависит только от распределения вероятностей, но не от алфавита).

Для целых положительных, должно выполняться следующее неравенство:

Для целых положительных, где, должно выполняться равенство:

информационный пропускной энтропийный

Шеннон определил, что измерение энтропии, применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надёжной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидание «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка -- имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т.д.

(Claude Elwood Shannon, 30 апреля 1916 - 24 февраля 2001) - американский математик и электротехник, один из создателей математической теории информации, в значительной мере предопределил своими результатами развитие общей теории дискретных автоматов, которые являются важными составляющими кибернетики. В 1936 году закончил Мичиганский университет. После защиты диссертации (1940) в 1941 году поступил на работу в знаменитые Лаборатории Белла.

С 1956 года преподавал в МТИ.

Большую ценность представляет другая работа - Communication Theory of Secrecy Systems (1949), в которой сформулированы математические основы криптографии.

С 1956 - член Национальной академии наук США и Американской академии искусств и наук

Процесс передачи информации

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

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

Примеры

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

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

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

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

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

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

I=- (p1 log2 p1 + p2 log2 p2 + … + pN log2 pN)

где pi - вероятность того, что именно i-е сообщение выделено в наборе из N сообщений.

Легко заметить, что если вероятности p1, …, pN равны, то каждая из них равна 1/N, и формула Шеннона превращается в формулу Хартли.

Помимо двух рассмотренных подходов к определению количества информации, существуют и другие.

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

В качестве единицы информации условились принять один бит (английский bit - binary, digit - двоичная цифра).

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

А в вычислительной технике битом называют наименьшую;порцию; памяти, необходимую для хранения одного из двух знаков «0» и «1», используемых для внутримашинного представления данных и команд.

где I - количество информации;
N - количество возможных событий;
р i - вероятность i-го события.

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

Р 1 = 1/2, р 2 = 1/4, р 3 = 1/8, р 4 = 1/8.

Тогда количество информации, которое мы получим после реализации одного из них, можно рассчитать по формуле (2.2):

I = -(l/2 log 2 l/2 + l/4 log 2 l/4 + l/8 log 2 l/8 + l/8 log 2 l/8) = (1/2 + 2/4 + 3/8 + 3/8) битов = 14/8 битов = 1,75 бита.

Этот подход к определению количества информации называется вероятностным .

Для частного, но широко распространенного и рассмотренного выше случая, когда события равновероятны (p i = 1/N), величину количества информации I можно рассчитать по формуле:

(2.3)

По формуле (2.3) можно определить, например, количество информации, которое мы получим при бросании симметричной и однородной четырехгранной пирамидки:

I = log 2 4 = 2 бита. Таким образом, при бросании симметричной пирамидки, когда события равновероятны, мы получим большее количество информации (2 бита), чем при бросании несимметричной (1,75 бита), когда события неравновероятны.

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

Выбор оптимальной стратегии в игре "Угадай число". На получении максимального количества информации строится выбор оптимальной стратегии в игре "Угадай число", в которой первый участник загадывает целое число (например, 3) из заданного интервала (например, от 1 до 16), а второй - должен "угадать" задуманное число. Если рассмотреть эту игру с информационной точки зрения, то начальная неопределенность знаний для второго участника составляет 16 возможных событий (вариантов загаданных чисел).

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

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

Задания

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

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

1.4. Вероятность первого события составляет 0,5, а второго и третьего - 0,25. Какое количество информации мы получим после реализации одного из них?

1.5. Какое количество информации получит второй игрок в игре "Угадай число" при оптимальной стратегии, если первый игрок загадал число: от 1 до 64? От 1 до 128?

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

Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии 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 бит на символ, что конечно будет варьироваться для разных текстов. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для её зашифровки без потери информации, при оптимальном кодировании.

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

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

Неотрицательность : H (X) ⩾ 0 {\displaystyle H(X)\geqslant 0} .
Ограниченность : 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} .
Если независимы, то H (X ⋅ Y) = H (X) + H (Y) {\displaystyle H(X\cdot Y)=H(X)+H(Y)} .
Энтропия - выпуклая вверх функция распределения вероятностей элементов.
Если 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}} вычисляется как произведение исходной и условной вероятности.