Информатика задачи на вероятностный подход

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

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

по формуле Шеннона:

где Pi — вероятность i -го события,

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

Формула была предложена в 1948 г.

а мериканский учёный,

(30 апреля 1916 — 24 февраля 2001 )

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

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

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

Количество информации в сообщении о некотором событии зависит от его вероятности. Чем меньше вероятность события, тем больше информации оно несёт.
P = K / N , где К — количество случаев реализации одного из исходов события, N — общее число возможных исходов одного из событий 2 i = log 2(1/ p ), где i — количество информации, p — вероятность события

Задача 1. В коробке 50 шаров, из них 40 белых и 10 чёрных. Определить количество информации в сообщении о вытаскивании наугад белого шара и чёрного шара.

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

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

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

= log 1,25/ log 2 » 0,32 бит

Количество информации о вытаскивании чёрного шара i2 = log2(1/0,2) = log25 = log5/log2 » 2,32 бит

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

Задача 2. В озере живут караси и окуни. Подсчитано, что карасей 1500, а окуней — 500. Сколько информации содержится в сообщениях о том, что рыбак поймал карася, окуня, поймал рыбу?

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

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

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

p 1 = 1500/2000 = 0,75, окуня p 2 — 500/2000 = 0,25.

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

I 1 = log 2(1 / 0,75) » 0,43 бит, I 2 = log 2(1 / 0,25) » 2 бит — количество информации в сообщении поймать карася и поймать окуня соответственно.

Количество информации в сообщении поймать рыбу (карася или окуня) рассчитывается по формуле Шеннона

I = — 0,75*log20,75 — 0,25*log20,25 = — 0,75*(log0,75/log2) −0,25*(log0,25/log2) = 0,604 бит » 0.6 бит.

Ответ: в сообщении содержится 0,6 бит информации

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

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

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

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

где 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 бит .

Задача 3. Загадывают число в диапазоне от 1 до 200. Какое наименьшее количество вопросов надо задать, чтобы наверняка отгадать число. На вопросы можно отвечать только «Да» или «Нет».

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

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

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

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

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

Система задач на использование вероятностного подхода.

Решение задач данной группы надо начинать с определения исходов (равновероятностных или разновероятностных), заданного в условии задачи.

Решение задач с равновероятностными исходами.

Количество информации в случае равных вероятностей исходов события определяется по формуле Хартли: I=log​2 N или 2 ​I =N, где i- количество информации в полученном сообщении, N-количество возможных исходов события.

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

Читайте также:  Знакомания моя страница вход

Решение. Так как в коробке все карандаши разного цвета, поэтому вероятность вытащить карандаш любого цвета одинакова, и равна 1/16, т.е. количество вариантов в сообщении, что «вытащили карандаш такого-то цвета» равна N=16.

Воспользуемся формулой I=log​2​N в нашем случае

I= log216,

I=log22 4 ,

I=4 бит.

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

2 I =N,

2 I =16, 2 I =2 4 ,

I=4 бит.

Ответ: количество информации в сообщение о том, что из коробки с карандашами вытащили карандаш красного цвета равно 4 бит.

Задача 2. Сообщение о том, что Вася живет в пятом подъезде, несет 4 бита информации. Сколько подъездов в доме?

Решение. Эта задача является «обратной! По отношению к задачи 1. Для решения данной задачи используется формула Хартли 2 I =N.

В условии задан информационный вес сообщения I=4бит.

Необходимо найти количество возможных событий (в данном случае, количество подъездов в доме)

2 I =N,

2 4 = N,

2 4 =16,

N =16 (под.)

Ответ: в доме 16 подъездов.

Задача 3. Друзья рисовали плакат с надписью «С днем рождения, Наташа!» У них был набор баночек с краской различных цветов. Сколько баночек с цветной краской было у ребят, если сообщение о том, что надпись была красного цвета, несет 3 бит информации?

Решение. Для решения данной задачи также используется формула Хартли 2 I =N.

В условии известен информационный вес сообщения I=3бит.

