«Энтропия и информация. Решение логических задач» «Кто владеет информацией, тот владеет миром!» Э.Талейран. - презентация

1 «Энтропия и информация. Решение логических задач» «Кто владеет информацией, тот владеет миром!» Э.Талейран

2 1. Случайные события. Мера их неопределенности. Формула Хартли. 2. Энтропия по Шеннону. Свойства энтропии. 3. Условная энтропия. Решение задач на условную энтропию. 4. Количество информации. Решение задач. 5. Решение логических задач на взвешивание через энтропию и количество информации. 6. Решение логических задач о лжецах через энтропию и количество информации. 7. Защита творческих проектов. Итого: 14 часов Итого: 14 часов УЧЕБНО ТЕМАТИЧЕСКИЙ ПЛАН

3 ЦЕЛИ КУРСА «ЭНТРОПИЯ И ИНФОРМАЦИЯ. «ЭНТРОПИЯ И ИНФОРМАЦИЯ. РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ» Развитие логического мышления и формирование базы математических знаний; Развитие логического мышления и формирование базы математических знаний; Практическое применение изучаемого (изученного) программного материала средней школы; Практическое применение изучаемого (изученного) программного материала средней школы; Построение простейших вероятностных моделей реальных процессов и явлений, учитывающих влияние случая; Построение простейших вероятностных моделей реальных процессов и явлений, учитывающих влияние случая; Создание определенного алгоритма для оценки предсказуемости случая; Создание определенного алгоритма для оценки предсказуемости случая; Решение логических задач с применением понятия энтропии; Решение логических задач с применением понятия энтропии;

4 Задачи курса: Расширить представления учащихся о дискретной математике, ее возможностях при вполне жизненных ситуациях; Расширить представления учащихся о дискретной математике, ее возможностях при вполне жизненных ситуациях; Ввести новые математические понятия энтропии и количества информации; Ввести новые математические понятия энтропии и количества информации; Установить зависимость степени неопределенности от числа равновероятных исходов; Установить зависимость степени неопределенности от числа равновероятных исходов; Показать способы использования ориентированного графа и кодового дерева для построения рассуждений и выводов; Показать способы использования ориентированного графа и кодового дерева для построения рассуждений и выводов; Интегрировать алгебраический и графический методы для решения задач о лжецах, на взвешивание и др.; Интегрировать алгебраический и графический методы для решения задач о лжецах, на взвешивание и др.; Предложить комплекс логических задач, решаемых методом подсчета Предложить комплекс логических задач, решаемых методом подсчета

5 В результате освоения данного курса ученик должен научиться: Различать количественные характеристики случайного события: вероятность и степень неопределенности (энтропию); Различать количественные характеристики случайного события: вероятность и степень неопределенности (энтропию); Уметь находить степень неопределенности через известную (найденную) вероятность случайного события; Уметь находить степень неопределенности через известную (найденную) вероятность случайного события; Сравнивать два события по их неопределенности; Сравнивать два события по их неопределенности; Находить количество информации об опыте для оптимизации его результатов; Находить количество информации об опыте для оптимизации его результатов; Применять полученные умения и навыки для решения логических задач алгебраическим и графическим методами. Применять полученные умения и навыки для решения логических задач алгебраическим и графическим методами.

6 Занятие 1. Случайные события. Мера их неопределенности. Формула Хартли. Цель занятия: Вспомнить понятие случайных событий; Вспомнить понятие случайных событий; Ввести понятие энтропии, ее свойства; Ввести понятие энтропии, ее свойства; Ввести формулу Хартли, рассмотреть условия применения ее при решении задач на угадывание; Ввести формулу Хартли, рассмотреть условия применения ее при решении задач на угадывание;

