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

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

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

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

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

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

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

I= log₂16,

I=log₂2⁴,

I=4 бит.

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

2^I=N,

в нашем случае

2^I=16, 2^I=2⁴,

I=4 бит.

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

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

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

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

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

2^I=N,

2⁴= N,

2⁴=16,

N =16 (под.)

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

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

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

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

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

2^I=N,

2³= N,

2³=8,

N=8 (б.)

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

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

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

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

N1 = 16,

2^I=N,

2^I=16,

2⁴=16,

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

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

N2 = 8,

2^I=N,

2^I=8,

2³=8,

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

3) I = I1 + I2,

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

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

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

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

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

2 вопрос: Число < 150? Нет (Вариантов 50)

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

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

2^I=200,

т.к. 2⁷=128, а 2⁸=256, то 7 < I < 8.

Т.к. количество вопросов нецелым числом быть не может, то необходимо задать не более 8 вопросов.

Если ответ получается не целый (как в данном случае I=7,644), выберите следующее целое число (I=8бит).

Следовательно основную формулу для расчета количества информации ( 2^I=N) правильнее было бы записать так: наименьшее целое I такое, что 2^I>=N.

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

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

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

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

7 вопрос: Число > 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- общее количество рыб в реке.

P1 = 1500/2000 = 0,75.

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

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

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

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

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

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

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

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

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

I_б = log₂(1/P_б ),​ где I_б-количество информации в сообщении "На стоянку заехал автомобиль белого цвета" 

8=log₂(1/P_б), где Р_б- вероятность въезда белого автомобиля.

1/Р_б=2⁸, тогда Р_б=1/2⁸=1/256.

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

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

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

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

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

Р_​б+кр​=1/64.

Так как Р_​б+кр​=Р_​б +Р_​кр​=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=1/256,

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

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

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

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

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

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

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

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

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

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

1/16=Nc/96 ,

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

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

1/Рз=2^​5, тогда Рз=1/2⁵=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-log₂24: заменив число 7 на log₂128 и применив правило вычисления разности логарифмов получим: 7-log_​2​24=log₂128-log₂24=log₂(128/24).

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

I₁₊₃=log₂(128/24) .

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

7-log₂120=log₂128-log₂120=log₂(128/120).

Информационный объем сообщения «Квартира не однокомнатная» (т.е. двухкомнатная или трехкомнатная) равен: I₂₊₃=log₂(128/120) .

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

log₂(128/24)=log₂(1/P₁₊₃), тогда 128/24=1/P₁₊₃ , следовательно P₁₊₃=24/128.

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

log₂(128/120)=log₂(1/P₂₊₃), тогда 128/120=1/P₂₊₃ следовательно P₂₊₃=120/128.

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

Р₁₊₂₊₃= Р₁+ Р₂₊₃=1, тогда P₁=1-P₂₊₃=1-120/128=8/128.

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

Р₁₊₃= Р₁+ Р₃=1,

P₃=P₁₊₃-P₁=24/128-8/128=16/128 .

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

I₃=log₂(1/P₃)= log₂(128/16)=log₂8=3 бит

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

Задачи для самостоятельного решения

• 2015 Апрель