Текст книги "Вычислительное мышление: Метод решения сложных задач"

Просто как A, B, C

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

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

Красота алгоритмов в том, что им следуют, не имея представления, чтó именно они значат. В случае с нашим алгоритмом помощница предположительно знает, что и для чего она делает, но книга все равно была бы написана, даже если бы она ничего не понимала. Все, что нужно делать, – считать моргания и записывать буквы в соответствии с полученными инструкциями. Мы могли бы дать помощнице таблицу, чтобы сверять по ней буквы, и тогда работа выполнялась бы без какого-либо ее осмысления вообще. Красота алгоритмов заключается в возможности действовать механически, и в этом их смысл – ведь компьютеры тоже слепо выполняют инструкции. Это умеют абсолютно все компьютеры.

Наш алгоритм общения на деле состоит из двух частей. Одну часть выполняет Боби (моргнуть нужное количество раз), а другую – помощница (сосчитать, сколько раз моргнул Боби, и записать соответствующую букву, когда моргание прекратится). Более того, в информатике есть специальное название для алгоритма, при помощи которого делятся между собой информацией два человека или компьютера, – он называется протокол. Если оба человека выполнят свою часть протокола, то слова, которые задумал Боби, окажутся записанными на бумаге. Если кто-то сделает ошибку – например, собьется со счета и таким образом отойдет от протокола, – то сообщение не будет доставлено. В компьютерах хорошо то, что они не делают таких ошибок, каждый раз точно выполняют инструкции. Коль скоро инструкции верны, машины-то уж точно их верно выполнят.

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

Как это сделал Боби?

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

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

Попробовав, вы, вероятно, осознаете, что для эффективного применения этого метода нужно решить еще кое-какие проблемы. А после нескольких попыток вам, весьма вероятно, придет в голову способ улучшить алгоритм. Что вы можете предложить?

Проверяем детали

Нетрудно осознать, что придется иметь дело не только с буквами алфавита. Нам также понадобятся пробелы, цифры, точки и так далее. Их необходимо добавить к списку букв, который использует помощница. Вероятно, есть способ и получше, чем зачитывать длинный список. Например, сначала задать вопрос: «Это буква?» Если ответ положительный, то будем продолжать как раньше. Если нет, переходим к другим символам. Звучит знакомо? Это та же идея, благодаря которой в компьютерах используются разные наборы символов.

Еще одна проблема, требующая решения: что делать, если человек моргнет по ошибке? У нас должен быть способ сказать: «Проигнорируйте последний раз и начинайте читать буквы с начала». Но так, чтобы не пришлось передавать эту фразу по буквам! Подобным образом, если вы сделали ошибку, нужно найти способ вернуться назад. Нам нужен код, который означает «отменить». Возможность отменить действие – важная часть любого алгоритма с участием людей, так как люди делают ошибки. Например, условимся, что для этого надо быстро моргнуть два раза. Или придумайте что-нибудь получше. Вполне вероятно, что вы обнаружите другие проблемы, требующие решения?

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

Алгоритмическое мышление подразумевает, что мы обдумываем детали и находим решения для возникающих проблем. Мы осознаем, что есть много способов сделать одно и то же, а потом предлагаем улучшенные варианты для конкретной ситуации. Также заметим, что одна из упомянутых выше задач связана с характерной для человека особенностью – свойством ошибаться. Теоретически наше решение работает, надо только моргнуть в нужный момент! И мы могли бы высокомерно заявить, что надо совершать определенные действия, а не получилось – сами виноваты. На практике не всегда моргаешь, когда нужно. И лучше все-таки решить задачу так, чтобы алгоритм работал для людей. В конце концов, мы пытаемся помочь человеку, а не машине! Вычислительное мышление связано еще и с пониманием того, что такое человек.

Улучшаем метод

Что дальше?

Мы могли бы немного ускорить процесс общения для пациента с синдромом «запертого человека», осознав, что порой уже на половине слова можно догадаться, что имеется в виду. Например, если у вас получилось «а-н-т-и-л», с большой долей вероятности можно утверждать, что нужное слово – «антилопа». Значит, поменяем правила так, чтобы помощница высказывала подобные догадки. Кроме того, надо найти способ сказать «нет», если догадка не верна. Например, такое правило: моргнуть, если слово угадано, и не моргать – если нет. Именно по этому принципу работает функция предиктивного ввода текста в телефоне, то есть используется алгоритм для решения очень похожей задачи. То же самое делают поисковые движки, когда вы набираете свой запрос.

Помощники Боби действительно использовали вариант предсказания текста, что и описано в его книге. Он также отмечает, что его очень раздражало, если люди пытались угадать его мысли, не условившись с ним о способе подтверждения. Отсутствие навыков вычислительного мышления у собеседников Боби приводило к тому, что он очень расстраивался, пытаясь «сказать» им, что они ошиблись, а собеседники были уверены, что догадались правильно. Представим, например, что мы продолжаем разговор о животных и я передал буквы «б-а-р-с». Какова будет ваша догадка? Что слово уже закончилось и это слово – «барс»? Нет. Я хотел сказать «барсук».

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

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

В самом широком смысле можно считать, что в случае Боби мы занимаемся передачей информации. В любой ситуации, когда есть необходимость передать информацию, используется общий алгоритм. Программисты создают коллекции алгоритмов для разного рода задач, чтобы при необходимости выбрать наиболее подходящий. Например, азбука Морзе тоже алгоритм передачи информации. Используя разную последовательность точек и тире (в нашем случае – долгое или быстрое моргание), обозначают разные буквы. Этот алгоритм изобрели, чтобы передавать сообщения по телеграфу, но, вероятно, получится использовать его и здесь. Мы еще вернемся к этой идее.

В еще более широком смысле мы вправе представить нашу задачу как поиск очередной доли информации (следующая буква). И видимо, мы сумеем обобщить наш алгоритм настолько, что он позволит искать что угодно. Ниже мы вернемся и к этой идее.

В порядке популярности

Боби предложил другой способ улучшить алгоритм АВС. До того, как оказаться на больничной койке, он был главным редактором французского женского журнала Elle и имел хорошее представление о языке. Например, ему было известно, что E – самая распространенная буква (в английском и французском). Поэтому Боби попросил, чтобы буквы зачитывали в порядке их популярности – то есть частотности. В английском этот порядок таков: E, Т, А, О… Во французском, на котором говорил Боби, это Е, S, А, R… Боби, соответственно, использовал французский порядок. Таким образом, помощница быстрее доходила до распространенных букв.

Похожий трюк использовался веками, чтобы расшифровать секретные коды. Он называется частотный анализ. Алгоритм для использования частотности букв был изобретен арабскими учеными около 1000 лет назад. Марию Стюарт обезглавили, потому что сэр Фрэнсис Уолсингем, начальник разведки королевы Елизаветы I, лучше нее владел вычислительным мышлением. Но это уже другая история. Идея Боби использовать частотный анализ – это пример и сопоставления с образцом, и обобщения. Задачи трансформируются, и решения для них используются повторно. Осознав, что расшифровывание кодов и угадывание букв – процессы схожие, мы видим, что частотный анализ, изобретенный для одного, пригоден для другого.

Насколько это быстро?

Давайте вернемся к алгоритму Боби, который мы определенно усовершенствовали. Новый способ должен быть лучше изначальной идеи – моргать разное количество раз для разных букв. Однако напрашивается вопрос: как быстро это будет – сколько времени уйдет, чтобы написать книгу? Удалось ли найти наилучший способ или можно предложить более быстрый алгоритм, который облегчит написание книги?

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

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

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

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

В худшем случае (для латинского алфавита), при котором кто-нибудь, например, все время жужжит («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 вопросов.

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

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

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