7 Занятие 1. Случайные события. Мера их неопределенности. Формула Хартли. Задачи занятия: Научиться среди предложенных событий выбирать неопределенные; Научиться среди предложенных событий выбирать неопределенные; Установить соответствие между вероятностью события и его неопределенностью; Установить соответствие между вероятностью события и его неопределенностью; Научиться подсчитывать энтропию события по формуле Хартли; Научиться подсчитывать энтропию события по формуле Хартли; Отработать метод половинного деления для решения задач на угадывание; Отработать метод половинного деления для решения задач на угадывание; Разобрать алгоритм решения задач на угадывание с применением понятия энтропии Разобрать алгоритм решения задач на угадывание с применением понятия энтропии

8 Степень неопределенности – есть еще одна характеристика случайного события, которую назвали энтропией. (Н(α)). За единицу энтропии принимается неопределенность, содержащаяся в опыте, имеющем два равновероятностных исхода. Единица измерения, учитывая двоичную систему исчисления, - бит.

9 Формула Хартли Пусть опыт α имеет k равновозможных исходов, тогда Пусть опыт α имеет k равновозможных исходов, тогда Этой формулой удобно пользоваться, когда исходы равновероятны. Этой формулой удобно пользоваться, когда исходы равновероятны.

10 Чем больше равновероятных исходов, тем больше степень неопределенности Чем больше равновероятных исходов, тем больше степень неопределенности Чем меньше вероятность, тем больше степень неопределенности Чем меньше вероятность, тем больше степень неопределенности Что имеет большую степень неопределенности угадывание месяца или дня недели рождения случайно встреченного человека? Что имеет большую степень неопределенности угадывание месяца или дня недели рождения случайно встреченного человека? Какую степень неопределенности имеет угадывание месяца рождения случайно встреченного человека? Какую степень неопределенности имеет угадывание месяца рождения случайно встреченного человека? Н(α) = log k = log12 = 2 + log 3. Н(α) = log k = log12 = 2 + log 3.

11 ПРИЛОЖЕНИЕ 2.

12 Занятие 2. Энтропия по Шеннону. Свойства энтропии. Цели занятия: Продолжить усвоение понятия энтропия и ее свойств через введение формулы К. Шенона Продолжить усвоение понятия энтропия и ее свойств через введение формулы К. Шенона Задачи занятия: Создать проблемную ситуацию невозможности решить задачу с помощью формулы Хартли; Создать проблемную ситуацию невозможности решить задачу с помощью формулы Хартли; Ввести формулу Клода Шеннона; Ввести формулу Клода Шеннона; Рассмотреть анализ условий задач табличным и графическим методами; Рассмотреть анализ условий задач табличным и графическим методами; Ввести алгоритм решения задач на сравнение неопределенностей событий; Ввести алгоритм решения задач на сравнение неопределенностей событий; Свойства энтропии; Свойства энтропии; Провести тренинг сравнения степеней неопределенности событий. Провести тренинг сравнения степеней неопределенности событий.

13 Где вероятности равновозможных исходов. Он же предложил назвать эту величину энтропией Клод Шеннон

14 Имеются 2 урны. Первая содержит 20 шаров – 10 белых, 5 черных и 5 красных; Вторая содержит 16 шаров: 4 белых, 4 черных и 8 красных во второй. Из каждой урны вытаскивают по одному шару. Исход какого из этих двух опытов следует считать более неопределенным? (Приложение 3.) Первый опыт связан с первой корзиной: Первый опыт связан с первой корзиной: Н (α)= -1\2 log 1\2 - 1\4 log 1\4 - 1\4 log 1\4 = 1\2 +1\2 +1\2 = 3\2 бита Второй опыт связан со второй корзиной: Второй опыт связан со второй корзиной: Н (β)= -1\2 log 1\2 - 1\4 log 1\4 - 1\4 log 1\4 = 1\2 +1\2 +1\2 = 3\2 бита

15 Какую степень неопределенности содержит опыт угадывания цвета двух шаров, извлеченных из урны, в которой находятся 2 белых и 3 черных шара? Р=2\5 Р=3\5 Р=2\5 Р=3\5 Р=1\4 Р=3\4 Р=2\4 Р=2\4 Р=1\4 Р=3\4 Р=2\4 Р=2\4 Р=2\5 * 1\4 Р=3\10 Р=3\10 Р=3\10 Р=2\5 * 1\4 Р=3\10 Р=3\10 Р=3\10=1\10

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

