Потенциал Образовательный журнал
для старшеклассников и учителей

<< К разделам
Информатика
Алгоритмы
Теория информации
Теория программирования
Все статьи
Журнал
Подписка
Интернет-Журнал «Потенциал» External link mark
Авторам
Печатные номера
Полезные сайты
ЗФТШ External link mark
МЦНМО External link mark
Журнал "Квант" External link mark
"Открытый Колледж" External link mark
Союз образовательных сайтов External link mark
Интернет-портал "Абитуриент" External link mark
Другие ссылки...

WOlist.ru - каталог качественных сайтов Рунета Союз образовательных сайтов Rambler's Top100 Портал ВСЕОБУЧ. Все образование Москвы и регионов РФ.

Главная Подписка Архив Авторы Фотоальбом Подготовка в вуз Магазин

Информация, энтропия и обобщённые вруны

Ворожцов Артём Викторович Ворожцов Артём Викторович
Закончил Московский физико-технический институт (МФТИ), преподаватель кафедры информатики МФТИ, тренер команд МФТИ по программированию, ответственный редактор раздела "Информатика".


Мало в нашем мире осталось того, что нельзя оцифровать и зазиповать.
Книги, шедевры живописи, музыка, видео, 3D-объекты, красивые девушки ... Всю реальность целиком моделируют, цифруют, кодируют, получая на выходе виртуальность. Трудно поверить, что все это лишь биты, биты, биты ... неисчислимый поток единичек и нулей. Мы начинаем раздел ''Теория информации и кодирования'' c обсуждения вопроса ''Что такое информация и как её измерять''.

Что такое ИНФОРМАЦИЯ?

Оцифровану Зазиповану Мою песню тебе шлю по проводу Скорость низкая Дорога дальняя Серверами чужими, заморскими
Сергей Фролов

Гриша спрашивает у Пети: "Какой у нас третий урок?" – "Математика" – отвечает Петя. Он передал Грише нужную информацию. А сколько именно информации заключалось в ответе Пети? На этот вопрос может ответить теория информации. Другая важная задача, которую решает теория информации и которая имеет непосредственное отношение к современным проблемам теле- и радиосвязи, такая: "Два человека соединены проводом (радиосвязью). Сколько информации они смогут друг другу передавать в единицу времени, если известны характеристики помех, возникающих в этом проводе (в эфире)?"

Как и в каких единицах измерять информацию станет ясно из следующей игры.

Игра "Угадай число"

Игра "Угадай число": Ведущий загадывает натуральное число от 1 до 100. Остальные играющие задают ему вопросы, на которые можно ответить либо "да", либо "нет". Нужно угадать число, задав как можно меньше вопросов. Например, отгадывающие могут задавать такие вопросы: "Верно ли, что это число 27?", "Загаданное число меньше 50?", "Загаданное число чётное?".

Задача: Сколько вопросов требуется для угадывания одного из первых n натуральных чисел?

Нетрудно догадаться, что для n=2 необходим ровно один вопрос. Для n=3 или n=4 требуется два вопроса (в худшем случае).

Решим эту задачу для случая n=16.

Первый вопрос: "Верно ли, что загаданное число лежит справа от вертикальной палочки?":

1 2 3 4 5 6 7 8 | 9 10 11 12 13 14 15 16

После ответа на этот вопрос, мы будем знать, в какой половине находится загаданное число. Пусть слева. Тогда второй вопрос: "Верно ли, что загаданное число лежит справа от вертикальной палочки между 4 и 5?" Если ли же загаданное число справа от 8, то второй вопрос будет таким: "Верно ли, что загаданное число лежит справа от вертикальной палочки между 12 и 13?"

1 2 3 4 | 5 6 7 8 | 9 10 11 12 | 13 14 15 16

После второго вопроса мы будем знать, в какой из четырех частей лежит загаданное число. Эту часть мы тоже разделим на две половинки, и после третьего вопроса узнаем, в какой из них лежит загаданное число. А после четвёртого вопроса мы будем знать само число. Итак, мы показали, что четырех вопросов достаточно, чтоб угадать загаданное число из 16 возможных. За пять вопросов мы сможем наверняка узнать правильный ответ из 32 возможных:

Определение: Вопрос называется элементарным, если он подразумевает два возможных ответа, например "Да" или "Нет".

Количество информации I определяется минимальным количеством элементарных вопросов, которые нужно задать, чтобы наверняка выведать эту информацию. Количество информации измеряется в битах.

Чтобы выведать один бит информации, нужно правильно задать элементарный вопрос и получить на него ответ. Если информация представляет собой один из n возможных равноправных вариантов, то её величина равна логарифму n по основанию 2: I=log2 n.

В частности, 5=log2 32. Логарифм может принимать любые значения, в том числе и нецелые. Мы не можем задать полтора вопроса или π вопросов, но тем не менее дробное количество информации имеет смысл. Задав вопрос, допускающий три возможных ответа, мы получим log2 3 ≈ 1.5848... бит информации.

Клод Шеннон, создатель теории информации, определил в 1945 году как следует интерпретировать дробное (любое неотрицательное вещественное) количество информации.

Клод Элвуд Шеннон (Claude Shannon), 1916-2001 — дальний родственник Томаса Эдисона, был сотрудником Bell Laboratories с 1941 дo 1972 г. В его работе "Математическая теория коммуникаций" (http://cm.bell-labs.com/cm/ms/what/shannonday/), опубликованной в 1948 г., впервые определялась мера информационного содержания любого сообщения и понятие кванта информации — бита. Эти идеи легли в основу теории современной цифровой связи. Другая работа Шеннона "Communication Theory of Secrecy Systems", опубликованная в 1949 г., способствовала превращению криптографии в научную дисциплину.

Задача 1: Грише сказали, что следующий урок — математика. До этого он знал, что следующий урок — либо математика, либо физика, либо рисование, либо география. Сколько бит информации сообщили Грише?

Решение: Количество возможных вариантов следующего урока равно 4. Ответ: I=log2 4=2.

Задача 2: У Васи есть одна доминошка. Он признался, что у него дубль. Сколько информации он нам сообщил?

Решение: После признания Гриши осталось 7 вариантов. Количество информации, которую он по прежнему от нас скрывает равно log2(7). А до признания он скравал log2 28. Поэтому Гриша сообщил нам log2(28) - log2(7)=2 бит.

Итого: количество информации, необходимое для описания объекта, равно логарифму по основанию два от количества возможных объектов:

Информативность объекта = log2 Количество возможных объектов

То есть

I(a)=log2 N (1)

Количество информации о каком-то объекте, которую мы получили в сообщении, равно логарифму от отношения количества возможных вариантов до сообщения на количество возможных после.

Если обозначить сообщение буквой w, то

Например, если Гриша нам признался, что оба числа на его доминошке нечётные, то он нам сообщил log2(28/6)≈ 2.22 бит информации.

Значительная часть простых задач теории информации сводится к комбинаторным задачам, то есть к вычислению числа объектов с некоторой данной конфигурацией. Другая часть задач связана с вычислением функции ЭНТРОПИИ.

ЭНТРОПИЯ — мера незнания

Задача 3: Перед нами 5 чёрных ящиков. В каждом из них находится либо чёрный, либо белый шарик. Мера неизвестности (неизвестной информации) равна 5 бит. Нам говорят, что 3 из них белые. Сколько информации нам сообщили? Сколько нам осталось узнать?

Решение: Сначала было 25 вариантов и мера неизвестности равнялась log2 (25)=5 . Когда нам сказали, что 3 шарика белые, число возможных вариантов стало равно количеству возможных распределений 3 белых и 2 чёрных шариков по 5 ящикам. Их 10 штук. Если ввести обозначения: 1 — белый, а 0 — чёрный, то получим:

(11100),(11010),(11001),(10110),(10101),(10011), (01110),(01101),(01011),(00111).

Это число распределений равно C3, 2=C35=C25 и называется числом сочетаний 3 элементов из 5, или 2 элементов из 5, или биномиальным коэффициентом (2,3). Это число C3, 2=10 получается так: первый нолик можно поместить на любое из 5 мест, второй — на любое из оставшихся 4. Всего получается 20 вариантов. Но среди них каждый вариант повторён дважды — сначала нолики выбраны в одном порядке, потом — в другом. А нам неважно, в каком порядке были выбраны нолики. Поэтому реальных вариантов в два раза меньше — 10 штук.

Ответ: Было неизвестно 5 бит, потом стало неизвестно log2(C3, 2)=log2(10)≈ 3.32 бит, значит нам сообщили 5-log2(10) ≈ 1.68 бит.

Давайте обобщим эту задачу.

Задача 4: Перед нами сколько-то чёрных ящиков. В каждом из них находится либо чёрный, либо белый шарик. Нам говорят, что 60% из них — белые. Сколько информации нам осталось узнать? То есть, чему равна мера нашего незнания? Решите эту задачу, когда число ящиков равно
  • а) 10;
  • б) 100;
  • в) 1000;
  • г) n.

