 |
Тема: «Количественные характеристики информации. Перевод чисел из одной системы счисления в другую»
|
|
|
|
Цель работы: Определение количества информации при равновероятных событиях. Определение количества информации при различных вероятностях событий.
В Перевод чисел из одной системы счисления в другую.
Определение количества информации при равновероятных событиях. Определение количества информации при различных вероятностях событий
Количественные характеристики информации
N
· 2 I
,
где N – количество возможных событий;
12. – количество информации.
где
N
I = -å p i ×log2 p i,
i =1
p i –вероятностьi-го события.
I
В log 2
N
.
Энтропия системы H(α), имеющая N возможных состояний, согласно формуле Шеннона, равна
| N | i | ||
| H (a)= - | å i | ||
| P log P | |||
| i =1 | |||
где Pi –вероятность того,что система находится вi-м состоянии.
Пример. Имеются два ящика,в каждом из которых по12шаров.Впервом – 3 белых, 3 черных и 6 красных; во втором – каждого цвета по 4. Опыты состоят в вытаскивании по одному шару из каждого ящика. Что можно сказать относительно неопределенностей исходов этих опытов?
Решение. Находим энтропии обоих опытов:
H a
H b
- -
- -
3
12
4
12
log
log
2
2
3
12
4
12
-
-
3
12
4
12
log
log
2
2
3
12
4
12
-
-
6
12
4
12
log
log
2
2
6
12
4
12
- 1,50
- 1,58
бит,
бит.
|
|
|
54
H b
- H a
, т.е. неопределенность результата в опыте b выше и,
следовательно, предсказать его можно с меньшей долей уверенности, чем результат a.
Пример. В ящике имеются2белых шара и4черных.Из ящикаизвлекают последовательно два шара без возврата. Найти энтропию, связанную с первым и вторым извлечениями, а также энтропию обоих извлечений.
Решение. Будем считать опытом А извлечение первого шара.Онимеет два исхода: A 1 – вынут белый шар; его вероятность p(A 1) = 2/6 = 1/3;исход A 2 –вынут черный шар;его вероятность p(A 2)=1 – p(A 1) = 2/3. Эти данные позволяют с помощью сразу найти H(А):
H(А)=– p(A 1)log 2 p(A 1)– p(A 2)log 2 p(A 2)=–1/3 log 2 1/3–2/3log 2 2/3=0,918 бит.
Опыт В –извлечение второго шара также имеет два исхода: B 1 –вынут белый шар; B 2 – вынут черный шар, однако их вероятности будут зависеть от того, каким был исход опыта В. В частности:
при А1:
при А2:
| p | A 1 | (B) = 1/ 5 | ||
| 1 | ||||
| p | A 2 | (B) = 2 / 5 | ||
| 1 | ||||
| p | A 1 | (B | ) = | |
| 2 | ||||
| p | A 2 | (B | ) = | |
| 2 |
- /
3 /
5
5
;
.
Следовательно, энтропия, связанная со вторым опытом, является условной и равна:
| H | A 1 | (b) = -1/ 5 | ||
| H | A 2 | (b) = -2 / 5 | ||
log2 1/ 5 - 4 / 5 log2 4 / 5 = 0,722 бит,
log2 2 / 5 - 3/ 5 log2 3/ 5 = 0,971 бит,
H a (b)= p (A 1)× H A 1(b)+ p (A 2)× H A 2(b)= 1 3×0,722+3 2 ×0,971=0,888бит.
H = 0,918 + 0,888 = 1,806бит.
Пример. Имеется три тела с одинаковыми внешними размерами,но сразными массами x 1, x 2 и x 3. Необходимо определить энтропию, связанную
и нахождением наиболее тяжелого из них, если сравнивать веса тел можно только попарно.
Решение. Последовательность действий достаточно очевидна:сравниваем вес двух любых тел, определяем из них более тяжелое, затем с ним сравниваем вес третьего тела и выбираем наибольший из них. Поскольку внешне тела неразличимы, выбор номеров тел при взвешивании будет случаен, однако общий результат от этого выбора не зависит. Пусть опыт А состоит в сравнении веса двух тел, например, 1-го
|
|
|
55
В 2-го. Этот опыт, очевидно, может иметь два исхода: A 1 – x 1 > x 2; его вероятность p(A 1) = 1/2; исход A 2 – x 1 < x 2; также его вероятность p(A 2)=1/2.
| H(А) = –1/2 log 2 1/2 – 1/2 log 2 1/2 = 1 бит. | |
| Опыт В – сравнение весов тела, выбранного в опыте | , и3-го– |
имеет четыре исхода: B 1 – x 1 > x 3, B 2 – x 1 < x 3, B 3 – x 2 > x 3, B 4 – x 2 < x 3; вероятности исходов зависят от реализовавшегося исхода А– для удобства
представим их в виде таблицы
Таблица 1.1
| B 1 | B 2 | B 3 | B 4 | |
| A 1 | 1/2 | 1/2 | 0 | 0 |
| A 2 | 0 | 0 | 1/2 | 1/2 |
| H A 1(b)= -1/ 2 | log2 | 1/ 2 -1/ 2 | log2 | 1/ 2 =1 | бит, | |||||||||||
| H A 2(b)= -1/ 2 | log2 | 1/ 2 -1/ 2 | log2 | 1/ 2 =1 | бит, | |||||||||||
| H | (b) = p (A) × H | (b) + p (A) × H | (b) = | 1 | ×1+ | 1 | ×1 | = 1 | ||||||||
| a | A 1 | A 2 | ||||||||||||||
| 1 | 2 | 2 | 2 | |||||||||||||
Следовательно, энтропия сложного опыта, т.е.
испытаний:
H (a ^ b)= H (a)+ H (b)=2бит.
бит.
всей процедуры
Пример. Какое количество информации требуется,чтобы узнатьисход броска монеты?
Решение. В данном случае n=2 и события равновероятны,т.е.
p 1 =p 2 =0,5.
I = – 0,5 log 2 0,5 – 0,5 log 2 0,5 = 1 бит.
Игра «Угадай-ка–4». Некто задумал целое число в интервале от 0 до
- Наш опыт состоит в угадывании этого числа. На наши вопросы Некто может отвечать лишь «Да» или «Нет». Какое количество информации мы должны получить, чтобы узнать задуманное число, т.е. полностью снять начальную неопределенность? Как правильно построить процесс угадывания?
Исходами в данном случае являются: A 1 – «задуман 0», A 2 – «задумана 1», A 3 – «задумана 2», A 4 – «задумана 3». Конечно,
предполагается, что вероятности быть задуманными у всех чисел одинаковы. Поскольку n = 4, следовательно, p(A i)=1/4, log 2 p(A i)= –2 и I =
56
2 бит. Таким образом,для полного снятия неопределенности опыта(угадывания задуманного числа) нам необходимо 2 бит информации.
Теперь выясним, какие вопросы необходимо задать, чтобы процесс угадывания был оптимальным, т.е. содержал минимальное их число. Здесь удобно воспользоваться так называемым выборочным каскадом:
|
|
|
Рисунок 1.1
Таким образом, для решения задачи оказалось достаточно 2-х вопросов независимо от того, какое число было задумано. Совпадение между количеством информации и числом вопросов с бинарными ответами неслучайно.
Пример. Случайным образом вынимается карта из колоды в32карты. Какое количество информации требуется, чтобы угадать, что это за карта? Как построить угадывание?
Решение. Для данной ситуации n = 2 5,значит, k = 5 и,следовательно, I = 5 бит. Последовательность вопросов придумайте самостоятельно.
Пример. В некоторой местности имеются двеблизкорасположенные деревни: A или B. Известно, что жители A всегда говорят правду, а жители B – всегда лгут. Известно также, что жители обеих деревень любят ходить друг к другу в гости, поэтому в каждой из деревень можно встретить жителя соседней деревни. Путешественник, сбившись ночью с пути оказался в одной из двух деревень и, заговорив с первым встречным, захотел выяснить, в какой деревне он находится и откуда его собеседник. Какое минимальное количество вопросов с бинарными ответами требуется задать путешественнику?
Решение. Количество возможных комбинаций,очевидно,равно4(путешественник в A, собеседник из A; путешественник в A, собеседник из B; и т.д.), т.е. n = 2 2 и, следовательно значит, k = 2. Последовательность вопросов придумайте самостоятельно.
57
Таблица 1.2
| Буква | пробел | о | е, ѐ | а | и | т | н | с |
| Относи- | ||||||||
| тельная | 0,175 | 0,090 | 0,072 | 0,062 | 0,062 | 0,053 | 0,053 | 0,045 |
| частота | ||||||||
| Буква | р | в | л | к | м | д | п | у |
| Относи- | ||||||||
| тельная | 0,040 | 0,038 | 0,035 | 0,028 | 0,026 | 0,025 | 0,023 | 0,021 |
| частота | ||||||||
| Буква | я | ы | з | ь, ъ | б | г | ч | й |
| Относи- | ||||||||
| тельная | 0,018 | 0,016 | 0,016 | 0,014 | 0,014 | 0,013 | 0,012 | 0,010 |
| частота | ||||||||
| Буква | х | ж | ю | ш | ц | щ | э | ф |
| Относи- | ||||||||
| тельная | 0,009 | 0,007 | 0,006 | 0,006 | 0,004 | 0,003 | 0,003 | 0,002 |
| частота |
|
|
|
|
|
|