Необходимо найти количество возможных событий (в данном случае, количество баночек с краской)

2 I =N,

2 3 = N,

2 3 =8,

N=8 (б.)

Ответ: у ребят было 8 баночек с краской разного цвета.

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

Решение. Для решения данной задачи также используется понятие равновероятных событий и формула Хартли 2 I =N.

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

N1 = 16,

2 I =N,

2 I =16,

2 4 =16,

I1= 4 бита — количество информации, в сообщении, что книга находится на таком — то стеллаже.

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

N2 = 8,

2 I =N,

2 I =8,

2 3 =8,

I2= 3 бита — количество информации, в сообщении, что книга находится на таком — то стеллаже.

3) I = I1 + I2,

I = 4 бита + 3 бита = 7 бит.

Ответ: информационный объем сообщения о том, что книга находится на определённом месте, равен 7 бит.

Задача 5. Загадывается число в диапазоне от 1 до 200. Какое наименьшее количество вопросов надо задать, чтобы отгадать число, если на вопросы можно отвечать только «Да» или «Нет»?

Решение. Самый длинный, нерациональны способ отгадывания этого числа- это задание вопросов типа «Это число 1», «Это число 2» и т.д. Если задуманное число 199, нужно задать 199 вопросов. Другой, но тоже нерациональный способ просто наугад называть число из указанного диапазона. Рациональнее задавать такие вопросы, которые уменьшают количество вариантов вдвое. Например, если загадано число 152, то такими вопросами могут быть

1 вопрос: Число >100? Да (Вариантов 100)

2 вопрос: Число 175? Нет (Вариантов 25) и т.д.

Вероятность ответов «Да» и «Нет» в каждом из наборов вариантов одинаковая, воспользуемся формулой Хартли 2 I =N.

2 I =200,

т.к. 2 7 =128, а 2 8 =256, то 7 I =N) правильнее было бы записать так: наименьшее целое I такое, что 2 I >=N.

Для отгадывания числа нужно задать 8 вопросов. Продолжим задавать вопросы для числа 152.

4 вопрос: Число > 160? Нет

5 вопрос: Число > 155? Нет

6 вопрос: Число 151? Да

8 вопрос: Число =152? Да

Ответ: Наименьшее количество вопросов для отгадывания числа равно 8.

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

Количество информации в случае различных вероятностей событий определяется по формуле Шеннона:

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

Pi — вероятности i-го исхода событий;

Ii -частное количество информации, получаемое в случае реализации i-ого исхода;

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

Ki — количество случаев реализации i-го события.

Задача 1. В реке обитают щуки и сомы. Подсчитано, что щук 1500, а сомов — 500. Сколько информации содержится в сообщениях о том, что рыбак поймал щуку, сома, поймал рыбу?

Решение. События поимки щуки или сома не являются равновероятными, так как сомов в озере меньше, чем щук. Общее количество щук и сомов в реке 1500 + 500 = 2000.

Pi=k/N, Pi- вероятность i-го исхода событий

Вероятность попадания на удочку щуки P1=K1/N, где K1-количество щук в реке, N— общее количество рыб в реке.

Читайте также:  Брянск 50 письмо заказное что это такое

P1 = 1500/2000 = 0,75.

Вероятность попадания на удочку сома P2 = 500/2000 = 0,25.

I1 = log2(1/P1), I2 = log2(1/P2), где I1 и I2 — количество информации в сообщении когда поймали щуки или сома соответственно.

I1 = log2(1 / 0,75) ≈ 0,42 бит, I2 = log2(1 / 0,25)≈2 бит — количество информации в сообщении поймали щуку или поймали сома соответственно.

Количество информации в сообщении поймали любую рыбу рассчитывается по формуле Шеннона

I = P1log2(1/P1)+ P2log2(1/P2) I = 0,75*0,42+0,25*2 =0,815бит≈0,8бит

Ответ: в сообщении о том, что поймали щуку, содержится 0,42бит, поймали сома — 2бит, поймали рыбу- 0,8 бит информации.