Решение: По аналогии получаем

  • a) log2(C6, 4);
  • б) log2(C60, 40);
  • в) log2(C600, 400);
  • г) log2(C0.6n, 0.4n).

Надо получше изучить числа Cm1, m2 — это количество способов разместить m1 единичек и m2 ноликов по m1+ m2 местам. Какова общая формула для Cm1, m2? Для вычисления удобно пользоваться такой формулой:

Cm1, m2= Cm1-1, m2+ Cm1, m2-1.

Докажем эту формулу. Давайте поместим на первое место единичку и разместим в оставшихся позициях m1-1 единичку и m2 нолик. Это можно сделать Cm1-1, m2 способами. Затем поставим на первое место нолик и разместим в оставшихся позициях m1 единичку и m2-1 нолик. Это можно сделать Cm1, m2-1 способами. В итоге мы переберём все возможные размещения m1 единичек и m2 ноликов.

Эта формула позволяет нам просто вычислять Cm1, m2.

               1
             1   1
           1   2  1
         1   3   3  1
       1   4   6   4  1
     1   5  10  10  5   1

Это треугольник Паскаля. Каждое число в этом треугольнике есть сумма двух над ним стоящих. Чтобы узнать, чему равно C2, 3, нам нужно взглянуть на 2+3=5-ую строчку. На первом месте стоит 1 — это C5, 0, число способов размещения пяти единичек по пяти местам. Далее 5=C4, 1, число способов разместить 4 единички и один ноль по пяти местам. Далее следует нужное нам C3, 2=10, число способов разместить 3 единички и 2 нулика по 5 местам.

Задача 5: Чему равно C2, 4? Чему равно C3, 4?

Задача 6: Чему равно наше незнание, если мы знаем, что 3 бита из 8 бит байта — единички, а остальные — нули? Байт — это восемь мест, в которых стоят нули и единицы.

Если мы в треугольнике Паскаля дойдём до 11 строчки, то получим

{1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1}.

Эти числа нарисованы в виде гистограммы на рисунке 1, а логарифмы этих чисел, делённые на 11, на рисунке 2.

Рис.1 Числа из 11-ой строчки треугольника Паскаля Рис.2 Логарифмы чисел из 11-ой строчки треугольника Паскаля, деленные на 11

Утверждение 1: Если нам сообщают, что 600 из неизвестных нам 1000 бит — единички, то мера нашего незнания, равная изначально 1000, уменьшается до log2(C600, 400) или, в общем случае:

Если нам сообщают, что p ∙ n (где 0<p<1 ) из неизвестных нам n бит есть единички, то мера нашего незнания, равная изначально n, уменьшается до log(Cp∙ n, (1-p)∙ n). Мера нашего незнания умножается на число, меньшее 1, которое равно

Давайте рассмотрим это соотношение подробнее. Обозначим его Hn(p). Это число можно интерпретировать как незнание, приходящееся на каждый из n бит. Или так: cтолько информации нам осталось узнать про каждый бит, после того, как нам сказали, что p∙100% бит равны 1.

Рис.3 Графики функций H(p) и H_{n}(p) для различных n

Определение: Энтропией случайной величины с вероятностями {p,1-p} называется функция H(p)=- (p∙ log2 p +(1-p)∙ log2 (1-p) )

Утверждение: Чем больше n, тем более схожи функция Hn(p) и функция энтропии H(p). Выбирая большие n, мы можем сделать их сколь угодно мало отличающимися в каждой точке.

