Информация и энтропия

Энтропия и информация. Решение логических задач»

https://refdb.ru/look/2327838-pall.html

http://cito-web.yspu.org/link1/metod/theory/node28.html

Уп № 1. Первый встречный человек мужского пола.

1. За понедельником будет вторник.

2. За контрольную работу можно получить «отлично».

3. К телефону из 5 членов семьи подойдет младший сын.

4. После 31 января наступит 1 февраля.

5. После лета буде зима.

6. Каждый из 15 учен, посещающ данные занятия, поступит на матем специальность.

7. В лотерее победит билет с номером 777777.

8. Подброшенная монетка упадет гербом вверх.

9. На подброшенном кубике выпадет шесть очков.

10. Из выбираемых наугад карточек с цифрами выберем карточку с цифрой 5.

Задания: среди 11 событий а)Указать достоверные (2,5) б)Указать невозможные (6)

В)Указать неопред (1, 3,4,6,7,8,9,10)Г)Среди неопред указать те, кот имеют 2 равновозм исх (1,9)

Д)Неопр события расст в порядке возраст числа равновер исходов (№ 1,9-2; № 3-4; №4-5; № 10-6; № 11-10; № 7-15; № 8-число проданных билетов)

Е)Назвать событие более неопредел. (№ 8) ж)Назвать событие менее неопредел. (№ 1,9)

З)Учит зад№ 6 и № 7, устань з-ть степени неопред от числа равновер исходов. (Чем больше равновер исходов, тем больше степень неопределенности)

И)Сделать тот же вывод, исп понятие вероятности. (Чем меньше вероятность, тем больше степень неопределённость).

 Понятие ЭНТРОПИИ

Величина, характеризующая количество неопределенность в теории информации обозначается H и называется информационная энтропия За единицу энтропии принимают неопределённость, содержащуюся в опыте, имеющ 2 равновероятных исхода. Единицы измерения в - бит.

В математической теории связи (т информации) исходят из того, что в некотором сообщении x_i количество информации I(x_i) зависит не от её конкр содержания, степени важности и т.д., а от того, как выбрано данное сообщ из общей совокупности возможных сообщений.

В реальных условиях выбор конкретного сообщения производится с некот априорн вероятностью P(x_i). Чем меньше эта вероятность, тем больше информации содерж в данном сообщении. Вероятностный подход и положен в основу опр меры колич информации.

Пусть опыт α меет k равновозможных исходов. От этого числа зависит и зн вероят одного из них Р(А)=1/k, и зн энтропии. . Если k=1, то f(k) = 0 (неопред нет)

f(k) – возраст, т.к. чем больше равновозможных исходов, тем больше степень неопределенности.

Рассм сложный опыт αβ, где опыт α имеет k равновозм исхода, а β – m равновозм исхода. Оч, что неопредел сложного опыта αβ б склад из неопр каждого опыта в отд. т.е. f(km) = f (k) + f(m)Сопост получ информ с имеющ знаниями функцион за-тей, получ, что f (k) – есть логарифмич зависимость: log₂k или logk выбор основания системы логарифмов здесь несуществен,

Энтропия по Хартли) дискретного источника с независимым выбором сообщений) При частичном снятии неопредел, полученное количество информации и оставшаяся неснятой неопределенности составят в сумме исходную неопределенность. H_t + I_t = H.

Ф-ла Хартли – частный сл формулы Шеннона для равновероятных альтернатив.

Из

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

:

Если кол рассм альтернатив в рез получ сообщ уменьш вдвое, т.е.  , то I=log₂(2)=1 бит. Др сл, получ 1 бита информ искл из рассм 0.5 равноз вариантов.

Зад1/1. Что имеет большую степень неопределенности угадывания месяца или дня недели рожд случайно встреченного человека.

Реш: Т к месяц рожд имеет 12 равновер исходов, а день недели имеет 7 равновер исхода, то степень неопред угадыв месяца рождения больше, чем угадыв дня недели.