Задача 2. На автостоянке находятся автомобили черного, красного и белого цветов, причем 36 из них красного цвета. Информационный объем сообщения «На стоянку заехал автомобиль белого цвета» равен 8 бит. Количество информации в сообщении «На стоянку заехал не черный автомобиль» равно 6 битам. Определите, какова вместимость автостоянки и сколько на стоянке белых, красных и черных авто.

Решение. В данной задаче разное количество автомобилей черного, красного и белого цвета, поэтому въезд на стоянку автомобиля определенного цвета имеет разную вероятность. Будем использовать формулу Шеннона.

Из условия задачи имеем

Iб = log2(1/Pб ),​ где Iб-количество информации в сообщении «На стоянку заехал автомобиль белого цвета»

8=log2(1/Pб), где Рб— вероятность въезда белого автомобиля.

1/Рб=2 8 , тогда Рб=½ 8 =1/256.

Обозначим через N количество автомобилей на стоянке.

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

Р​К =36/N, где Рк — вероятность въезда красного автомобиля.

Используя информационный объем сообщения «На стоянку заехал не черный автомобиль» (т.е. белый или красный), определим, вероятность встречи не черного автомобиля

6=log​2​(1/Р​б+кр​) , следовательно 1/Рб+кр=2 ​6 ,

Так как Р​б+кр​=Р​б​кр​=1/64, получим, 1/256+36/N=1/64, тогда (N+36×256)/(256+N)=1/64

64(N+9216)=256N,

N+9216=4N,

3N=9216,

N=3072 — количество машин на автостоянке.

Т.к. Рб=Nб/N, где Nб — количество автомобилей белого цвета,

Nб=N/256=3072/256=12 — количество автомобилей белого цвета.

Пусть — количество автомобилей черного цвета, тогда

Nч= N- Nб— Nкр=3072−12−36=3024-количество автомобилей черного цвета.

Ответ: на автостоянке 3072 машины, среди них 12− автомобили белого цвета, 36-красного, 3024-черного цвета.

Задача 3. У скупого рыцаря в сундуке золотые, серебряные и медные монеты. Каждый вечер он извлекает из сундука одну из лежащих в нем 96 монет, любуется ею и кладет обратно в сундук. Количество информации, содержащееся в сообщении «Из сундука извлечена серебряная монета», равно четырем битам. Информационный объем сообщения «Из сундука извлечена золотая монета» равен пяти битам. Определить количество медных, золотых и серебряных монет в сундуке.

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

Из условия задачи имеем 4=log2​(1/Р​с​), где Рс- вероятность извлечения купцом из сундука серебряной монеты.

1/Рс=2 ​4 , тогда Рс=½ ​4 =1/16.

Обозначим через N количество монет в сундуке, тогда из условия задачи имеем. Рс=Nc/N, где Nс — количество серебряный монет в сундуке,

N=96-по условию задачи.

1/16=Nc/96 ,

Nc=96/16=6-серебряных монет в сундуке.

Аналогичным образом находится количество золотых монет , 5=log​2​(1/Рз), где Рз- вероятность извлечения золотой монеты.

1/Рз=2 ​5 , тогда Рз=½ 5 =1/32.

Рз=Nз/N ,где Nз — количество золотых монет в сундуке,

N=96-по условию задачи.

1/32=Nз/96 ,

Nз=96/32=3-золотых монеты в сундуке.

Nм=N-Nc-Nз,

Nм=96−6−3=87 — медных монет в сундуке.

Ответ: В сундуке 87 медных, 3 золотых, 6 серебряных монет.

Задача 4. В многоквартирном доме имеются однокомнатные, двухкомнатные и трехкомнатные квартиры. Для анкетирования наудачу выбирается одна из квартир. Информационный объем сообщения «Квартира не двухкомнатная» равен 7-log224бит. Количество информации в сообщении «Квартира не однокомнатная» равно 7-log2120бит. Определите количество информации в сообщении «Квартира трехкомнатная».

