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

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

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

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

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

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

Коды для букв

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

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

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

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

Выбираем лучшее решение

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

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

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

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

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

Делаем жизнь Боби лучше

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

Главное – алгоритмическое мышление

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

Еще важнее – понять человека

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

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

Более того, решение Боби понятно любому. Наше же относится к более сложным и, вероятно, потребует объяснений. И объяснять этот метод будет не Боби. Думать о людях – это важно.

Описанная ситуация выдвигает на первый план еще один необходимый аспект оценки алгоритма. Мы должны ответить на вопрос: легко ли использовать наш алгоритм, не делая ошибок, и останутся ли у людей хорошие впечатления? Это необходимо сделать, даже если алгоритм выполняет компьютер, а люди взаимодействуют с программой. Так мы учитываем удобство использования и восприятие пользователем алгоритма. Подобная оценка в конечном итоге должна включать тестирование решений с участием реальных людей. И чем быстрее это делается, тем лучше.

Ему подошло

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

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

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

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

Глава 3
Магия и алгоритмы

Искусному фокуснику, который сам придумывает магические трюки, и опытному программисту нужны одни и те же навыки, а именно вычислительное мышление. Фокусы – это алгоритмы, и компьютерные программы – тоже. Оказывается, чтобы осуществить поиск данных, первые компьютеры воспроизводили фокус под названием «Сон об австралийском маге». Программисты, несомненно, настоящие волшебники!

«Сон об австралийском маге»

Механизм предсказания будущего

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

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

Перейдем к тому, что видит аудитория. Вызовите добровольца. Распределите карты в одну линию на столе лицом вверх, чтобы зрители видели, что это обычная перетасованная колода. Объявите, что сначала вам нужно поделить колоду примерно пополам. Попросите добровольца выбрать любую карту примерно посередине и покажите руками, что вы имеете в виду. Вы обязательно должны сделать так, чтобы ваши руки оказались над 16-й и 32-й картами. Таким образом вы ненавязчиво ограничиваете выбор до какого-то варианта между ними. Сбросьте карты справа от той, которую укажет доброволец (нижнюю часть колоды), и попросите его подтвердить, что это был свободный выбор. Возьмите оставшиеся карты и, держа их рубашкой вниз, объясните, что ночью перед выступлением вам всегда снятся странные сны, в которых маги учат вас новым фокусам. Накануне во сне к вам явился австралийский маг и научил методу «шиворот-навыворот», позволяющему угадывать карту, о которой никак нельзя было знать заранее.

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

Теперь укажите вот на какую странную вещь: в вашем сне австралийский маг сказал, что нужно заранее положить в конверт одну конкретную карту. Попросите добровольца посмотреть под столом и достать из конверта карту, предсказанную австралийским магом в вашем сне. Это тоже восьмерка червей!

Поблагодарите добровольца и попросите аудиторию поаплодировать ему.

Хитрые алгоритмы

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

Алгоритм, лежащий в основе «Сна об австралийском маге», показан на рис. 5.

Этот конкретный алгоритм содержит не только шаги, которые надо выполнять последовательно. В нем есть циклы, например «повторите 4 раза». Цикл показывает, что некоторые инструкции надо повторить. Он позволяет не писать одно и то же много раз. Именно такие инструкции программисты используют в компьютерных программах, чтобы компьютер повторил какие-то указания. Есть и второй цикл: «Повторите, пока не останется карт». Этот цикл воспроизводится 4 раза, как указано в первом цикле. Каждый раз вы проходите через всю колоду, оставляя и сбрасывая карты, пока не останется ни одной.

Придумываем фокусы

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

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

Почему это важно для информатики? Именно так мы добиваемся, чтобы работал компьютер. Компьютеры – это куски металла и кремния. Они не понимают, что делают. Просто слепо следуют инструкциям, как ученик колдуна. Программисты делают всю творческую работу, составляя инструкции. Для программирования важен навык писать инструкции очень точно и недвусмысленно, чтобы не допустить несоответствий. Цель каждой инструкции не должна вызывать никаких сомнений: компьютер должен в точности следовать указаниям. Каждый возможный исход событий должен быть описан в инструкции – компьютер не справится с непредвиденным. Однако, следуя этим указаниям, компьютер может творить чудеса (и даже казаться разумным, как мы увидим далее).

Все электронные устройства, которые вы когда-либо видели в действии, слепо следуют алгоритму.