Читать книгу "Вычислительное мышление. Метод решения сложных задач - Питер Макоуэн"

20 вопросов?

Уложитесь в пять

Смогли вы ответить на этот вопрос или нет, я гарантирую, что вы знаете, о каких вопросах идет речь. Чтобы вспомнить о них, нужно рассмотреть другую задачу.

Давайте сыграем в игру «20 вопросов». Это детская игра, в которой водящий задумывает известного человека, а вы пытаетесь догадаться, кто это, задавая вопросы. Изюминка в том, что отвечать следует только «да» или «нет». Сыграйте в эту игру с другом и обратите внимание, какие вопросы вы задаете. Представим, как может пойти игра.

«Вы женщина?» — «Нет».

«Вы живы?» — «Нет».

«Вы были кинозвездой?» — «Нет».

«Вы жили в Британии?» — «Да».

«Вы были писателем?» — «Да».

«Вы жили в XX веке?» — «Нет».

«Вы жили в XIX веке?» — «Нет».

«Вы Шекспир?» — «Да».

Вероятно, играя, вы задавали похожие вопросы. Очень маловероятно, что вы сразу начали спрашивать: «Вы Аристотель? Вы Джеймс Бонд? Вы Мария Кюри?» Так вы никогда бы не нашли ответ за 20 вопросов. До подобных формулировок дело обычно доходит в конце, когда вы практически уверены, что знаете, кто это (как мы только что показали). Скорее, вы начали с вопроса вроде «Вы женщина?».

Почему это хороший вопрос для начала? Да потому, что он отметает половину возможных вариантов при любом ответе. Если вы спросите «Вы королева Англии?», то в случае успеха отбросите миллионы других вариантов, а в случае (более вероятного) неуспеха — только одного человека. Чтобы сразу угадать, вам должно повезти не меньше, чем выигравшему в лотерею. Значит, секрет игры «20 вопросов» — задавать вопросы так, чтобы каждый раз отбрасывать половину людей, каким бы ни был ответ.

Насколько это эффективно?

Задавать вопросы, которые оставляют половину возможных ответов, — лучше, чем называть конкретное имя, но насколько? Давайте предположим, что я изначально задумал кого-то одного из миллиона. Если после каждого вопроса отметать половину людей, сколько вопросов понадобится? После первого останется 500 000 человек, после второго — 250 000... После десяти вопросов от исходного миллиона останется примерно 1000 человек (рис. 1). Продолжаем... После следующего вопроса осталось 500, потом 250, 125... и на двадцатом вопросе остается один возможный человек. Если вам удастся каждый раз точно задавать вопрос, после которого останется половина ответов, то вы гарантированно выиграете. И всегда это будет 20 вопросов.

Все это, конечно, алгоритмическое мышление. Мы пытались разработать алгоритм для игры «20 вопросов». Однако до конца решить задачу не удалось — было непонятно, как определить нужные вопросы. Это остается вашей задачей во время игры. Здесь используется еще один трюк вычислительного мышления — декомпозиция (разложение на части). Надо разделить проблему на части, чтобы сосредоточиться на каждой отдельно. Пока у нас получилось найти общую стратегию. Подобрать конкретные вопросы, которые оставят половину вариантов, — отдельная проблема.

Декомпозиция — популярная стратегия для решения задач и жизненно важный инструмент информатики. Задачи, которые надо решать при составлении программ или разработке процессов (например, для вашего ноутбука или телефона), имеют гигантские масштабы. Современные компьютерные микросхемы сложнее, чем дорожная сеть всей планеты Земля. Представьте, что вы пытаетесь решить такую задачу в один прием. Это можно сделать, только разложив ее на части и работая над ними отдельно.

Декомпозиция полагается на абстракцию — сокрытие деталей. Здесь мы абстрагируемся от конкретных вопросов и думаем только о том, какого типа вопросы надо задавать. Мы также использовали декомпозицию, когда размышляли, насколько эффективным был наш изначальный алгоритм. Чтобы выяснить, каким образом можно написать книгу, мы разложили одну задачу на две: выяснить, как передавать отдельные буквы, и провести всю необходимую работу с помощью полученного решения.

Новый алгоритм

Итак, если правильно задавать вопросы, то в худшем случае понадобится только 20 вопросов, чтобы угадать задуманного человека из миллиона возможных вариантов. Вспомним теперь, что хватит 13 вопросов (в худшем случае — 26), чтобы определить одну из 26 букв алфавита. «Да/нет» не отличается от «моргнуть / не моргать». А спрашивать «Это A? Это В?» — примерно то же самое, что спрашивать «Вы Микки-Маус?» или «Вы Нельсон Мандела?». Вы точно так же пытаетесь выяснить, о какой из многих вещей я думаю. Это опять-таки та же самая задача, что и предиктивная система набора текста в телефонных сообщениях!

Но если это та же самая задача, то и соответствующая ей стратегия должна обеспечить нам более удачное решение, чем уже найденное. Здесь мы снова используем сопоставление с образцом и обобщение. Мы преображаем задачу, чтобы повторно использовать решения. Каков эквивалент решения, которое оставит только половину вариантов, применительно к алфавиту? Сначала, наверное, имеет смысл спросить: «Это гласная?» — но как будут выглядеть остальные четыре вопроса? Каждый раз оставлять только половину вариантов из алфавита? Напрашивается такой первый вопрос: «Это между А и М?» Если ответ утвердительный, то потом мы спрашиваем: «Это между А и F?» Если ответ отрицательный, мы спрашиваем: «Это между N и S?» — и так далее. Таким образом мы гарантированно доберемся до любой буквы алфавита, которую задумал человек, всего за пять вопросов, как это показывает дерево решений на рис. 2. Начните сверху диаграммы и двигайтесь вниз в соответствии с ответами «да/нет».

В этот момент нужно подключить еще один компонент алгоритмического мышления. Необходимо прояснить все детали, потому что здесь можно запутаться. Спрашивая «Это между А и М?», надо уточнить, входит ли «М» в этот промежуток (входит).

Попробуем еще больше усовершенствовать эту технику, используя частотный анализ. Поскольку букв только 26, реально добраться до «Е» и других распространенных букв быстрее чем за пять вопросов. Попробуйте сделать дерево решений, которое это обеспечит. Кроме того, можно использовать принцип предиктивного набора текста, чтобы предугадывать набранные не до конца слова. Все подобные решения из более ранних алгоритмов применимы и здесь. Мы повторно используем готовые решения.

Коды для букв

Дерево решений представляет собой совсем другой подход. Если мы примем «да» и «нет» или «моргнуть» и «не моргать» за 1 и 0, тогда дерево решений определит двоичную последовательность, которую должен усвоить больной с синдромом «запертого человека», чтобы обозначить каждую букву (рис. 3).