В лучшем случае вся книга будет состоять только из «А»: «АААА…» (возможно, выражая боль автора). Чтобы общаться при помощи одной буквы «А», достаточно сказать «А» один раз (ответить на один вопрос), и ответ будет получен. Здесь мы снова используем абстракцию – сначала анализируем, что будет, если посчитать только одну букву, и игнорируем всю книгу – по крайней мере для начала. Умножьте наш ответ для одной буквы на количество букв в книге и получите упомянутый лучший случай.
В худшем случае (для латинского алфавита), при котором кто-нибудь, например, все время жужжит («ZZZZ…»), потребуется 26 вопросов для каждой буквы. Итак, мы определили границы, в которых будет происходить передача любой информации. У нас никогда не получится лучше, чем при варианте с одной буквой, и хуже, чем со всеми 26.
Оценка будет точнее, если учесть среднее количество вопросов на каждую букву, то есть средний случай. Сделать это не так трудно. В длинном сообщении на каждую «А» где-нибудь еще придется «Z», на каждую «B» найдется «Y» и так далее. Это значит, что в среднем во всей книге на каждую продиктованную букву надо будет задать 13 вопросов. Умножьте число букв в книге на 13, и вы получите примерную оценку работы при ее написании. Умножьте это на среднее время, которое уходит у помощницы, чтобы произнести букву, и вы получите время, необходимое, чтобы написать книгу.
Отметим, что мы снова оцениваем наш алгоритм – но на сей раз нас интересует не то, действует ли он вообще, а то, насколько быстро он действует. У алгоритма оценивают много разных аспектов, но надежность и эффективность – два важнейших для оценки.
Изменение, внесенное Боби, — сначала спрашивать о распространенных буквах — улучшает ситуацию. Вероятно, получится уложиться в 10‒11 произносимых букв. А с учетом частотности, мы рассчитаем это точнее. Частотность можно уточнить или определить самостоятельно. Возьмите отрывок из любимой книги и посчитайте, сколько раз появляется каждая буква. Потом расположите буквы по порядку, начиная с самой распространенной, и посчитайте вероятность их появления. Средний случай — это число букв, которое необходимо произнести для угадывания одной буквы, вероятность появления которой равна 50%.
Итак, частотный анализ привел к улучшениям, но не слишком значительным, и в худшем случае для выяснения одной буквы все равно надо задать 26 вопросов. Но каждый специалист по информатике знает, что можно существенно улучшить этот процесс. Любая буква выясняется всего за пять вопросов! Гарантированно! И это не средний случай, а худший! Знаете, какие пять вопросов надо задать?
20 вопросов?
Смогли вы ответить на этот вопрос или нет, я гарантирую, что вы знаете, о каких вопросах идет речь. Чтобы вспомнить о них, нужно рассмотреть другую задачу.
Давайте сыграем в игру «20 вопросов». Это детская игра, в которой водящий задумывает известного человека, а вы пытаетесь догадаться, кто это, задавая вопросы. Изюминка в том, что отвечать следует только «да» или «нет». Сыграйте в эту игру с другом и обратите внимание, какие вопросы вы задаете. Представим, как может пойти игра.
«Вы женщина?» — «Нет».
«Вы живы?» — «Нет».
«Вы были кинозвездой?» — «Нет».
«Вы жили в Британии?» — «Да».
«Вы были писателем?» — «Да».
«Вы жили в XX веке?» — «Нет».
«Вы жили в XIX веке?» — «Нет».
«Вы Шекспир?» — «Да».
Вероятно, играя, вы задавали похожие вопросы. Очень маловероятно, что вы сразу начали спрашивать: «Вы Аристотель? Вы Джеймс Бонд? Вы Мария Кюри?» Так вы никогда бы не нашли ответ за 20 вопросов. До подобных формулировок дело обычно доходит в конце, когда вы практически уверены, что знаете, кто это (как мы только что показали). Скорее, вы начали с вопроса вроде «Вы женщина?».
Почему это хороший вопрос для начала? Да потому, что он отметает половину возможных вариантов при любом ответе. Если вы спросите «Вы королева Англии?», то в случае успеха отбросите миллионы других вариантов, а в случае (более вероятного) неуспеха — только одного человека. Чтобы сразу угадать, вам должно повезти не меньше, чем выигравшему в лотерею. Значит, секрет игры «20 вопросов» — задавать вопросы так, чтобы каждый раз отбрасывать половину людей, каким бы ни был ответ.
Насколько это эффективно?
Задавать вопросы, которые оставляют половину возможных ответов, — лучше, чем называть конкретное имя, но насколько? Давайте предположим, что я изначально задумал кого-то одного из миллиона. Если после каждого вопроса отметать половину людей, сколько вопросов понадобится? После первого останется 500 000 человек, после второго — 250 000... После десяти вопросов от исходного миллиона останется примерно 1000 человек (рис. 1). Продолжаем... После следующего вопроса осталось 500, потом 250, 125... и на двадцатом вопросе остается один возможный человек. Если вам удастся каждый раз точно задавать вопрос, после которого останется половина ответов, то вы гарантированно выиграете. И всегда это будет 20 вопросов.