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

Обновлено: 05.07.2024

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

Вероятность некоторого события — это величина $p$ 0 ≤ p ≤ 1 , которая показывает частоту появления этого события в ряде однотипных испытаний.

Если событие может наступить или не наступить с одинаковой вероятностью, то его вероятность: $p = 0,5$.

Американский учёный Клод Шеннон был одним из основоположников теории информации и криптографии. Им была выведена в $1948$ году формула для вычисления количества информации равновероятных событий:

I = − ∑ i = 1 N p i ⋅ log 2 p i , где $i$ — количество информации; $N$ — количество возможных событий; p i — вероятность $i$-го события.

пусть вероятность выпадения осадков в виде дождя равна $0,5$, ветра — $0,25$, грозы и молнии — $0,125$. Определим, какое количество информации получим при реализации одного из них.

I = − 0 , 5 ⋅ log 2 0,5 + 0 , 25 ⋅ log 2 0,25 + 0 , 125 ⋅ log 2 0,125 + 0 , 125 ⋅ log 2 0,125 = = − − 0,5 − 0,5 − 0,375 − 0,375 = 1,75 .

Тема урока: Формулы Хартли и Шеннона

Решение задач для подготовки к ЕГЭ

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

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

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

Известно также, что в ЕГЭ в частях А и В много задач дается именно на определение количества информации.

Цели и задачи урока состоят в том, чтобы ученики:

на примерах конкретных задач лучше поняли формулу Хартли и попробовали сами ее объяснить или вывести;
увидели применение формулы для решения типичных задач;
поняли что такое вероятность события, умели вычислить вероятность события;
увидели в чем состоит различие формул между формулами Хартли и Шеннона.

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

организационный момент, постановка целей урока – 5 минут.
повторение теоретического материала и проверка домашнего задания -20 минут.
решение задач с использованием формул Хартли и Шеннона – 15 минут
домашнее задание – 5 минут

Проверка домашнего задания и повторение теоретического материала

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

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

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

Например, если мы получили 4 бита информации, то количество возможных событий будет N = 24 = 16.

Например, для кодирования в двоичном алфавите двух состояний (0 и 1) достаточно одного бита.

Для кодирования трех состояний, например, трех сигналов светофора требуется более 1 бита, например 00 – красный, 01 – желтый, 10 – зеленый, то есть 2 бита..

Для кодирования четырех сторон света (Север, Юг, Запад, Восток) уже требуется все 4 комбинации – 00, 01, 10, 11 из 0 и 1, то есть 2 бита.

Для кодирования от 5 до 8 состояний требуется уже трехбитный код, варианты которого будут: 000, 001, 010, 011, 100, 101, 110, 111.

Можно сделать вывод: чем больше необходимо закодировать состояний (событий), тем больше требуется битов, или больше требуется количество информации. Эти события (состояния) и можно найти по формуле: N=2 I

Как можно использовать формулу для решения задач (рассказать на примере)?

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

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

Формула Хартли. Как она записывается и применяется ?

Таким образом, известная формула N=2 I является формулой Хартли, но записанной через показательную функцию.

Следует напомнить, что логарифмом числа по основанию 2 называют показатель степени (I), в которую нужно возвести основание логарифма (число 2), чтобы получить заданное число N.

Таким образом, применяя формулу Хартли, мы получаем I= log 2 16=4.

Что такое вероятность события? На каких примерах можно это можно объяснить?

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

Из урны, в которой лежат 3 красных, 2 желтых, 1 зеленый и 2 синих шара, не глядя, вынимают один шар. Требуется найти вероятности следующих событий:

Обозначим вероятности событий P А и P В соответственно.

Понятно, что вероятность того, что вынутый шар окажется красным больше, так как красных шаров больше.

Известно, что синих шара 2, значит вероятность того, что вынутый шар будет синим равна 2/8 или 1/4, то есть P А =1/4.

Так как красных и синих шаров вместе 5, то вероятность того, что вынутый шар окажется красным P в =5/8.

Ответ: P А =1/4, P в =5/8

Формула Шеннона. Чем она отличается от формулы Хартли и в каких случаях используется?

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

I = log 2 N=log 2 (1/P) или 1/P = 2 N

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

Пусть мы имеем алфавит, состоящий из N символов. Тогда частота появления каждого символа может быть записана:

P 1 , P 2 , . . . P N ,

