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

И снова изобретаем фокусы

Новое из старого

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

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

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

Новые фокусы с помощью информатики

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

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

Выберите стопку

Давайте посмотрим, как этот принцип работает в «Сне об австралийском маге». Как мы увидели на примере перфокарт, он работает, потому что на каждом этапе мы сбрасываем и оставляем некий набор чисел в зависимости от их представления в двоичной системе. На первом этапе уходят перфокарты с нечетными числами, то есть с 1 в первой позиции двоичного кода (в первом колонке) – это 1, 3, 5, 7, … (0001, 0011, 0101, 0111, …). В следующем раунде мы отбрасываем числа 2, 6, … Это карты с 1 во второй позиции двоичного кода (во втором колонке), то есть 0010, 0110, … Это не все карты, у которых есть 1 в этой позиции, потому что некоторые мы уже отбросили. Давайте перечислим все такие карты. У нас получится более длинный список: 2, 3, 6, 7, 10, … (0010, 0011, 0110, 1111, 1010, …). В следующий раз избавляемся от карт с 1 в третьей позиции двоичного кода (колонке четверок). В полный список войдут 4, 5, 6, 7, 12, … (0100, 0101, 0110, 0111, 1100….). Теперь стоит отметить, что мы наблюдаем здесь еще одну модель. Первое число в каждом списке карт указывает на колонку в двоичном коде, которой соответствует весь список.

На этом основан еще один фокус. Сделайте стопку карт, на которых написаны числа 1, 3, 5, 7, 9, 11, 13, 15. Сделайте еще одну стопку карт, с числами 2, 3, 6, 7, 10, 11, 14, 15. Сделайте третью стопку, с 4, 5, 6, 7, 12, 13, 14, 15. И наконец, четвертую, с 8, 9, 10, 11, 12, 13, 14, 15. Перетасуйте карты в каждой стопке. Сами стопки могут идти в любом порядке.

Теперь попросите добровольца задумать число от 1 до 15 и запомнить его, но не говорить вам. Возьмите одну из стопок и сдавайте карты по одной. Объясните, что вы читаете мысли человека, который смотрит на карты, даже не глядя на него. Вам достаточно смотреть на карты. Когда вы закончите сдавать карты, попросите добровольца сказать, было ли задуманное число в этой стопке, что является «дополнительной проверкой на детекторе лжи», которая поможет вам настроиться на его мысли. Если доброволец скажет, что число было в стопке, отложите карты в сторону. Если нет, оставьте их на месте. Повторите эту процедуру с каждой стопкой.

После четвертой стопки назовите число, которое задумал доброволец! Как же вы это сделали?

Достаточно запомнить самое маленькое число в каждой отложенной стопке. Сложите их, и получится число, которое задумал человек. Почему? Эти самые маленькие числа отражают разряд в двоичном коде, который есть во всех картах из этой стопки. Так, если стопка отброшена, то загадочное число имеет 1 в этом разряде. Сложите эти малые значения, и вы переведете число из двоичного кода в десятичный. Например, если сброшены стопки 1 и 4, это значит, что искомое число – 0101 в двоичном коде или 5 в десятичном (0 × 8 + 1 × 4 + 0 × 2 + 1 × 1 = 4 + 1 = 5).

Таким образом, у вас появился новый фокус на основе той же математической модели, что и предыдущий.

Примечание фокусника

Считается, что принцип 16-й карты стал известен в 1958 г., когда программист и известный фокусник Алекс Элмсли опубликовал фокус «7–16» в журнале фокусников Ibidem. Он известен в среде фокусников благодаря манипуляции с картами, названной в его честь «счет Элмсли».

От фокусов к программам и наоборот

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

Глава 4
Головоломки, логика и образцы

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

Головоломки «Улей»

Логические головоломки

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

Говоря о логическом мышлении, в определенном отношении мы подразумеваем способность мыслить ясно и учитывать даже небольшие детали. Однако есть и более глубокий смысл – умение работать с математической логикой, и если вы им обладаете, то будете успешно выдвигать неопровержимые аргументы. Логически обоснованные аргументы неоспоримы, и еще древнегреческие философы осознали их важность. Умение найти неоспоримые аргументы полезно людям любых профессий, а не только программистам. Это нужно и для решения головоломок, только здесь оно сведено к чистой логике. Как и любой другой навык, логическое мышление можно освоить и улучшить. Для этого необходима практика (надо много тренироваться, как и в любом другом случае), разгадывание головоломок – приятный способ ее получить. Чем больше вы решаете головоломок, тем больше полезных хитростей подскажет вам вычислительное мышление.

Соты в улье

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

Головоломка «Улей» представляет собой блок из шестиугольников – символический улей с сотами. Его участки разделены толстыми линиями. Заполняя улей, необходимо соблюдать два правила.

1. В каждой выделенной области должны находиться числа от 1 и до числа, равного количеству шестиугольников в области. Например, самый верхний уровень в головоломке на рис. 12 состоит из четырех шестиугольников, поэтому их надо заполнить числами 1, 2, 3 и 4. Числа нельзя повторять. Если в области всего два шестиугольника, как на этом рисунке, то нужно внести числа 1 и 2.

2. Шестиугольники с одинаковыми номерами не могут соприкасаться ни с одной гранью. Таким образом, поскольку в улье на рис. 12 в среднем шестиугольнике стоит 4, ни в одном из пяти, окружающих его шестиугольников 4 стоять не может.

На рис. 12 представлена простая головоломка «Улей», которую мы предлагаем решить. Попробуйте сделать это, прежде чем продолжить чтение.

Решаем головоломку «Улей»

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

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