Строгое доказательство этой теоремы использует явную формулу и формулу Стирлинга, суть которой заключена в том, что мы можем n! заменять на .

Если в ящиках чёрные, белые и синие шарики, то мера незнания про каждый ящик равна log2 3. Но когда нам сообщают информацию, что 30% шариков черные, 25% — белые, остальные 45% — синие, то мера нашего незнания о том, что хранится в каждом ящике, уменьшается с log2 3 ≈ 1.585 до величины

H({0.3, 0.25, 0.45})=- (0.3log2 0.3 + 0.25log2 0.25 + 0.45log2 0.45) ≈ 1.539

То есть случайная величина с вероятностями p1, p2, p3, p1+p2+p3=1 имеет энтропию

Общая формула энтропии случайной величины такая:

Cлучайная величина — это конвеер, по которому поступают черные ящики, мы их открываем и узнаем, что там. Известно процентное содержание различных элементов в этих ящиках.

Энтропия позволяет записать более общую формулу для информативности сообщения (сравните с формулой (1)):

Информативность сообщения =Hдо сообщения-Hпосле соообщения Или, если обозначить сообщение как w, то

I(w)=Hдо получения w-Hпосле получения w (2)

Вруны и обобщённые вруны

А что, если человек, который нам отвечает на вопросы, — заядлый врунишка? Если он — абсолютный врун, то ничего страшного нет. Например, если он на вопрос "Это ты съел варенье?" отвечает "Нет!" — значит съел. Абсолютный врун — это тот, кто всегда врет. Абсолютные вруны являются прекрасными проводниками информации, надо только все их ответы интерпретировать наоборот!

Конечно, абсолютных врунов не бывает. Чаще встречаются обычные, нормальные вруны, которые врут, скажем, в 40% случаев. С ними гораздо сложнее. Но и у них можно выведать всю правду. Только придется задать больше вопросов. То, сколько бит выведанной информации в среднем приходится на один вопрос, называется пропускной способностью "обобщённого вруна".

Её можно вычислить так: зададим обобщённому 40%-вруну n элементарных вопросов. Мы знаем, что на 40% вопросов он соврал. Информация о том, на какие именно из заданных вопросов он соврал, представляет собой n∙ H(0.4) бит. Это значит, что если бы он перестал врать, то мы за n∙ H(0.4) элементарных вопросов узнали бы, где он соврал. Но врун врёт. И пока мы будем у него выяснять, в каких именно вопросах он нам соврал, он нам будет продолжать врать и всё путать. Лучше рассуждать по-другому. Предположим, что мы смогли составить n вопросов так, что в полученных n ответах содержится нужная нам перевранная информация размером m бит и еще информация о том, в каких именно из n ответов он врал. То есть m + n ∙ H(0.4)=n или m=n - n∙ H(0.4)= n∙ (1-H(0.4)), и пропускная способность вруна —

Это значит, что если умело задавать вруну вопросы, то за n вопросов можно выведать у него n∙ (1-H(p)) бит.

Тот же результат можно получить из таких рассуждений: на выходе у вруна ответы "Да" и "Нет". Мера неопределенности равна один бит. Но в этой мере неопределённости часть неопределенности возникает из-за случайности "вранья". Каждый раз врун кидает монетку, чтоб решить — врать или не врать. Мера этой неопределённости равна H(p). Значит, "полезная", не связанная с враньём неопределённость в одном ответе равна 1-H(p).

На рисунке 4 показана геометрическая интерпретация пропускной способности. Длина отрезка AB — и есть пропускная способность. Рядом показан случай несимметичного вруна, который в случае правильного ответа "Да" врёт с одной вероятностью α, а в случае ответа "Нет" — c другой вероятностью β.

Если врун врёт с вероятностью 1/2, то нам никогда не удастся у него ничего выведать.


Рис.4 слева - симметричный врун, справа - несимметричный врун

"Данетки"