Решение. Проведем преобразование числового выражения 7-log224: заменив число 7 на log2128 и применив правило вычисления разности логарифмов получим: 7-log​2​24=log2128-log224=log2(128/24).

Следовательно, информационный объем сообщения «Квартира не двухкомнатная» (т.е. однокомнатная или трехкомнатная) равен:

Аналогичным образом проведем преобразование числового выражения 7-log2120.

Информационный объем сообщения «Квартира не однокомнатная» (т.е. двухкомнатная или трехкомнатная) равен: I2+3=log2(128/120) .

Читайте также:  База данных автосалона пример

Используя формулу Шеннона Ii=log2(1/Pi) можно вычислить вероятность выбора в многоквартирном доме не двухкомнатной квартиры, т.е. однокомнатной или трехкомнатной:

log2(128/24)=log2(1/P1+3), тогда 128/24=1/P1+3 , следовательно P1+3=24/128.

Аналогичным образом вычислим вероятность выбора не однокомнатной квартиры (т.е. двухкомнатной или трехкомнатной).

log2(128/120)=log2(1/P2+3), тогда 128/120=1/P2+3 следовательно P2+3=120/128.

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

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

Теперь по формуле Шеннона подсчитаем информационный объем сообщения «Квартира трехкомнатная»:

Ответ: в сообщении «Квартира трехкомнатная» содержится 3 бит информации.

Представлен конспект урока информатики в 10 классе по теме «Вероятностный подход к определению количества информации». Разбираются типовые задачи по этой теме.

Скачать:

Вложение Размер
statya.rar 394.24 КБ

Предварительный просмотр:

Конспект урока информатики в 10 классе

Тема урока: «Вероятностный подход к определению количества информации»

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

Тип урока : урок изучения нового материала.

Оборудование: компьютерный класс, оборудованный компьютерами Pentium I и выше, лицензионное ПО: операционная система Windows 97/2000/XP, MS Office 2000 и выше, интерактивная доска, проектор.

2.Объяснение нового материала (сопровождается презентацией — приложение 1 ):

Введение понятия «количество информации»

-Можно ли измерить количество вещества и как именно?

-Можно ли определить количество энергии?

-Можно ли измерить количество информации и как это сделать? ( правильного ответа на этот вопрос учащиеся не дадут ).

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

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

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

Пример. Первоклассник изучает таблицу умножения. Учитель сообщает ему, что 2 х 2 = 4. Первоклассник этого раньше не знал, поэтому такое сообщение содержит для него информацию. А для ученика 5 класса таблица умножения хорошо известна, поэтому из такого сообщения информацию он не получит.

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

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

Следовательно, можно сказать так: неопределенность знаний — это количество возможных результатов события (бросания монеты, кубика; вытаскивания жребия и пр.)

На экзамен приготовлено 20 билетов.

  • Чему равно количество событий, которые могут произойти при вытягивании билета? (2 0 )
  • Равновероятны эти события или нет? ( да )
  • Чему равна неопределенность знаний ученика перед тем как он вытянет билет? (2 0 )
  • Во сколько раз уменьшится неопределенность знания после того как ученик билет вытянул? (2 0 )
  • Зависит ли этот показатель от номера вытянутого билета? ( нет )

Вернемся к примеру с монетой. Предположим, что у монеты обе стороны «орел».

  • Существует ли неопределенность знаний перед броском в этом случае? Почему? ( нет, заранее знаем, что выпадет «орел»)
  • Получите вы новую информацию после броска? ( нет, ответ знаем заранее )
  • Будет ли информативным сообщение о результате броска? ( не будет, поскольку оно не принесло новых и полезных знаний)
  • Чему равно количество информации в этом случае? ( нулю, так как данное сообщение является неинформативным)

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

За единицу измерения информации принимается уменьшение неопределенности знаний человека в 2 раза.

Эта единица называется битом и является минимальной единицей информации.

Игра «Угадай число».

Один из учеников загадывает число из интервала от 1 до 16. Учитель задает вопросы, ученик на них отвечает, и весь класс вместе с учителем заполняют следующую таблицу:

Оцените статью
Adblock detector