Пример 2.5

Игра «Угадай-ка—4». Некто задумал целое число в интервале от 0 до 3. Наш опыт состоит в угадывании этого числа. На наши вопросы Некто может отвечать лишь «Да» или «Нет». Какое количество информации должны получить, чтобы узнать задуманное число, т.е. полностью снять начальную неопределенность? Как правильно построить процесс угадывания?

Исходами в данном случае являются: А₁ - «задуман 0», А₂ - «задумана 1», А₃ - «задумана 2», A₄ - «задумана 3». Конечно, предполагается, что вероятности быть задуманными у всех чисел одинаковы. Поскольку n = 4, следовательно, p(A_i) = 1/4, log₂ р(А_i) = -2 и / = 2 бит. Таким образом, для полного снятия неопределенности опыта (угадывания задуманного числа) нам необходимо 2 бит информации.

Теперь выясним, какие вопросы необходимо задать, чтобы процесс угадывания был оптимальным, т.е. содержал минимальное их число. Здесь удобно воспользоваться так называемым выборочным каскадом:

Таким образом, для решения задачи оказалось достаточно 2-х вопросов независимо от того, какое число было задумано. Совпадение между количеством информации и числом вопросов с бинарными ответами неслучайно.

Пример 2.7

Контрольные вопросы и задания

Организация структур данных в ОЗУ

Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды

Кодирование чисел в компьютере и действия над ними

Вернуться в оглавление: Теоретические основы информатики