Зад 2/1.а) Какую степень неопредел имеет угадыв месяца рожд случ встречен чел.

Реш:Т к месяц рожд имеет 12 равновер исходов, то фла Хартли: Н(α) = log k = log12 = 2 + log 3.

Б) Ск вопр след задать, чтобы быстрее отгад конкр месяц? Отвеч говорит «да» или «нет».

Т к неопредел данного опыта 2 + log 3, а число вопр – целое, то для полн снятия неопред треб число вопросов – ближ целое число, превыш (или совп, если Н(α) целое) с Н(α), т.е

. n ≥ Н(α) = log k. 32+log3  2+log 3≈ 3,24 Ответ: 4.

Предложить вариант системы вопросов. Например,

1)В 1й половине года? (Да) 2)в 1й половине выбранной половины? (Да)

3)Это средний из 3 месяц? (Нет) 4)Это 1й из 3 месяц? (Нет) Зн, третий месяц сезона.

Зад 3 Сколько вопросов н задать, чтобы отгадать  число не превыш

А)10 n=4 б) 100. n=7 в)1000 n=10

Энтропия по Шеннону. Свойства 

Клодом Шенноном, амер матем и инж, предл принять в кач меры неопредел опыта α с возм исходами А_1, А_2, … А_k вел 

Количество информации I и энтропия H характеризуют одну и ту же ситуацию, но с кач противоп сторон. I – это кол информации, кот треб для снятия неопределенн H. По опр Леона Бриллюэна информация есть отрицательная энтропия (негэнтропия). Когда неопред снята полн, кол получ информации I= изнач существ неопредел

При частичном снятии неопределенности получ кол информации и оставш неснятой неопределенность сост в сумме исх неопределенность. H_t + I_t = H.

Общая мера неопределенности опыта есть взвешенная сумма мер неопредел отд исходов: -p(А₁) log p(А₁) - p(А₂) log p(А₂) - p(А₃) log p(А₃) … -p(А_k) log p(А_k) = Н (α), что наз энтропией опыта α. чем событие б предсказуемо, тем оно менее информативно. Зн и его энтропия б ниже

Общий объем информации в книге вычислим как сумму произведений информационного веса каждого символа на число повторений этого символа в книге:

1)Баб испекл 8 пирож с капустой,16 пирож с повидл. Маша съела 1 пирож.(Отв.:0,815 бит)

Пусть К₁ – это кол пирожков с повидлом, К₁=24 К₂ – кол пир с капустой, К₂=8

N – общее кол пирожков, N = К₁ +К₂=24+8=32

Выч вер выбора пирожка с разной начинк и кол информ, кот при этом б получено.

Вер выб пирожка с повидл: р₁=24/32=3/4=0,75. Вер выб пирожка с капуст: р₂=8/32=1/4=0,25.

Вычислим кол инф, содерж в сообщ, что Маша выбр пирожок с повид:

I₁=log₂(1/p₁)= log₂(1/0,75)= log₂1,3=1,15470 бит.

Выч кол инф, в сообщ, если б выбран пирож с капуст: I₂=log₂(1/p₂)= log₂(1/0,25)= log₂4=2 бит

I = - (р₁∙log₂p₁ + р₂∙log₂p₂)= - (0,25∙ log₂0,25+0,75∙ log₂0,75)≈-(0,25∙(-2)+0,75∙(-0,42))=0,815 бит

2)В корзин 32 клубка красн и черн шерсти. Среди них 4 клубк красной . Ск инф несет сообщ, что выб клубок красн шерсти? Ск инф несет сообщ, что выб клубок шерсти любой окраски?

Дано: К_к=4;N=32 Найти: I_к, I

Найдем кол клубков черной шерсти: К_ч=N- К_к; К_ч=32-4=28

Найдем вер доста клубка каждого вида: p_к= К_к/N=4/32=1/8; p_ч= К_ч/N=28/32=7/8;

