Формула шеннона в информационных потоках. Основные понятия и определения информатики I. Постановка цели урока

На месте каждого символа в сообщении может стоять любой символ алфавита 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).

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

Вернемся к задаче №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 - письменно