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

Нам необходимо определить эффективность алгоритма. Проведем эксперимент и применим научное мышление.Например, следующим образом: несколько раз определим время, которое уходит на передачу какого-то отрывка с каждым алгоритмом и с разными участниками, и выясним, в каком случае все было в среднем быстрее. Однако на это уйдет очень много времени и сил. Есть способ и лучше.

Можно прибегнуть к аналитическому мышлению.В этом случае необходимо сделать простые вычисления. Например, давайте учитывать не время, а сделанную работу. Если подсчитать, сколько букв алфавита произносит помощница, то мы всегда определим потраченное время. Просто надо знать, сколько времени уходит на произнесение одной буквы, и умножить это время на количество букв. Мы только что произвели действие, которое называется абстрагированием.Это еще один элемент вычислительного мышления, который применяется, чтобы упростить задачи и облегчить написание программ. Абстрагирование – просто длинное слово, которое подразумевает, что некоторые подробности скрывают или игнорируют. Мы проигнорировали такую деталь, как точное время, потраченное на всю книгу, и вместо этого подсчитали произнесенные буквы. «Число произнесенных букв» – это абстракцияреально потраченного времени. Такой принцип очень часто используется в вычислительных процессах, чтобы упростить их работу.

Как же нам выяснить, сколько букв надо произнести? Для этого нужно задать несколько вопросов. Самый простой звучит так: сколько это будет в лучшем случае? Каково минимальное количество букв, которое должна произнести помощница, чтобы получилась книга? Рассмотрим и худший случай. Если не повезет, то насколько? Наконец, рассмотрим средний вариант и таким образом получим реалистичную оценку необходимой работы. Давайте чисто теоретически представим, что нам нужны только буквы алфавита, без цифр и знаков пунктуации. И проанализируем наш простой алгоритм, в соответствии с которым помощница говорит: «A, B, C…»

В лучшем случае вся книга будет состоять только из «А»: «АААА…» (возможно, выражая боль автора). Чтобы общаться при помощи одной буквы «А», достаточно сказать «А» один раз (ответить на один вопрос), и ответ будет получен. Здесь мы снова используем абстракцию – сначала анализируем, что будет, если посчитать только одну букву, и игнорируем всю книгу – по крайней мере для начала. Умножьте наш ответ для одной буквы на количество букв в книге и получите упомянутый лучший случай.

В худшем случае (для латинского алфавита), при котором кто-нибудь, например, все время жужжит («ZZZZ…»), потребуется 26 вопросов для каждой буквы. Итак, мы определили границы, в которых будет происходить передача любой информации. У нас никогда не получится лучше, чем при варианте с одной буквой, и хуже, чем со всеми 26.

Оценка будет точнее, если учесть среднее количество вопросов на каждую букву, то есть средний случай. Сделать это не так трудно. В длинном сообщении на каждую «А» где-нибудь еще придется «Z», на каждую «B» найдется «Y» и так далее. Это значит, что в среднем во всей книге на каждую продиктованную букву надо будет задать 13 вопросов. Умножьте число букв в книге на 13, и вы получите примерную оценку работы при ее написании. Умножьте это на среднее время, которое уходит у помощницы, чтобы произнести букву, и вы получите время, необходимое, чтобы написать книгу.

Отметим, что мы снова оцениваем наш алгоритм – но на сей раз нас интересует не то, действует ли он вообще, а то, насколько быстро он действует. У алгоритма оценивают много разных аспектов, но надежность и эффективность – два важнейших для оценки.

Изменение, внесенное Боби, — сначала спрашивать о распространенных буквах — улучшает ситуацию. Вероятно, получится уложиться в 10‒11 произносимых букв. А с учетом частотности, мы рассчитаем это точнее. Частотность можно уточнить или определить самостоятельно. Возьмите отрывок из любимой книги и посчитайте, сколько раз появляется каждая буква. Потом расположите буквы по порядку, начиная с самой распространенной, и посчитайте вероятность их появления. Средний случай — это число букв, которое необходимо произнести для угадывания одной буквы, вероятность появления которой равна 50%.

Итак, частотный анализ привел к улучшениям, но не слишком значительным, и в худшем случае для выяснения одной буквы все равно надо задать 26 вопросов. Но каждый специалист по информатике знает, что можно существенно улучшить этот процесс. Любая буква выясняется всего за пять вопросов! Гарантированно! И это не средний случай, а худший! Знаете, какие пять вопросов надо задать?

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

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

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

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

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

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

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

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

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

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

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

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

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