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

Вид материалаПояснительная записка

Содержание


Занятие № 3. Условная энтропия. Решение задач на условную энтропию
Задачи занятия
Решение задачи № 1 / 3
Задача № 2/3.
Задача № 3\3.
Домашнее задание
Подобный материал:
1   2   3   4   5

Занятие № 3. Условная энтропия. Решение задач на условную энтропию


Цель занятия: введение понятия условной энтропии для решения соответствующих задач.

Задачи занятия:
  • Ввести понятие условной энтропии;
  • Обозначить тип задач, решаемых с применением условной энтропии;
  • Ввести алгоритм решения задач на условную энтропию;
  • Разобрать набор задач;
  • Ввести свойства энтропии, привести доказательство;

План занятия:
    1. Проблемная ситуация через задачу 1 / 3
    2. Разбор Графа условной энтропии в общем виде;
    3. Применение общих подходов к конкретной ситуации;
    4. Решение задач 2 / 3 – 4 / 3
    5. Свойства энтропии. Доказательство свойства № 5.
    6. Домашнее задание.

Ход занятия:

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

Анализ условия показывает, что задача отличается от предыдущих, т.к. есть дополнительное условие. Такие задачи принято относить к условной энтропии.

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

Н (β/Аi) = ∑ [Р(Вj i) log (Р(Вj i))-1] Граф нахождения условной энтропии выглядит следующим образом:


Решение задачи № 1 / 3:


Н (β /α) = Р(А1) Н (β/А1)+ Р(А2) Н (β/А2)

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

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

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

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


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

Н (β/А2) = 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/3. Какую неопределенность содержит опыт угадывания четности суммы очков случайно взятой кости домино, если известно, что одна кость утеряна?

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






Ответ: 17/7log3 -20/63log5 – 11/63log11 – 32/21(бит)

Задача № 3\3. Найти энтропию угадывания простых цифр при извлечении двух карточек из цифровой азбуки.

Решение: Из десяти цифр четыре являются простыми: 2,3,5,7.

Вероятность угадать простую цифру равна 4/10=2/5; Вероятность угадать непростую цифру равна 6/10 = 3/5.

Карточки с какими цифрами вытащены (простыми или непростыми – неизвестно)

Если первой выбрана карточка с простой цифрой, то вероятность для второй карточки 3/9 или 6/9; если первой выбрана карточка с непростой цифрой, то вероятность для второй карточки 5/9 или 4/9. Построим граф двух зависимых опытов α и β, учитывая, что Р(Пр, Пр)=2/15; Р(Пр, Пр)=4/15; Р(Пр, Пр)=4/15; Р(Пр, Пр)=1/3


опыт β


опыт α






Ответ:

Задача № 4/3. Найти энтропию угадывания простых цифр при извлечении трех карточек из цифровой азбуки.

Решение: Из десяти цифр четыре являются простыми: 2,3,5,7.

Вероятность выбрать простую цифру равна 4/10=2/5;

Вероятность выбрать непростую цифру равна 6/10 = 3/5.

Карточки с какими цифрами вытащены вторыми простыми или непростыми – неизвестно.



Н (α βγ)= 1/30log30 + 3(1/10log10) + 4(1/6 log6) = (1/30 + 1/30log5 +1/30log3 + 3/10 + 3/10log5 +2/3 + 2/3 log3)= (1/3 log5 + 7/10 log3 +1)(бит).

Ответ: (1/3 log5 + 7/10 log3 +1)(бит)

После решения такого количества задач можно обозначить свойства энтропии:
  1. Н(α) ≥0 (очевидно)
  2. Н(α) = 0, если Р (Аi) = 1, а все Р (Аj) = 0 (очевидно)
  3. Н(α) – max, если все Р(Аi)=1/n, т.е. равновероятны
  4. Н(αβ) = Н(α) + Н(β), если α и β - независимы
  5. Н(αβ) = Н(α) + Н(β/α), в общем случае, если α, β содержат по два исхода
  6. 0 ≤Н(β/α) ≤ Н(β)
  7. Н(α1, …. αk) ≤ Н(α1) + …. Н( αk)

Доказательство: 5. Н(αβ) = Н(α) + Н(β/α), в общем случае, если α, β содержат по два исхода

Пусть α={A1 , A2 } β={В1 , В2 }, тогда αβ = { A1В1 , A2 В2, A1В2, A2 В1}

Н (α β)= -[Р(A1В1)log Р(A1В1)+Р(A1В2)log Р(A1В2)+Р(A2В1) log Р(A2В1) + Р(A2В2) log Р(A2В2)] = -Р(А1)Р(В11)[logР(A1)+logР(В1/A1)] - Р(А1)Р(В21)[logР(A1)+log Р(В2/A1)] - Р(А2)Р(В12)

[log Р(A2)+ log Р(В1/A2)] - Р(А2)Р(В22)[ log Р(A2)+ log Р(В2/A2)] = Н(α) + Р(А1)Н(β/А1) + Р(А2) Н(β/А2) = Н(α) + Н(β/α)

Домашнее задание: №1. Какую степень неопределенности содержит опыт извлечения двух костей домино относительно «дуплей»?

№ 2. Найти энтропию угадывания дней рождения двух случайно встреченных людей.

№3. Найти энтропию угадывания месяцев рождения двух случайно встреченных.