Что такое ДаНетка? Это загадка, которая "разыгрывается" между ведущим и отгадывающими. Отгадывающие задают вопросы, а загадывающий отвечает на них "да", "нет" или "не имеет значения". В результате отгадывающие должны прояснить ситуацию полностью, задав как можно меньше вопросов. У всех ДаНеток, в которых вопрос не оговорен отдельно, вопросом является "Почему?", "Как и/или что случилось?" или "Кто это?".

  1. Бежит человек с ружьём, а за ним толпа. Человек оглядывается, кричит: "Не видать вам моего золота!", стреляет пять раз и бежит дальше.
  2. От тщеславия она лишилась пищи.
  3. Мальчик рассказывает: "Вчера был такой ужасный дождь, а мой папа не взял ни зонта, ни шляпы. Когда он появился в дверях, вода лилась с него ручьями, но ни один волос на его голове не промок".
  4. Чем сильнее его бьют по нужному месту, тем лучше он выполняет свою функцию.
  5. Человек в течение получаса не обращал внимания на часы. В результате он не получил крупную денежную сумму.
  6. Два джигита соревнуются: чей конь последним придет к финишу. Но дело не идет, оба стоят на месте. Они обращаются за советом к мудрецу... После этого оба поскакали во весь опор.
  7. На автостраде произошло довольно странное ДТП. Оба водителя доставлены в больницу в тяжелом состоянии. Интересно, что их машины не получили при этом никаких повреждений.
  8. Из трамвая выскакивает и быстро убегает человек, а за ним другой, который кричит: "Все забирай, но отдай билет!"
  9. Грабитель влез в окно, огляделся, лег на кровать и спокойно заснул.
  10. Человек вызывает лифт, заходит внутрь и умирает.
  11. Наперерез бегущему молодому мужчине бежит другой и сильно пинает его в ногу. Это видят полицейские, но даже не пытаются арестовать хулигана.
  12. Восемь мужчин поочередно падают вниз с десятиметровой высоты.
  13. Он бежал медленнее всех, и его убили.
  14. Мужчина, завернувшись в простыню, озадаченно разглядывает еще теплый труп.
  15. Человек пошел на пляж, а на следующий день его уволили за профнепригодность.
  16. Натуралист увидел птичье гнездо с яйцами, наклонился над ним и умер унизительной смертью.
  17. Вооруженный мужчина покупает у проходящих мимо людей маленькие кусочки пластмассы.
  18. Человек шел по дороге, посмотрел на часы и умер в недоумении.
  19. Пятьдесят один вегетарианец стал жертвой дорожно-транспортного происшествия.
  20. Человек движется со скоростью 350 километров в час без помощи каких-либо технических средств, и только потому, что его технические средства не сработали.

Отгадки

  1. Это биатлонист, он бежит первым и претендует на золотую медаль.
  2. Басня "Ворона и лисица".
  3. Папа был лысый.
  4. Гвоздь.
  5. Часы были шахматные. Человек — шахматист, играющий решающую партию крупного турнира. Не заметив, что противник уже сделал ход, он просрочил время и проиграл партию, заняв в турнире только второе место.
  6. Мудрец посоветовал обменяться конями.
  7. Был сильный туман, водители высунулись из окон, чтоб видеть осевую разметку, и столкнулись головами.
  8. Карманник украл у пассажира трамвая бумажник, где лежал лотерейный билет, выигравший автомобиль, но пассажир быстро заметил пропажу.
  9. Это была собственная квартира грабителя. Он потерял ключ и пришлось лезть через окно.
  10. Двери лифта открылись, но лифт-то не подошел.
  11. Матч чемпионата мира по футболу (полицейские сидят на трибуне).
  12. Соревнования по прыжкам в воду.
  13. Тараканьи бега с тотализатором. Таракана, прибежавшего последним, с досады раздавил человек, поставивший на него много денег.
  14. Мужчина был в летаргическом сне, но его посчитали мертвым, и медсестра уже везла его на вскрытие, когда он очнулся и сел на каталке. Медсестра умерла от ужаса.
  15. Человек работал диктором на радио, а на пляже, точнее в море, он чуть не попал в пасть акулы. От пережитого потрясения он стал заикаться.
  16. Это было гнездо страуса. А сзади к натуралисту подошел страус-хозяин гнезда и пнул его.
  17. Кассир в казино обменивает выигранные фишки посетителей на наличные деньги.
  18. Дорога была железная, через туннель, где нельзя было отойти, а поезд шел не по расписанию.
  19. Вегетарианец-водитель грузовика не справился с управлением на горной дороге, и машина упала в пропасть. В кузове грузовика стояло пятьдесят клеток с кроликами.
  20. Он спрыгнул с самолета с парашютом, а тот не раскрылся.