Наконец, слева внизу у нас есть область из двух ячеек. В них должны стоять 1 и 2 (по первому правилу). В одном шестиугольнике уже есть 2, так что единственный вариант для оставшегося шестиугольника – это 1 (рис. 14).

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

Теперь постараемся понять, куда в этой же области нужно поставить 2. Оба нижних шестиугольника соприкасаются с 2, и единственно, куда можно написать 2, – в ячейку между двумя единицами справа внизу (рис. 16).

Над этой областью стоит 4, и рядом нельзя поставить еще 4 – ее нужно расположить внизу. Это определяет, где должны оказаться 3 и 4 относительно остальных шестиугольников, как показано на рис. 17.

Итак, у нас осталась верхняя область. Заполняем ее, рассуждая похожим образом. В прилегающей области стоит 1, значит, единственное возможное место для последней 1 – верхний левый угол, как на рис. 18.

Соответственно, в последний шестиугольник надо поставить 3, поскольку в этой области должны стоять числа 1–4 и недостает только 3. Решение целиком показано на рис. 19.

Мы разгадали головоломку. И сделали это, исходя из двух правил и исходных данных – известных чисел. Основываясь на них, мы многократно выявляли новые факты в этой головоломке. Мы прибегли к особому виду логических рассуждений, называемому дедукцией, который позволяет с помощью известных фактов и правил мироустройства (в данном случае – правил головоломки) получать новые факты. Считается, что именно так Шерлок Холмс творил свои детективные чудеса. Он подмечал разные детали в людях и ситуациях, а потом с помощью дедукции выводил новые факты, которые являлись следствием этих деталей. Чем больше фактов он узнавал, тем дальше мог продвинуться в дедукции, что и позволяло в конечном итоге раскрывать преступления. Ученые-информатики и математики используют похожий метод. Хорошие программисты обращаются именно к дедукции, чтобы убедиться в бесперебойной работе своих программ.

Выводим правила

Сопоставляем с образцом и создаем правила

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

Правило одного шестиугольника

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

3. ЕСЛИ в области есть только один шестиугольник, ТО в нем может стоять только 1.

Чтобы наглядно представить это правило и не ограничиваться словами, мы набросаем схему (рис. 20). Стрелка показывает, какие изменения мы вносим в улей. Слева изображена позиция сопоставления с образцом, а справа – вносимые изменения, если найдем образец. Подобные правила называются порождающими правилами, правилами логического вывода или правилами подстановки. Наше правило в виде схемы показывает, что если мы найдем пустой участок в один шестиугольник, то можем преобразовать его в шестиугольник с 1.

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

Правило двух шестиугольников

Теперь выведем еще одно новое правило для областей, состоящих из двух шестиугольников. Мы видели, что если есть область из двух шестиугольников и в одном стоит 2, то во второй нужно поставить 1 (рис. 21).

Мы вправе рассматривать это как обобщенное правило из конкретного примера нашей головоломки. Не важно, в каком шестиугольнике стоит 2, – логика не меняется. Даже если картинку перевернуть, правило останется прежним. Это правило применимо и к шестиугольникам, соприкасающимся по диагонали в любом направлении. Но обобщение можно продолжить. По той же логике, если в области из двух шестиугольников в одном уже стоит 1, в другой нужно поставить 2. Это показано на рис. 22.

Объединив два эти отдельные правила, мы получаем полное обобщенное правило:

4. ЕСЛИ один шестиугольник в области из двух содержит 1 или 2,ТО в другом шестиугольнике будет второе число из этих двух.

Правило можно представить в виде схемы, где x будет обозначать любое число (точно так же, как математики используют x и y для обозначения переменных в алгебре).

В одном случае x заменяет 1, а в другом – 2, но замена остается неизменной в рамках одного примера. Схема правила приведена на рис. 23. На схеме x обозначает другое число. То есть если x – это 1, то x – это 2 и если x – это 2, то x – 1. Это правило подходит для области из двух шестиугольников, повернутой в любую сторону, и не важно, какое число стоит наверху, а какое – внизу. Схема превращается в одно из изначальных правил (и их схем), если заменить x на 1 или 2. Так мы начали изобретать своего рода математические обозначения, которые используются с той же целью, что и символы в математике. Они дают возможность говорить о вещах с большой точностью, и это важно, так как по мере усложнения правил надо стараться избегать возможных ошибок.

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

Правило угла

Давайте рассмотрим последний пример создания более общего правила на базе нашего для решения простой головоломки. Оказывается, он весьма полезен. Мы поняли, куда поставить 1 в области из четырех шестиугольников в нижнем углу. Это было возможно, потому что в прилегающей области уже стояла 1, устроившаяся в углу, как показано на рис. 24.

Единицу нужно поставить в позицию a, b, c или d (рис. 24). Однако в соответствии со вторым правилом головоломки рядом не должна находится ячейка с 1. Значит, позиции b и с исключаются. Остается только позиция d, и только туда получается поставить 1. Мы можем изобразить этот этап в виде схемы для правила замены (рис. 25).

Конечно, в любых пустых шестиугольниках уже могут стоять числа, но правило остается справедливым – это еще один способ обобщить наше новое правило. Кроме того, число, которое мы используем при сопоставлении с образцом, необязательно должно быть 1. Это может быть любое другое число в рамках достаточно большой области. Если мы опять поставим x на место любого возможного числа, то наше правило становится обобщенным вариантом (рис. 26).

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

Получаем обобщенное правило:

5. ЕСЛИ шестиугольник соседствует с областью из четырех шестиугольников и только три из четырех соприкасаются с ним, ТО в четвертом будет стоять то же число, что и в указанном вначале шестиугольнике.

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

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

Записываем правила

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

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

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

ЕСЛИ <какая-то ситуация> ТО <действие, которое надо выполнить>

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

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

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