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

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

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

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

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

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

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

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