Конспект лекций по программированию для начинающих. Гладков В.П. - 9 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Составители: 

Рубрика: 

11
искать среди существительных, область поиска уменьшается за счет
отбрасывания слов, относящихся к другим частям речи. Таким образом,
получена информация, уменьшившая степень нашего незнания.
Если общее количество слов α, то неопределенность можно оценить
log
2
(1/α) = -log
2
α =I
1
. После отбрасывания слов остальных частей речи
останутся только существительные. Их количество равно β (β<<α). В этом
случае неопределенность можно оценить log
2
(1/β) = -log
2
β = I
2
. Количество
информации, полученное с этим сообщением, будет равно уменьшению
степени неопределенности I = I
1
- I
2
= -log
2
α+log
2
β.
Пример 2.7. Пусть имеется колода из 32 игральных карт (в колоде утеряны
4 шестерки). Задумывается одна из карт. Необходимо, задавая вопросы, на
которые будут даны ответы «Да», «Нет», угадать задуманную карту.
Решение. Первый вопрос: «Задумана карта черной масти?» На вопрос
получен ответ «Нет». Он принес количество информации К
1
= log
2
32 - log
2
16 =
5 - 4 = 1 бит. Неопределенность ситуации уменьшилась вдвое.
Второй вопрос: «Задумана карта бубновой масти?» Ответ «Да» приносит
еще один бит информации. К
2
= log
2
16 - log
2
8 = 4 - 3 = 1.
Третий вопрос: «Задумана карта-картинка?» Ответ «Нет» уменьшает
неопределенность ситуации еще вдвое. К
3
= log
2
8 - log
2
4 = 3 - 2 = 1. После
третьего вопроса осталось 4 варианта: карта может быть 7,8,9 или 10.
Четвертый вопрос: «Задумана семерка или девятка бубновые?» Ответ «Да»
приносит еще один бит информации. К
4
= log
2
4 - log
2
2 = 2 - 1 = 1.
Пятый вопрос проясняет ситуацию: «Задумана семерка бубновая?» Ответ
«Нет» дает еще один бит информации. После этого ответа установлено, что
задумана девятка бубновой масти.
В 1948 году американский инженер и математик К.Шеннон обобщил
формулу Р.Хартли на случай получения информации об одном из N событий,
вероятности появления которых различны.
Рассмотрим
некоторый умозрительный эксперимент. Пусть имеется
генератор, который на своем экране может демонстрировать любую из букв
некоторого алфавита, состоящего из К букв. Генерирование осуществляется в
соответствии с заданным законом распределения:
A
i
A
1
A
2
.. A
k
P
i
P
1
P
2
.. P
k
Каждая из букв появляется в соответствии с вероятностью появления. За
экраном ведется наблюдение: пусть на экране уже появлялось N букв (N -
достаточно большое число).
Если мы интересуемся буквой A
i
, то она на экране появится приблизительно
N·P
i
раз. Каждое появление буквы A
i
дает -log
2
P
i
бит информации. Всего за все
ее появления будет получено -N·log
2
P
i
бит информации.
После демонстрации всех N букв, суммируеем полученную информацию:
()
INPlogP
i2i
i=1
k
=− ⋅ ⋅
∑
                                            11

искать среди существительных, область поиска уменьшается за счет
отбрасывания слов, относящихся к другим частям речи. Таким образом,
получена информация, уменьшившая степень нашего незнания.
    Если общее количество слов α, то неопределенность можно оценить
log2(1/α) = -log2α =I1. После отбрасывания слов остальных частей речи
останутся только существительные. Их количество равно β (β<<α). В этом
случае неопределенность можно оценить log2(1/β) = -log2β = I2. Количество
информации, полученное с этим сообщением, будет равно уменьшению
степени неопределенности I = I1 - I2 = -log2α+log2β.
    Пример 2.7. Пусть имеется колода из 32 игральных карт (в колоде утеряны
4 шестерки). Задумывается одна из карт. Необходимо, задавая вопросы, на
которые будут даны ответы «Да», «Нет», угадать задуманную карту.
    Решение. Первый вопрос: «Задумана карта черной масти?» На вопрос
получен ответ «Нет». Он принес количество информации К1 = log232 - log216 =
5 - 4 = 1 бит. Неопределенность ситуации уменьшилась вдвое.
    Второй вопрос: «Задумана карта бубновой масти?» Ответ «Да» приносит
еще один бит информации. К2 = log216 - log28 = 4 - 3 = 1.
    Третий вопрос: «Задумана карта-картинка?» Ответ «Нет» уменьшает
неопределенность ситуации еще вдвое. К3 = log28 - log24 = 3 - 2 = 1. После
третьего вопроса осталось 4 варианта: карта может быть 7,8,9 или 10.
    Четвертый вопрос: «Задумана семерка или девятка бубновые?» Ответ «Да»
приносит еще один бит информации. К4 = log24 - log22 = 2 - 1 = 1.
    Пятый вопрос проясняет ситуацию: «Задумана семерка бубновая?» Ответ
«Нет» дает еще один бит информации. После этого ответа установлено, что
задумана девятка бубновой масти.
    В 1948 году американский инженер и математик К.Шеннон обобщил
формулу Р.Хартли на случай получения информации об одном из N событий,
вероятности появления которых различны.
    Рассмотрим некоторый умозрительный эксперимент. Пусть имеется
генератор, который на своем экране может демонстрировать любую из букв
некоторого алфавита, состоящего из К букв. Генерирование осуществляется в
соответствии с заданным законом распределения:
                          Ai    A1 A2 ..        Ak
                          Pi    P1 P2      ..   Pk
    Каждая из букв появляется в соответствии с вероятностью появления. За
экраном ведется наблюдение: пусть на экране уже появлялось N букв (N -
достаточно большое число).
    Если мы интересуемся буквой Ai, то она на экране появится приблизительно
N·Pi раз. Каждое появление буквы Ai дает -log2Pi бит информации. Всего за все
ее появления будет получено -N·log2Pi бит информации.
     После демонстрации всех N букв, суммируеем полученную информацию:
                                      k
                           I = − N ⋅ ∑ Pi ⋅ log 2 ( Pi )
                                      i=1

Страницы