17 Граф и формула нахождения условной энтропии выглядит следующим образом Н (β/Аi) = [Р(Вj /Аi) log (Р(Вj /Аi)) -1 ] … A1A1 AnAn P(A 1 ) P(A 2 ) P(A n ) α A 1 P(A 2 ) P(A 1 ) P(A n ) A2A2 An α

18 Какую энтропию содержит опыт угадывания простой цифры при извлечении из цифровой азбуки при условии, что одна карточка утеряна? Опыт α = {утеряна одна карточка} = {А1, А2 } А1 = {утеряна карточка с простой цифрой}, n(А1) = 4, Р(А1)= 4/10 =2/5, А2 = {утеряна карточка с непростой цифрой}, n(А2) = 6, Р(А2)= 6 /10 =3/5 β = {угадывание карточки с простой цифрой}

19 β Ответ: 1 бит. (Приложение 4)

20 Занятие 4. Количество информации. Решение задач Цель занятия: Введение понятия количества информации для решения задач Задачи занятия: Ввести новые понятия и формулы: количество информации, ориентированный граф, свойства количества информации; Ввести новые понятия и формулы: количество информации, ориентированный граф, свойства количества информации; Разобрать типовые задачи на количество информации; Разобрать типовые задачи на количество информации; Провести интерпретацию информации через энтропию; Провести интерпретацию информации через энтропию; Доказать ряд свойств количества информации; Доказать ряд свойств количества информации;

21 КОЛИЧЕСТВО ИНФОРМАЦИИ Количество информации I(α,β) показывает, насколько осуществление опыта α уменьшает неопределенность β т.е. как много нового узнаем мы об исходе опыта β, произведя измерение (наблюдение) α; Информацию можно измерить числом, которое называется количеством информации об опыте β, содержащемся в опыте α I(α,β)=H(β) – H(β/α)

22 Свойства количества информации 0 I(β/α) Н(β) 0 I(β/α) Н(β) I(α,β) = Н(α) + Н(β) - Н(α*β), I(α,β) = Н(α) + Н(β) - Н(α*β), I(α,β) = I(β,α) I(α,β) = I(β,α) I(α,β,γ) I(α,β), где α,β,γ- три произвольных опыта I(α,β,γ) I(α,β), где α,β,γ- три произвольных опыта (Приложение 5)

23 Решение логических задач на взвешивание через энтропию и количество информации.

24 ЗАДАЧИ НА ВЗВЕШИВАНИЕ Задача: Имеется 12 монет одного достоинства, одна из которых фальшивая, отличающаяся от других по весу (причем неизвестно, легче она или тяжелее настоящих). Каково наименьшее число взвешиваний на чашечных весах без гирь, которое позволяет обнаружить фальшивую монету?

25 Решение: т.е. определение фальшивой монеты связано с получением информации, измеряющейся числом log24 или k*log3log24 Отсюда и т.к. k – целое число, то k3

26 M 1 M 2 M 3 M 4 M 5 M 6 M 7 M 8 M 9 M 10 M 11 M 12 = M 3 M 4 M 6 M 1 M 2 M 5 М1М1 М2М2 М7М7 М5М5 М8М8 М3М3 М4М4 М 11 М 10 М6М6 М 12 М9М9 М 10 М 11 М9М9 М 12 Аналогично 1-му = M1 M2M1 M2 M7 M8M7 M8 M3 M4M3 M4 = = M 1 M 2 M 3 M 9 M 10 M 11 = M 9 M 10 = M 1 M 12 M 9 M 10 =

27 ТВОРЧЕСКИЕ ПРОЕКТЫ: Web-сайт: «Теория информации» Презентация: «информация и логические задачи»