где Pi - вероятность появления i – го символа.

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

Тогда средний информационный вес символа (количество информации, содержащееся в символе) такого алфавита выражается формулой Шеннона:

I = P 1 log 2 (1/ P 1 ) + P 2 log 2 (1/ P 2 ) + . . . + P N log 2 (1/ P N )

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

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

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

Приведите примеры использования формулы Шеннона.

Задачи.
1. Определить количество информации, получаемое при реализации одного из событий, если бросают:

а) несимметричную четырехгранную пирамидку;

б) симметричную и однородную четырехгранную пирамидку.

Решение.
а) Будем бросать несимметричную четырехгранную пирамидку.
допустим, что грани пирамидки такие, что отношение их площадей можно представить пропорцией: 4 : 2: 1: 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 (бит).
Вывод : при равновероятных событиях получаемое количество информации максимально.

Формулу Хартли теперь можно рассматривать как частный случай формулы Шеннона :

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

1. Какое минимальное количество двоичных разрядов потребуется для того, чтобы закодировать алфавит языка племени Мумба-Юмба, состоящий их 16 символов?

Решение: Пусть x – количество двоичных разрядов, тогда 2 x = 16 ; 2 x = 2 4 ; x = 4

Ответ: 4 разряда

2. 256 символов на клавиатуре кодируются последовательностью из 0 и 1. Сколько же потребуется таких 0 и 1 (то есть разрядов)?
Решение: Пусть x – количество двоичных разрядов, тогда 2 x = 256 ; 2 x = 2 8 ; x = 8
Ответ: 8 бит или 1 байт

3. Какое минимальное количество двоичных разрядов потребуется для того, чтобы закодировать цифры десятичной системы счисления?
Решение: Пусть x – количество двоичных разрядов, тогда
2 x = 10 ; 2 x = 2 3 = 8 (мало) ; 2 x = 2 4 =16 ; x = 4
Ответ: 4 разряда

4. Определить информационный объем полноэкранного графического изображения на экране, имеющем разрешающую способность 640*320 и 16 возможных цветов.
Решение: Пусть х – это количество бит, необходимых для кодирования цвета
из формулы Хартли х = log 2 16 = 4 или 16=2 4 , то есть х=4
640*320*4 = 26 *10*25*10*22=213*100 бит = 210 *100 байт = 100 Кбайт
Ответ: 100 Кбайт

5. Для хранения области экрана монитора размером 256*128 точек выделено 32 Кбайта оперативной памяти. Сколько максимально цветов допустимо использовать для раскраски точек?
Решение:
256 х 128 = 2 8 *2 7 =2 15 точек

32 Кбайт = 32 х 1024 байт = 2 5 *2 10 (32768) байт = 2 15 х 8 бит = 2 18 бит

Для цвета остается:

2 18 бит / 2 15 = 8 бит или 2 8 = 256 (количество цветов)
Ответ: 256 цветов

Все четыре события имеют разную вероятность выполнения:

P1=12/36=1/3; P2=4/36=1/9; P3=20/36=5/9; P4=1/36

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

I1=log 2 36/12=log 2 3=1.585 I2=log 2 9=3.17 I3=log 2 9/5=0.847 I4=log 2 36=5.174

Ответ : последний результат показывает, что для кодирования всех 36 карт требуется 5.174 бита или шестибитное слово (2 5 =32 – мало, 2 6 =64, то есть 64>36).

Пусть х – искомое число купейных вагонов.

Тогда P = x/16 - вероятность того, что знакомый приезжает в купейном вагоне.

Для решения используем формулу: I=log 2 1/P или 1/P = 2 I

То есть 16/х = 2 2 , 4х=16, х=4

Ответ: в поезде 4 купейных вагона.

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

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

Оценка знаний учащихся

Оценка за тест выставляется с помощью программы следующим образом:

Уровень выставления оценки можно менять в зависимости от уровня знаний учащихся и подготовки класса.

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

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

Равновероятные события

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

Рассмотрим пример, где для экзамена приготовили 40 билетов. Вероятность событий, которые произойдут при вытягивании билета, будет равна 40. Причем эти события будут равновероятны. При этом неопределенность знаний студента перед выбором билета, будет равна 40. Соответственно неопределенность знания после того как студент взял билет уменьшится в 40 раз. Зададимся вопросом, зависит ли этот показатель от номера вытянутого билета. Нет, поскольку события равновероятны.

