Когда я учился в институте, очень популярной была игра «Быки и коровы». Я был практически непобедимым игроком, а всё благодаря относительно несложному алгоритму, разработанному мною на основе теории информации. И вот недавно я обнаружил, что в любимую игру моей юности можно сразиться онлайн. И что вы думаете? Я сыграл трижды против самого сильного «соперника» (из тех, что предложил компьютер), и все три раза выиграл! 🙂
Я решил рассказать о разработанной мною оптимальной стратегии игры «Быки и коровы» на основе теории информации, но для начала – о книге, которая познакомила меня с основами теории информации. В печатном виде найти ее непросто (всё же год издания 1980-й), а вот в электронном – пожалуйста.
Альфред Реньи. Трилогия о математике. – М.: Мир, 1980. – 376 с. В сборник включены научно-популярные произведения известного венгерского математика и популяризатора науки: «Диалоги о математике», «Письма о вероятности», «Дневник. — Записки студента по теории информации», а также четыре статьи: о теории вероятностей, о ее преподавании, о числах Фибоначчи и о математической теории «деревьев».
Скачать краткий конспект в формате Word
Примечание. Файл Word содержит буквы греческого алфавита, благодаря чему восприятие материала облегчено 🙂
Книга интересна вся, но к разработке алгоритма игры «Быки и коровы» «причастна» лишь новелла «Дневник. — Записки студента по теории информации». Краткое её изложение я вам и представляю.
Возникновение математической теории информации стало возможным после того, как было осознано, что количество информации можно задать числом. Чтобы измерить количество любой информации, необходимо закодировать ее в виде последовательности нулей и единиц наиболее рациональным способом (то есть способом, позволяющим получить самую короткую последовательность). Длина (количество знаков) полученной последовательности нулей и единиц (кодового слова) может служить мерой количества информации. Ответ на вопрос, допускающий лишь два ответа — «да» и нет», а в остальном произвольный, служит единицей для измерения количества информации.
Каждая цифра числа, записанного в двоичной системе счисления, содержит одну единицу информации. Отсюда и название единицы информации — бит (от английского binary digit —двоичная цифра).
На лекции присутствовали 32 студента. Лектор спросил, сколько вопросов необходимо задать, чтобы установить, кого из нас он задумал. Я тотчас ответил, что для этого понадобится 5 вопросов. Тогда лектор попросил меня пояснить, какие вопросы я имею в виду. Я сказал, что, прежде всего, составил бы список присутствующих, расположив их фамилии в алфавитном порядке, и спросил бы (в этом и состоял бы мой первый вопрос), не внесен ли задуманный лектором студент в первую половину списка. Полученный ответ, каким бы он ни был — утвердительным или отрицательным, позволил бы сузить круг поисков, вдвое уменьшив число «подозреваемых» с 32 до 16. Действуя аналогично, я вторым вопросом сократил бы число студентов, среди которых может оказаться задуманный лектором слушатель, до 8, третьим вопросом — до 4, четвертым — до 2 и, задав пятый вопрос, установил бы, кто был задуман. Затем лектор поинтересовался, хватило бы мне пяти вопросов, если бы их надо было задавать все сразу, то есть если бы, ставя очередной вопрос, я не знал ответов на предыдущие вопросы. Мне казалось, что если все вопросы задавать сразу, то их понадобится больше пяти. Но я заблуждался. Лектор показал, как следует задать сразу пять вопросов, чтобы по ответам на них можно было установить, кто из студентов был задуман. Перенумеруем сидящих в аудитории последовательными целыми числами от 0 до 31 и запишем порядковый номер каждого студента в двоичной системе. Каждой из 32 фамилий мы тем самым поставим в соответствие пятиразрядное двоичное число (если двоичная запись порядкового номера окажется короче пяти знаков, припишем недостающие знаки (нули) слева; например, число 1 запишем в виде 00001. Пять вопросов, которые можно задать сразу, заключаются в следующем: верно ли, что в двоичной записи порядкового номера фамилии задуманного студента первая, вторая, третья, четвертая и пятая цифры равны единице?
Если в заданном множестве Н, содержащем N элементов, выделен какой-то элемент х, о котором заранее известно лишь, что он принадлежит множеству Н, то, чтобы найти х, необходимо получить количество информации, равное log2Nбитам. Эту формулу обычно называют формулой Хартли.
Закон аддитивности информации:
(1) log2N1N2 = log2N1 + log2N2
При неудачном выборе вопросов новой является лишь какая-то доля информации, а другая ее часть содержится в информации, полученной при ответе на предыдущие вопросы.
Формула Хартли исходит из молчаливого предположения о том, что все N элементов равновероятны. Однако в действительности такое предположение выполняется редко.
В общем же случае количество информации Н(x) можно найти по формуле Шеннона:
(2) Н(x) = p1log2(1/p1) + p2log2(1/p2) + … + pNlog2(1/pN),
где x – неизвестный элемент множества Н = {х1, х2, …, хN}, то есть x – случайная величина, принимающая значения х1, х2, …, хN, а рK – вероятность того, что x принимает значения хK(k = 1, 2, … N).
По возможности всегда следует стремиться к тому, чтобы утвердительные и отрицательные ответы на задаваемые нами вопросы были равновероятны.
Вероятность наступления независимых событий равна произведению их вероятностей.
Если при фиксированном значении N распределение вероятностей (p1, р2, …, рN) отлично от равномерного распределения, то сумма p1log2(1/p1) + p2log2(1/p2) + … + pNlog2(1/pN) всегда меньше чем log2N. Это означает следующее: если о случайной величине x известно лишь, что она принимает N различных значений, то при наблюдении одного значения x наибольшую информацию мы получаем в том случае, если все возможные значения x равновероятны.
Формулу (2) Винер вывел в 1948 г. независимо от Шеннона. Однако еще в XIX веке эта формула встречалась в работах Больцмана, поэтому ее часто называют формулой Больцмана — Шеннона. Больцман пришел к ней, занимаясь совсем другой задачей – изучением энтропии. Энтропия физической системы служит мерой неупорядоченности системы. Следовательно, можно считать, что энтропия системы является мерой неопределенности состояния молекул, образующих систему.
Неопределенность есть не что иное, как недостача информации, или отрицательная информация. Ту же мысль можно выразить иначе: информация есть не что иное, как убыль неопределенности. До наблюдения случайной величины x мы пребываем в полной неопределенности относительно того, какое из своих значений она может принять. После того как наблюдение произведено, неопределенность устраняется. Наблюдение случайной величины x содержит Н(x) битов информации; поскольку эта информация позволила избавиться от неопределенности, существовавшей до наблюдения, естественно принять число Н(x) за меру этой неопределенности. Таким образом, Н(x) можно рассматривать относительно значения, принимаемого величиной x, и как меру неопределенности, существовавшей до наблюдения случайной величины x. Эту меру неопределенности и принято называть энтропией. Итак, формула Шеннона допускает следующую интерпретацию. Если случайная величина x принимает значения х1, х2, …, хN с вероятностями р1, р2, …, рN, то энтропию величины x (то есть меры неопределенности существовавшей до наблюдения величины x), которую мы обозначим Н(x), можно вычислить по формуле:
Кодовый знак, который может принимать лишь два значения, содержит один бит информации только тогда, когда оба его значения равновероятны (то есть вероятность каждого из них равна ½), а во всех остальных случаях количество информации, содержащейся в таком знаке, меньше одного бита (рис. 1).
Рис. Зависимость количества информации (энтропии) от вероятности одного из двух событий
Количество информации о случайной величине x, полученной при наблюдении случайной величины h:
Относительно величины I(x, h) можно утверждать следующее:
а) Величина I(x, h) всегда неотрицательна и обращается в 0 лишь в том случае, если x и h независимы. Если x и h независимы, то наблюдение случайной величины h; не дает никакого выигрыша в информации относительно случайной величины x.
б) Справедливо неравенство I(x, h) меньше или равно Н(x), причем равенство в нем достигается в том и только в том случае, если x = f(h), то есть если значения случайной величины h однозначно определяют значения случайной величины x. Действительно, в этом случае наблюдение случайной величины h позволяет точно установить значение случайной величины x, то есть получить полную информацию относительно x. Иначе говоря, наблюдение случайной величины h позволяет полностью устранить всю неопределенность Н(x), относительно случайной величины x.
в) Величина I(x, h) симметрична: I(x, h) = I(h, x), то есть наблюдение случайной величины h позволяет получить точно такое же количество информации относительно случайной величины x, какое наблюдение случайной величины x дает относительно случайной величины h. Именно поэтому величину I(x, h) принято называть взаимной информацией случайных величин x и h. Равенство I(x, h) = I(h, x) также означает, что если мы рассматриваем две случайные величины, в определенной мере зависящие друг от друга, то средства теории информации не позволяют определить, какая из них играет роль причины и какая — следствия. Единственное, что в наших силах, — это установить, насколько тесна связь между двумя случайными величинами – насколько велика корреляция!