кол инф, кот несет сообщ, что выб клубок красн : I_к= log₂(1/(1/ p_к))= log₂(1/1/8)= log₂8=3 бит

кол инф, кот несет сообщ, что достали клубок шерсти любой окраски:

Ответ: I_к=3 бит; I=0,547 бит

2. В корзине 8 черных и 24 белых шара. Ск битов информ несет сообщ о том, что достали черный шар? (Вар отв: а) 2 бита b) 4 бита c) 8 битов d) 24 бита)

Событ шариков неравновер, поэтому счи по ф-ле Шеннона:Pчерн = 1/4, Pбел =3/4. Поэтому

I = - (1/4 x log 2 (1/4) + 3/4 x log 2 (3/4)) = - (1/4 x (-2) + 3/4 x (-0,415)) = - (-0,5 - 0,311) = 0,811

Округляя до целого, получаем 1 бит.

3. Какое кол инф б содерж зрит сообщ о цвете вынут шарика, если в непрозр мешке хранятся:

а) 25 бел, 25 красн, 25 син, 25 зелб) 30 бел, 30 красн, 30 синих и 10 зел?

5) В зооп всего 32 обезьяны, кот сидят в 2 вальерх A и B. Среди них есть 1 обезьяна-альбинос. Сообщ "обезьяна-альбинос нах в вольере A" заним 4 бита. Ск обезьян сидит в вольере B?

Раз сообщ о том, что альбинос томится в A, несет 4 бит- вер события 2**(-4) = 1/16 (инф в 4 бита соотв выбору одного из 16 вар) поэтому в вольере А живет 1/16 часть всех обезьян
б) всего обезьян – 32, поэтому в вольере А живет 32/16 = 2 обезьяны
в) поэтому в вольере Б живут все оставшиеся 32 – 2 = 30 обезьян

Зад1/2. Имеются 2 урны. 1я содер 20 шаров – 10 белых, 5 черных и 5 красных; 2я содер 16 шаров: 4 белых, 4 черных и 8 красных во 2й. Из каждой урны вытаск по 1 шару. Исход какого из этих двух опытов следует считать более неопределенным?

Неопр 1 опыта, или энтропия :Н (α)= -1\2 log 1\2 - 1\4 log 1\4 - 1\4 log 1\4 = 1\2 +1\2 +1\2 = 3\2 бита

Неопр 2 опыта, или энтропия :Н (β)= -1\2 log 1\2 - 1\4 log 1\4 - 1\4 log 1\4 = 1\2 +1\2 +1\2 = 3\2 бита

Ответ: опыты одинаково неопределенны.

2)Какую степень неопредел содержит опыт угад цвета 2 шаров, извл из урны, в кот нах 2 белых и 3 черных шара? Реш. Постр граф неопределенн данного опыта.

Зад3/2.Из многол наблюдений за погодой на опред терр изв, что 15 июня вер осадков= 0,4; а 15 нояб = 0,8. Какой из прогнозов явл более неопределенным?

Прогноз на15 июня является более неопределенным

Б)  изменяем усл зад:. Из многол наблюд за погодой на опред терр изв, что 15 июня вероятность осадков 0,4; а 15 нояб вер осадков 0,8, причем вер дождя 0,48,а вер снега 0,32. На какое число прогноз погоды явл более неопределенным?

Пр. Док, что у опытов с 2 исход наиб энтропию имеет тот , у кот исходы равновер.

Реш. Пост график функции  (осн у log 1) и рассм среднюю линию  трапеции , где 

, поск функция  на промеж выпукла вверх.

Тогда 

 Условная энтропия. (дискретный источник с зависимыми сообщениями)

Условной энтропией опыта β отн опыта α наз мат ожид усл энтропии опыта β отн всех исходов опыта α: Н (β/α) = ∑Р(А_i) Н (β/А_i), где Н (β/А_i) – усл энтропия опыта β отн исхода А_i

