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

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

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

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

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

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

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

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

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

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

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

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

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