Задачи по теории информации

Задача 8: Коля съел на переменке шоколадку, яблоко и кекс. Сколько элементарных вопросов надо задать, чтоб узнать, в какой последовательности он их съел. Сколько информации от нас скрыто? А если Коля съел 6 различных объектов?

Задача 9: Натуральное число n. Известно, что оно чётное и 5 ≤ n ≤ 20. Сколько элементарных вопросов нам нужно задать, чтобы узнать это число?

Задача 10: В книге восемь рассказов, в каждой главе 32 страницы. Вася сказал, что он читает 5-ый рассказ. Сколько информации он нам сообщил? Сколько информации осталось у него выведать, чтобы узнать какую страницу он читает?

Задача 11: Мы сказали продавцу, что хотим купить коньки. Но коньки бывают обычные и роликовые, белого, чёрного, зелёного и фиолетового цвета. Кроме того есть размеры 38, 39, 42 и 44. Сколько информации вам нужно сообщить продавцу?

Задача 12: Нам сказали, что сумма чисел у доминошки X равна 3. Сколько информации нам сообщили?

Задача 13: Коля выучил стихотворение, в котором 32 слова. Оцените информацию, которую он запомнил. (Считайте, что всего в русском языке 10000 слов). По каким причинам сделанная вами оценка несколько завышена?

Задача 14: "Граждане встречающие! Поезд 26 прибывает по 7-му пути в 19:35." Сколько информации содержится в этом сообщении? (Всего на вокзале 8 платформ, ежедневно прибывает и отправляется в путь 120 поездов)

Задача 15: Преступник имеет следующие приметы: молодой человек, яркий брюнет, с заметной родинкой на левой щеке. Сколько информации нам про него известно? Считайте, что ярких брюнетов — 20%, с родинкой на левой щеке — 5%. Здесь "молодой человек" означает: 17-22 лет с вероятностью 0.25, 23-28 лет с вероятностью 0.5, 29-34 лет с вероятностью 0.25. В то время как общее распределение по возрастам такое: до 17 лет – 0.375, 17-22 лет – 0.125, 23-28 лет – 0.125, 29-34 лет — 0.125, 35 лет и старше – 0.25:
возраст вероятность
выглядеть молодым человеком
доля людей
данного возраста
до 17 0 0.375
17-22 0.25 0.125
23-28 0.5 0.125
29-34 0.25 0.125
после 34 0 0.25

Подсказка: для вычисления информативности сообщения о молодости пользуйтесь формулой (2).

Задача 16: "У доминошки X числа разные". Сколько бит информации нам сообщили и сколько еще осталось узнать, чтоб однозначно определить доминошку? Придумайте элементарные вопросы, которые нужно для этого задать.

Задача 17: Известно, что класс 8А состоит из 7 отличников, 16 хорошистов, 8 троечников и 4 двоечников. Сколько информации содержится в сообщении:
  • а) "Коля хорошист"
  • б) "Коля не двоечник"
  • в) "Коля учится без троек"
  • г) "Коля не отличник"?
Считайте, что Коля — случайный ученик из 8А класса.

Задача 18: У Коли в прошлом учебном году было в 6 предметов и 4 четверти. Нам сказали, что у него нет двоек и троек. Сколько информации нам сообщили?

Задача 19: Решите предыдущую задачу при условии, что нам сказали, что у Коли ровно половина пятерок и половина четвёрок в каждой четверти.

Задача 20: У Оли есть карта. Мы знаем, что масть этой карты — крести. Сколько информации нам известно?

Задача 21: Изначально мы знаем, что 3 < π< 4. Сколько дополнительной информации о числе π содержится в записи π=3.14159265...?

© Журнал "Потенциал", 2005-2017. Все права защищены. Воспроизведение материалов сайта и журнала "Потенциал" в любом виде, полностью или частично, допускается только с письменного разрешения редакции.
Отзывы и пожелания шлите почтой.
Подготовка к ЕГЭ
ЕГЭ по математике
login