Н (β/А_i) = ∑ [Р(В_j/А_i) log (Р(В_j/А_i))^-1]

Граф нахождения условной энтропии 

Зад 1/3. Какую энтропию содержит опыт угадывания простой цифры при извлечении из цифр азбуки при условии, что 1 карточка утеряна?

Опыт α = {утеряна одна карточка} = {А₁, А₂ }

А₁ = {утеряна карточка с простой цифрой}, n(А₁) = 4, Р(А₁)= 4/10 =2/5,

А₂ = {утеряна карточка с непростой цифрой}, n(А₂) = 6, Р(А₂)= 6 /10 =3/5

β = {угадыв карточки с простой цифрой}

Н (β/А₁) опр с учетом того, что утеряна карточка с простой цифрой и их ост 3 среди 9 карточек: Н (β/А₁) = 3/9 log 9/3 + 6/9 log 9/6 = log3-2/3, анал счит

Н (β/А₂) = 4 /9 log 9/4 + 5/9 log 9/5 = 2log3-5/9 log5 -8/9;

строим граф двух зависимых опытов α и β

Н(β /α)=2/5(log3-2/3) +3/5(2log3-5/9 log5-8/9) = (8/5log3-1/3log5–4/5)=1,6 *1,6–0,33*2,33–0,8≈1(бит)

Пр 1. В ящике 2 белых шара и 4 черных. Из ящика извл последоват 2 шара без возврата. Найти энтропию, связанную с 1 и 2 извлеч, а также энтропию обоих извлечений.

Б счит опытом извл 1 шара. Он имеет 2 исхода: A₁ – вынут белый шар; его вер p(A₁) = 2/6 = 1/3; исход A₂ – вынут черный шар; его вер p(A₂)=1 – p(A₁) = 2/3. Эти данные позв сразу найти H():

H()= – p(A₁)log₂ p(A₁) – p(A₂)log₂ p(A₂) = –1/3 log₂1/3 – 2/3 log₂2/3 = 0,918 бит

    Опыт – извл 2 шара также имеет два исхода: B₁ – вынут белый шар; B₂ – вынут черный шар, однако их вер будут зависеть от того, каким был исход опыта . В частности:

    След, энтропия, связанная со 2 опытом, явл условной и, согл (1.8) и (1.9), равна:

    Наконец, из (1.10): H( ) = 0,918 + 0,888 = 1,806 бит.

Пр . Какую энтроп содерж опыт угад простой цифры при извл из цифр азбуки при усл, что одна карточка утеряна?

Реш 1. Пусть опыт {утеряна 1 карт} = где = ={утеряна карт с простой цифрой}, = {утеряна карт с непрост цифрой}. Опыт = {угад карточки с прост цифрой}, и в зад предл найти усл энтропию . Т к карточек с простыми цифрами 4

-а

поск после утери карточки с простой цифрой осталось 9 карточек, и из них 3 с простой цифрой.

След, = (бит).

Реш 2. Построим граф двух зависимых опытов и:

Рис. 73 Тогда

(бит).

Пр2. Найти энтропию угадыв простых цифр при извл 2 карточек из цифровой азбуки.

Реш 1. Построим граф неопределен данного сложного опыта.

(бит).

Реш 2. Восп свойством энтропии, по кот . Из предыд примера

, а Тогда (бит).

Пр118. Какую неопр содерж опыт угадыв четн суммы очков случ взятой кости домино, если известно, что одна кость утеряна?

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

Рис. 75

Пр119. Найти энтропию четности сумм очков на двух костях, извл из полного набора домино.

Реш. Пусть опыт = {извл 1 кости домино}, а = {извл 2 кости домино}. Тогда энтропию сложн опыта нах по п-лу слож энтропий. где усл энтропия вычисл в реш предыд примера.

Пр 120. Док, что если опыты и содержат по два исхода.

Реш. Пусть = {A,A}, a = {B,B}, тогда , , , } и