Формула шеннона в теории вероятности. Формула шеннона в информационных потоках. Вариации и обобщения
Своё дальнейшее развитие теория информации получила в работах Клода Шеннона, американского инженера и математика (1916 – 2001). Шеннон является одним из создателей математической теории информации. Его основные труды посвящены теории релейно-контактных схем, математической теории связи, кибернетике. К. Шеннон изучал вопросы передачи информации в телеграфии, телефонии или радиовещании в виде сигналов электромагнитных колебаний. Одна из задач, которую ставил перед собой К. Шеннон, заключалась в том, чтобы определить систему кодирования, позволяющую оптимизировать скорость и достоверность передачи информации. Так как в годы войны он служил в шифровальном отделе, где занимался разработкой криптографических систем, то это позже помогло ему открыть методы кодирования с коррекцией ошибок. В своих работах 1948-1949 годов К. Шеннон определил количество информации через энтропию - величину, известную в термодинамике и статистической физике как мера разупорядоченности системы, а за единицу количества информации принял то, что впоследствии назвали битом (bit).
Для дальнейшего изложения необходимо использовать некоторые понятия теории вероятности: случайное событие, опыт, вероятность события, случайная величина. В окружающем нас мире происходят различные события, причём мы можем интуитивно, основываясь на опыте, оценивать одни из них как более возможные, чем другие. Случайным называют событие, которое может наступить или не наступить в результате некоторого испытания, опыта или эксперимента. Будем обозначать события заглавными буквами A, B, C и т.д. Количественная мера возможности наступления некоторого события A называется его вероятностью и обозначается как p(A), p – от английского probability. Чем более возможно наступление случайного события, тем больше его вероятность: если A более возможно чем B, то p(A) > p(B). Вводится понятие достоверного события – событие, которое обязательно наступит. Это событие обозначают W и полагают, что его вероятность p(W) = 1. Невозможным называют событие, которое никогда не произойдёт. Его обозначают Æ и полагают, что его вероятность p(Æ) = 0. Для вероятностей всех остальных событий A выполняется неравенство p(Æ) < p(A) < p(W), или 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. Так как Sр 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 , вычисленное по формуле Шеннона, равно Напомним, что 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) достигается в том случае, когда все состояния системы равновероятны. Это означает, что В 1928 г. американский инженер
Р. Хартли предложил научный подход к
оценке сообщений. Предложенная им
формула имела следующий вид: I
= log 2 K ,
Где К - количество
равновероятных событий; I - количество
бит в сообщении, такое, что любое из К
событий произошло. Иногда формулу Хартли
записывают так: I
= log 2 K = log 2 (1 / р) = - log 2 р,
т. к. каждое из К событий имеет
равновероятный исход р = 1 / К, то К = 1 / р. Задача.
Шарик находится в одной из
трех урн: А, В или С. Определить сколько
бит информации содержит сообщение о
том, что он находится в урне В. Такое сообщение содержит I =
log 2 3 = 1,585 бита информации. Но не все ситуации имеют
одинаковые вероятности реализации.
Существует много таких ситуаций, у
которых вероятности реализации
различаются. Например, если бросают
несимметричную монету или "правило
бутерброда". "Однажды в детстве я уронил
бутерброд. Глядя, как я виновато вытираю
масляное пятно, оставшееся на полу,
старший брат успокоил меня: Не горюй, это
сработал закон бутерброда. Что еще за закон
такой? - спросил я. Закон, который
гласит: "Бутерброд всегда падает
маслом вниз". Впрочем, это шутка, -
продолжал брат.- Никакого закона нет.
Прсто бутерброд действительно ведет
себя довольно странно: большей частью
масло оказывается внизу. Давай-ка еще пару
раз уроним бутерброд, проверим, - предложил
я. - Все равно ведь его придется выкидывать. Проверили. Из десяти раз восемь
бутерброд упал маслом вниз. И тут я задумался: а можно ли
заранее узнать, как сейчас упадет
бутерброд маслом вниз или вверх? Наши опыты прервала мать…"
(Отрывок из книги "Секрет великих
полководцев", В.Абчук). В 1948 г. американский инженер
и математик К Шеннон предложил формулу
для вычисления количества информации
для событий с различными вероятностями.
Если
I - количество информации,
К
- количество возможных событий,
рi
- вероятности отдельных событий,
то
количество информации для событий с
различными вероятностями можно определить
по формуле: I
= - Sum р i log 2 р i ,
где i
принимает значения от 1 до К. Формулу Хартли теперь можно
рассматривать как частный случай формулу
Шеннона: I
= - Sum 1 / К log 2
(1 / К) = I = log 2
К. При равновероятных событиях
получаемое количество информации
максимально. Задачи.
1. Определить
количество информации, получаемое при
реализации одного из событий, если
бросают
а) несимметричную четырехгранную
пирамидку;
б) симметричную и однородную
четырехгранную пирамидку.
Решение.
а)
Будем бросать несимметричную четырехгранную
пирамидку.
Вероятность отдельных
событий будет такова:
р1 = 1 / 2,
р2 = 1 /
4,
р3 = 1 / 8,
р4 = 1 / 8,
тогда количество
информации, получаемой после реализации
одного из этих событий, рассчитывается
по формуле:
I = -(1 / 2 log 2 1/2 + 1 / 4 log 2 1/4 + 1 / 8 log 2 1/8 + 1 / 8 log 2 1/8) = 1 / 2
+ 2 / 4 + + 3 / 8 + 3 / 8 = 14/8 = 1,75 (бит).
б) Теперь
рассчитаем количество информации,
которое получится при бросании
симметричной и однородной четырехгранной
пирамидки:
I = log 2 4 = 2 (бит).
2.
Вероятность перового события составляет
0,5, а второго и третьего 0,25. Какое
количество информации мы получим после
реализации одного из них?
3. Какое
количество информации будет получено
при игре в рулетку с 32-мя секторами? Физиологи и психологи научились
определять количество информации,
которое человек может воспринимать при
помощи органов чувств, удерживать в
памяти и подвергать обработке. Информацию
можно представлять в различных формах:
звуковой, знаковой и др. рассмотренный
выше способ определения количества
информации, получаемое в сообщениях,
которые уменьшают неопределенность
наших знаний, рассматривает информацию
с позиции ее содержания, новизны и
понятности для человека. С этой точки
зрения в опыте по бросанию кубика
одинаковое количество информации
содержится в сообщениях "два",
"вверх выпала грань, на которой две
точки" и в зрительном образе упавшего
кубика. При передаче и хранении
информации с помощью различных технических
устройств информацию следует рассматривать
как последовательность знаков (цифр,
букв, кодов цветов точек изображения),
не рассматривая ее содержание. Считая, что алфавит (набор
символов знаковой системы) - это событие,
то появление одного из символов в
сообщении можно рассматривать как одно
из состояний события. Если появление
символов равновероятно, то можно
рассчитать, сколько бит информации
несет каждый символ. Информационная
емкость знаков определяется их количеством
в алфавите. Чем из большего количества
символов состоит алфавит, тем большее
количество информации несет один знак.
Полное число символов алфавита принято
называть мощностью алфавита. Молекулы ДНК (дезоксирибонуклеиновой
кислоты) состоят из четырех различных
составляющих (нуклеотидов), которые
образуют генетический алфавит.
Информационная емкость знака этого
алфавита составляет: 4
= 2 I , т.е. I = 2 бит. При таком подходе в результате
сообщения о результате бросания кубика, получим различное количество информации,
Чтобы его подсчитать, нужно умножить
количество символов на количество
информации, которое несет один символ. Количество информации, которое
содержит сообщение, закодированное с
помощью знаковой системы, равно количеству
информации, которое несет один знак,
умноженному на число знаков в сообщении. Например, пусть при бросании несимметричной четырехгранной пирамидки вероятности отдельных событий будут равны: Р 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) можно определить, например, количество информации, которое мы получим при бросании симметричной и однородной четырехгранной пирамидки: I = log 2 4 = 2 бита. Таким образом, при бросании симметричной пирамидки, когда события равновероятны, мы получим большее количество информации (2 бита), чем при бросании несимметричной (1,75 бита), когда события неравновероятны. Количество информации, которое мы получаем, достигает максимального значения
, если события равновероятны
.
Выбор оптимальной стратегии в игре "Угадай число".
На получении максимального количества информации строится выбор оптимальной стратегии в игре "Угадай число", в которой первый участник загадывает целое число (например, 3) из заданного интервала (например, от 1 до 16), а второй - должен "угадать" задуманное число. Если рассмотреть эту игру с информационной точки зрения, то начальная неопределенность знаний для второго участника составляет 16 возможных событий (вариантов загаданных чисел). При оптимальной стратегии интервал чисел всегда должен делиться пополам, тогда количество возможных событий (чисел) в каждом из полученных интервалов будет одинаково и отгадывание интервалов равновероятно. В этом случае на каждом шаге ответ первого игрока ("Да" или "Нет") будет нести максимальное количество информации (1 бит). Как видно из табл. 1.1, угадывание числа 3 произошло за четыре шага, на каждом из которых неопределенность знаний второго участника уменьшалась в два раза за счет получения сообщения от первого участника, содержащего 1 бит информации. Таким образом, количество информации, необходимое для отгадывания одного из 16 чисел, составило 4 бита. Задания
1.3. Вычислить с помощью электронного калькулятора количество информации, которое будет получено: 1.4. Вероятность первого события составляет 0,5, а второго и третьего - 0,25. Какое количество информации мы получим после реализации одного из них? 1.5. Какое количество информации получит второй игрок в игре "Угадай число" при оптимальной стратегии, если первый игрок загадал число: от 1 до 64? От 1 до 128? Вероятностный подход к определению количества информации 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 класса, профильный уровень. Н.Д.Угринович, методическое пособие «Информатика и ИКТ 8 -11 класс» Какое сообщение содержит большее количество информации? 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
Решить задачи: Company Logo
Ответьте на вопросы: Company Logo
Домашнее задание: В основе нашего мира лежат три составляющие: вещество, энергия и информация. Как много в мире вещества, энергии и информации? Можно ли их измерить и как именно? Нам известны способы измерения количества вещества и энергии. Но как быть с информацией? Можно ли ее измерить? Ранее уже отмечалось, что существует несколько подходов к оценке количества информации. Сейчас мы более подробно остановимся на одном из них. Любое сообщение будет являться информативным, если оно пополняет знания человека, т.е. уменьшает неопределенность его знаний. Пример 1
Например, при подбрасывании монеты мы пытаемся угадать, какой стороной она упадет. Возможен один из вариантов исхода: монета окажется в положении «орел» или «решка». Каждое из этих двух событий окажется равновероятным, т. е. ни одно из них не имеет преимущества перед другим. Перед подбрасыванием монеты никто не может знать, как она упадет, т.е. существует неопределенность знания. После же наступления события, наоборот, присутствует полная определенность, так как бросающий получает зрительное сообщение о положении монеты, которое, в свою очередь, уменьшает неопределенность его знания в два раза, поскольку из двух равновероятных событий произошло одно. Пример 2
Другим примером является ситуация с шестигранным кубиком, т.е. перед броском никто не может знать, какой стороной он упадет. В данном случае присутствует возможность получить один результат из шести равновероятных. Таким образом, до броска неопределенность знаний бросающего будет равна 6, после же броска, она уменьшится ровно в 6 раз, поскольку именно 6 равновероятных событий может произойти. Пример 3
Рассмотрим пример, где для экзамена приготовили 40 билетов. Вероятность событий, которые произойдут при вытягивании билета, будет равна 40. Причем эти события будут равновероятны. При этом неопределенность знаний студента перед выбором билета, будет равна 40. Соответственно неопределенность знания после того как студент взял билет уменьшится в 40 раз. Зададимся вопросом, зависит ли этот показатель от номера вытянутого билета. Нет, поскольку события равновероятны. Проанализировав все рассмотренные выше примеры, можно прийти к выводу, что чем больше исходное число возможных равновероятных событий, тем в большее количество раз уменьшается неопределенность знаний, и тем большее количество информации будет содержаться в сообщении о результатах опыта. Рассмотрим в качестве примера разговорные языки. Обратимся к фактам доказанных исследований, которые показывают, что во всех разговорных языках одни буквы встречаются гораздо чаще, чем другие. Результаты исследований подтверждают, что на $1000$ букв в разных разговорных языках приходится различное число повторений. В качестве примеров в таблице приведены некоторые буквы в русском и английском языках: Рисунок 1.
Помимо этого, вероятность появления отдельных букв будет зависеть от того, какие буквы используются перед ними. Так, в русском языке после гласной никогда не может стоять мягкий знак, а также в словах не используются четыре гласные подряд и т.д. Разговорные языки имеют, как правило, свои особенности и закономерности. Именно поэтому количество информации, содержащееся в сообщениях любого разговорного языка, неприемлемо оценивать с помощью формулы Хартли, которая используется в алфавитном подходе к оценке информации и характерна для примеров с равновероятными событиями (примеры с монетой и кубиком). Как определить, какое количество информации содержит, например, текст романа "Война и мир", или фрески и полотна великих итальянских художников, или генетический код человека? Ответы на эти вопросы и подобные им науке пока не известны и, по всей вероятности, еще не скоро будут известны. Однако всех интересует, возможно ли объективно оценить количество информации? К задаче подобного рода можно отнести следующий пример. Как выяснить, являются ли равновероятными сообщения "первой выйдет из здания женщина" и "первым выйдет из здания мужчина"? Однозначного ответа на этот вопрос нет. Все будет зависеть от того, о каком именно здании идет речь. Если это, например, здание гинекологической клиники, то вероятность выйти первой у женщины очень высока, если это военная казарма, то вероятность выйти первым для мужчины будет выше, чем для женщины, а вот если это здание кинотеатра, то вероятности выйти первыми для мужчины и женщины будут одинаковыми. Для решения задач подобного рода используется общая оценка количества информации, предложенная американским учёным Клодом Шенноном в 1948г.
Созданная им формула определения количества информации способна учитывать возможную неодинаковую вероятность сообщений, содержащихся в наборе. Шеннон при создании формулы использовал применяемую в математике и гидродинамике вероятностную меру неопределенности
(называемую энтропией) для того, чтобы в полной мере оценить состояние изучаемой системы и получить максимально возможную информацию о протекающих в этой системе процессах. Эта оценка количества информации, по существу, является вероятностной мерой
, и, как оценка неопределенности, она отражает способность какого-либо источника проявлять все новые и новые состояния и таким образом отдавать информацию. Определение 1
Шеннон определил энтропию
как среднюю логарифмическую функцию множества вероятностей возможных состояний системы (возможных исходов опыта). Для расчета энтропии Шеннон предложил следующее уравнение: $H= -(p_1log_2p_1+p_2log_2p_2+. . .+p_Nlog_2p_N)$, где $p_i$ - вероятность появления $i$-того события в наборе из $N$ событий. Тогда количество информации, полученное в результате опыта, будет не что иное, как разность между энтропией системы до ($H_0$) и после ($H_1$) опыта: причем если неопределенность в результате опыта полностью исключается, то имеем: $I=\Sigma (p_ilog_2p_i), i=1,\dots ,N$. Рассмотрим пример, подтверждающий использование данной теории Шеннона на практике. Пример 4
В озере обитают пескари и окуни. Подсчитано количество особей в каждой популяции (пескарей - $1500$, а окуней - $500$). Необходимо определить, сколько информации содержится в сообщениях о том, что рыбак выловил пескаря, окуня, вообще рыбу? Решение.
События улова пескаря или окуня не являются равновероятными, поскольку окуней в озере обитает намного меньше, чем пескарей. Общее количество пескарей и окуней, обитающих в озере: $1500 + 500 = 2000$. Определим вероятность улова пескаря: $p_1= \frac{1500}{2000} = 0,75$, Определим вероятность улова окуня: $p_2 - \frac{500}{2000} = 0,25$. $I_1=log_2(\frac{1}{p_1}), I_1=log_2(\frac{1}{p_2})$, где $I_1$ и $I_2$ - вероятности улова пескаря и окуня соответственно. Количество информации, содержащейся в сообщении об улове пескаря: $I_1 = log_2(\frac{1}{0,75}) » 0,43$ бит, Количество информации, содержащейся в сообщении об улове окуня: $I_2=log_2(\frac{1}{0,25}) » 2$ бит. Количество информации, содержащейся в сообщении об улове рыбы (карася или окуня) рассчитывается по формуле Шеннона: $I = - p_1log_2p_1 - p_2log_2p_2$ $I = -0,75 \cdot log_20,75- 0,25 \cdot log_20,25=-0,75 \cdot (\frac{log0,75}{log2})-0,25 \cdot(\frac{log0,25}{log2}) =0,604 бит » 0.6$ бит. Ответ:
в сообщении содержится $0,6$ бит информации
где I - количество информации;
N - количество возможных событий;
р i - вероятность i-го события.
(2.3)
Просмотр содержимого документа
«Теория»
http://marknet.narod.ru/spr/list5.htm
Информатика. Справочный материал.
Количество информации. Формулы Хартли и Шеннона
Просмотр содержимого презентации
«Формула Шеннона»
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"
Равновероятные события
Неравновероятные события
Оценка количества информации. Формула Шеннона
