Раздел «Образование».FIVTLecturesTerm4Lecture07:
<< Список лекций ФИВТ, 4-й семестр, 2009 г.

Следующая лекция
Предыдущая лекция

Лекция 7. Теория информации. Понятия меры неопределённости, количества информации и энтропии

Понятие неопределённости и количества информации в сообщении о черном ящике

Будет использовать везде логарифмы по основанию 2.

Опр 1. Неопределённость, заключающаяся в чёрном ящике X равно log(N), N — число возможных вариантов того, что находится внутри.

Будем считать, что логарифм берется по основанию 2.

Теорема 1. Неопределённость, заключающаяся в двух черных ящиках X и Y равна сумме неопределённостей:

Опр 2. Количество информации, которое было передано в сообщении M о черном ящике X равно разности неопределённостей до и после получения сообщения:

Замечание. Неоределённость — это количество скрываемой информации. Это количество примерно равно (с точностью до округления до целого числа) минимальному количеству элементарных вопросов (deсision questions), которые нужно задать, чтобы выведать эту информацию. Вопрос будем называть элементарным, если он подразумевает два возможных ответа "Да" или "Нет".

Задача 1. У Коли есть доминошка. Сколько информации содержится в сообщении

Задача 2. У Коли есть карта (одна из 52 карт). Сколько информации содержится в сообщении

Задача 3. Коле едет в Питер. В поезде 12 вагонов. В каждом вагоне 36 мест. Сколько информации содержится в его сообщении "Номер моего места меньше чем номер моего вагона"?

Понятие энтропии

Задача 4. Есть N = 1000 черных ящиков, в каждом из которых находится 0 или 1. Сколько информации содержится в сообщении

Ответ на (а) дается формулой:

где C(n, m) = (n + m)! / (n!*m!) количество сочетаний n элементов из n+m.

Теорема 2. lim ( log( 2^N / C(p*N, (1-p)*N) ) ) / N ) = - ( p*log(p) + (1-p)*log(1-p) )

Опр 3. H(p) = - ( p*log(p) + (1-p)*log(1-p) ) — функция энтропии одной переменной.
H.png

Опр 4. H(p1, p2, ...) = - ( p1 * log(p1) + p2 * log(p2) + ... ) — функция энтропии нескольких переменных. Предполагается, что p1 + p2 + ... = 1.

Утверждение 1. Если мы знаем, что в потоке 0 и 1 доля 1 составляет p, то каждый новый полученный бит уменьшает меру неопределенности о точном значении получаемого бинарного слова примерно на H(p). Если длина получаемого слова стремится к бесконечности, то информация в кажом получаемм бите стремится к H(p).

Опр 5. Пусть v - дискретная случайная величина, принимающая N возможных значений. Величину H(p1, p2, ...) назовём энтропией случайной величины. Также с этой величиной будем связывать количество информации, получаемое нами при одном измерении этой случайной величины.

Опр 6. Величину 2^H(p1, p2, ...) назовём ээфекивным количеством значений случайной величины v.

Зависимые случайные величины

Задача 5. Четыре автора пишут статьи в три рубрики журнала. Число статей каждаго автора по каждой из тем приведено в таблице:
  спорт экономика и рынки политика
Автор 1 17 2 10
Автор 2 3 1 20
Автор 3 33 13
Автор 4 2 1 4

Найдите

Докажите, что

Следующая лекция
Предыдущая лекция