Готовые работы на аналогичную тему

Неравновероятные события

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

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

Оценка количества информации. Формула Шеннона

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

$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$.

Рассмотрим пример, подтверждающий использование данной теории Шеннона на практике.

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

Общее количество пескарей и окуней, обитающих в озере:

$1500 + 500 = 2000$.

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

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

где $I_1$ и $I_2$ - вероятности улова пескаря и окуня соответственно.

$I = - p_1log_2p_1 - p_2log_2p_2$

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

1. При случайном падении бутерброда вероятность падения его маслом вниз (более тяжёлой стороной) больше, чем маслом вверх.

2. В коробке 20 карандашей, из них 15 красных и 5 чёрных. Вероятность вытащить наугад красный карандаш больше, чем чёрный.

Решение: Вероятность вытаскивания белого шара – P 1 = 40/50 = 0,8

Вероятность вытаскивания чёрного шара P ₂ = 10/50 = 0,2

Количество информации о вытаскивании белого шара i ₁ = log 2(1/0,8) = log 21,25

Ответ: 0,32 бит; 2,32 бит

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

Общее количество карасей и окуней в пруду 1500 + 500 = 2000.

Вероятность попадания на удочку карася

p ₁ = 1500/2000 = 0,75, окуня p ₂ – 500/2000 = 0,25.

I ₁ = log ₂(1/ p 1), I ₁ = log 2(1/ p 2), где I ₁ и I ₂ – вероятности поймать карася и окуня соответственно.

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

определяется по формуле Хартли:

Формула Хартли – частный случай формулы Шеннона

для равновероятных событий:

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

i – количество информации в битах.

Формула была предложена Р. Хартли в 1928 г.

Ральф Хартли

30 ноября 1888 г – 1 мая 1970 г

Задача 1. В коробке 32 карандаша, все карандаши разного цвета. Наугад вытащили красный. Какое количество информации при этом было получено?

Решение: Так как вытаскивание карандаша любого цвета из имеющихся в коробке 32 карандашей является равновероятным, то число возможных событий равно 32.

N = 32, i = ? N = 2 i , 32 = 25, i = 5 бит .

Задача 2. В школьной библиотеке 16 стеллажей с книгами, на каждом – по 8 полок. Ученику сообщили, что нужный учебник находится на 2-ой полке 4-го стеллажа. Какое количество информации получил ученик?

1) Число стеллажей (случаев) – 16.

N 1 = 16, N 1 = 2 I , 16 = 2 I , 16 = 24, I 1= 4 бита.

2) Число полок на каждом стеллаже (случаев) – 8,

N2 = 8, N2 = 2I, 8 = 23, I2 = 3 бит .

3) i = i1 + i2, i = 4 бита + 3 бита = 7 бит .

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

Например, загадано число 152.

1 вопрос: Число >100? Да.

3 вопрос: Число > 175? Нет. и т.д.

Количество событий в каждом варианте будет одинаково, и их отгадывание равновероятно. N = Ii , 200 = 2 i , 7 i

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 2.1. Информационная модель игры "Угадай число"

Вопрос второго участника	Ответ первого участника	Неопределенность знаний (количество возможных событий)	Полученное количество информации
16
Число больше 8?	Нет	8	1 бит
Число больше 4?	Нет	4	1 бит
Число больше 2?	Да	2	1 бит
Число 3?	Да	1	1 бит

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

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

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

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

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

I = K log 2 ⁡ N N>

Для случая определения количества информации i в одном символе алфавита мощности N, формула Хартли принимает вид:

Соответственно, мощность алфавита равна:

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

При равновероятности символов p = 1 m , m = 1 p >,m=

>> формула Хартли переходит в собственную информацию.

Сколько вопросов надо задать, чтобы найти задуманное число от 1 до 100. Допустим, загаданное число 27. Вариант диалога:

Такой формулой можно представить, сколько вопросов (битов информации) потребуется, чтобы определить одно из возможных значений. N — это количество значений, а i — количество битов. Например, в нашем примере 27 меньше, чем 28, однако больше, чем 26. Да, нам могло бы потребоваться и всего 6 вопросов, если бы загаданное число было 28.

Количество информации (i), необходимой для определения конкретного элемента, есть логарифм по основанию 2 общего количества элементов (N).

Читайте также: