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

Таким образом, чтобы ускорить процесс, можно отказаться от вопросов. Человек, передающий информацию, проходит определенную последовательность для каждой буквы, а другой человек — записывает. Таким образом, обозначая морганием код 0110 (не моргать, моргнуть, моргнуть, не моргать), выражаем букву «P». Соответственно, дерево решений преображаем в таблицу поиска, как на рис. 4. Тому, кто хочет общаться с больным, можно дать либо дерево решений, либо такую таблицу. В сущности, мы только что изобрели код для общения, похожий на азбуку Морзе. И снова очевидно, что наша задача, в сущности, аналогична той, которую пытался решить Сэмюэл Морзе, чтобы передавать информацию с помощью телеграфа. Точки и тире соответствуют нашем единицам и нулям или вариантам «морг­нуть» и «не моргнуть». И снова мы применяем обобщение.

Однако не стоит выбирать решение второпях. Детали играют большую роль. Если не задавать вопросов, как узнать, что человек передает информацию? Если он не моргает, что это значит — он уснул или просто ничего не говорит? Как узнать, что он начал передавать буквы? Сколько времени продолжается «неморгание»? Небольшое изменение привело к необходимости решить много новых проблем. Сэмюэл Морзе их решил. В азбуке Морзе с этой целью используются три символа, а не два: точки, тире и тишина. Продолжительность каждого элемента точно определена. Какой бы долгой ни была точка, пауза между точками и тире одинаковая. Между буквами она в три раза дольше точки, между словами — в семь раз. Это обеспечивает структуру, которую мы потеряли, отказавшись от вопросов.

Решение в виде кода отлично подошло для телеграфа, и его вариант лежит в основе взаимодействия компьютеров в сети. Но можно ли сказать, что это решение больше подходит человеку с синдромом «запертого человека», — вопрос спорный. Машинам легко иметь дело с точными промежутками времени, а людям это гораздо сложнее, чем просто задать вопрос.

Алгоритмы поиска

Наше решение для игры «20 вопросов» можно использовать, чтобы помочь пациенту с синдромом «запертого человека» разговаривать, потому что задача, в сущности, не меняется. Это задача поиска: у нас есть серия предметов и надо найти один конкретный. Решения для этой задачи называются алгоритмами поиска, и они обеспечивают беспроигрышный способ что-нибудь найти. Первый подход, проверка всех вариантов по очереди («Это A?», «Это B?..», «Это певица Адель?», «Это Джеймс Бонд?..»), — алгоритм под названием линейный поиск. Порой это лучшее, что есть в вашем распоряжении. Например, если вы были свидетелем ограбления и участвуете в опознании преступника из нескольких людей, линейный поиск будет для вас оптимальным: рассмотрите по очереди каждое лицо, пока не увидите в ряду человека, который совершил преступление. Линейный поиск хорошо работает и тогда, когда вещи, среди которых вы ведете поиск, никак не упорядочены. Если вы ищете носок, который может быть в любом ящике комода, начните сверху и последовательно проверяйте ящики один за другим.

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

Кроме этих двух, есть еще много алгоритмов поиска. Например, каким образом поисковая система вроде Google просматривает каждую веб-страницу на планете за доли секунды? Она использует еще более продвинутый алгоритм!

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

Значит, надо было устроить так, чтобы помощница задавала Боби вопросы, после которых исключалась бы половина из возможных вариантов. Представьте себе: придется задать в худшем случае пять вопросов вместо 13 в среднем, помноженные на все количество букв в книге. И речь идет не только о книге, но и о разговорах с друзьями и родственниками, докторами и медсестрами. Если бы он был немного знаком с информатикой, насколько легче могла бы стать его жизнь!

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

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