Теория. К комбинаторике близки задачи на меры информации. Понятие «информация» - одно из самых фундаментальных, наряду с пространством, временем, материей и энергией и поэтому не имеет четкого определения. Но информацию нужно как-то измерять. Придуманы несколько мер информации. Для успешной сдачи ЕГЭ могут понадобиться две из них – комбинаторная и вероятностная.
Единицей информации является бит – ячейка, которая равновероятно может принимать значения 0 и 1.
Задача 2.4.1. Какой объем информации в битах мы получим, кидая монетку два раза, если оба раза выпадет «орёл»?
Задача 2.4.2. На правильный тетраэдр (пирамиду из четырех правильных треугольников) нанесли числа 0, 1, 2, 3. Какой объем информации нужен, чтобы сохранить результат одного кидания тетраэдра (грани, на которую он приземлится)?
Теория. Рассмотренная мера информации называется комбинаторной. И действительно, мы решили приведенные задачи с помощью комбинаторики. Воспользуемся формулой для определения количества битовых ячеек:
I = log2m
где m – мощность алфавита (количество разных типов событий).
Но этим меры информации не ограничиваются.
Предположим, что мы знаем, что ячейка может принимать только значение 0. Какой объем информации вы получите, когда заглянете в содержимое этой ячейки? Правильный ответ – ноль информации. Потому что вы и так до вопроса знали содержимое ячейки. Добавим теперь вероятность. Рассмотрим задачу с погодой. Предположим, наступил сезон дождей, и вы знаете, что вероятность дождливого дня равна 90%, а солнечного – 10%. Если мы используем комбинаторную меру информации, то у нас будет два состояния: солнечно/дождливо. Но согласитесь, что проснувшись, выглянув в окно и увидев дождь, вы меньше удивитесь, чем если увидите солнце. То есть, увидев дождь, вы, так как его и ожидали, получите меньше информации, чем увидев солнце. Таким образом, нужна новая мера информации – вероятностная. Эту меру придумал Шеннон, поэтому её еще называют мерой Шеннона:
Легко заметить, что при равновероятных событиях эта формула превращается в комбинаторную меру. Например, в задаче про тетраэдр четыре равновероятных состояния. Следовательно, вероятность выпадения нуля равна:
В общем случае, когда m равновероятных событий
То есть та же самая формула, что и для комбинаторной меры.
Задача 2.4.3. Двое играют в «крестики-нолики» на поле 4 на 4 клетки. Какое количество информации (в битах) получил второй игрок, узнав ход первого игрока?
Задача 2.4.4. В корзине лежат черные и белые шары. Среди них 18 черных шаров. Сообщение о том, что достали белый шар, несет 2 бита информации. Сколько всего шаров в корзине?
Задача 2.4.5. За четверть Василий Пупкин получил 20 оценок. Сообщение о том, что он вчера получил четверку, несет 2 бита информации. Сколько четверок получил Василий за четверть?
Задача 2.4.6. В закрытом ящике находятся 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике?
Примечание 1. Может возникнуть вопрос, можно ли в логарифме поменять основание 2 на какое-нибудь другое число? Можно, и формулы от этого не изменятся, но тогда это будет уже не бит, а другая мера информации. Например, в квантовых компьютерах используется мера информации кубит. Для ЕГЭ может потребоваться другое основание, например, 3, если элементарная ячейка для хранения информации может принимать три состояния: 0,1,2. Но такие задачи до сих пор в ЕГЭ не встречались.
Примечание 2. Если возможные состояния имеют разные вероятности и мы посчитаем соответствующий им объем информации, мы получим разные величины для различных состояний. Для кодирования это будет иметь практический смысл. Мы сможем построить неравномерный код. Например, в русском языке буква «О» встречается намного чаще, чем буква «Щ». Следовательно, мера информации для «О» меньше, чем для «Щ», и букву «О» можно закодировать меньшим количеством символов, чем «Щ». Задачи на неравномерный код приведены в следующем параграфе.