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

Делим на части

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

Обратите внимание, что здесь мы прибегли к абстрагированию, то есть прячем детали. В этом описании мы скрыли, как выполняются шаги. Эти детали можно записать в виде отдельного мини-алгоритма. Например, алгоритм для шага, когда мы сбрасываем каждую вторую карту, как показано на рис. 6b.

На самом деле мы уже занимались такого рода абстрагированием для каждого из шагов в начальной версии алгоритма. Зачем? Чтобы вы увидели общую идею и не увязли в подробностях.

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

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

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

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

Всегда ли получается фокус?

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

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

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

Это уменьшает объем необходимых тестов. Нам просто нужно проверить, получается ли фокус вне зависимости от того, как мы делим колоду. Останется ли у нас 16-я карта, независимо от того, куда укажет доброволец? Колоду можно разделить только в 52 местах, поэтому теперь мы знаем, что достаточно проверить 52 случая и посмотреть, всегда ли остается 16-я карта. Возможно, к этому моменту вы уже поняли, что это не всегда срабатывает! Необходимо ограничить промежуток, в рамках которого можно делить колоду…

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

Пятьдесят два варианта – это слишком много, а программисты (в отличие от фокусников) по натуре ленивы. Зачем делать больше работы, чем необходимо? Давайте лучше еще порассуждаем. Давайте сделаем упрощенную схему колоды и посмотрим, что получится, если сбрасывать каждую вторую карту. Такого рода вычислительное моделирование является важной частью вычислительного мышления. В нашей модели каждую карту представляет ее позиция в начале фокуса. Мы используем «…», чтобы показать, продолжается ли ряд чисел (снова абстракция). Вот наша модель колоды:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 …

Что останется, если мы сбросим каждую вторую карту, начиная с первой? Только четные позиции, а это означает, что 16-я карта останется на месте:

2 4 6 8 10 12 14 16 18 …

Мы снова сбрасываем каждую вторую карту, и остаются следующие позиции:

4 8 12 16 …

а потом

8 16

и, наконец,

16.

Эта модель показывает, что как при большем, так и при меньшем числе карт происходит одно и то же. Очевидно, что 16-я карта остается в любом случае, если убирать каждую вторую.

Однако у нас остается проблема, связанная с «…». Здесь мы наблюдаем важное свойство абстрагирования. Если отбросить важную деталь, то мы, вероятно, получим неправильный ответ. Логическое мышление тоже с легкостью заведет вас не туда, если не продумать в точности все возможные варианты. Если бы в начале фокуса мы разделили колоду в какой-то точке до 16-й карты, то, конечно, эта карта ушла бы при первом разделении. Тогда у нас осталась бы другая карта, например восьмая. Возможно, вы поняли это, как только обратились к абстрагированию. Однако есть еще одна похожая, но немного более тонкая проблема. Давайте снова проведем моделирование, но увеличим масштаб. Результат показан на рис. 7.

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

Итак, мы использовали численное моделирование и логическое мышление и таким образом убедились, что фокус действительно работает, но при условии, что перед тем, как мы начинаем сбрасывать карты, их в колоде минимум 16 и максимум 31. Численное моделирование – это создание моделей вычислительных процессов с целью их изучения. Здесь мы прибегли к моделированию, чтобы посмотреть, всегда ли получается фокус, но подобным образом можно провести и обобщение. Наша модель показывает принцип, лежащий в основе фокуса. Главное в нем – не игральные карты. Мы абстрагировались от них, как и от многих других деталей. Выявив этот базовый принцип, мы можем придумать другие варианты фокуса, основанные на нем. Мы еще вернемся к этому позже.

Перфокарты

Магия успешного поиска

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

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

На рис. 8 приведен пример перфокарты для числа 22. Чтобы увидеть, как использовать перфокарты для поиска данных с помощью магического принципа «шиворот-навыворот», давайте сделаем их сами, а потом посмотрим, как они действуют.

Шаблоны для перфокарт можно скачать здесь: www.cs4fn.org/punchcards/.

Распечатайте их – в идеале прямо на тонком картоне – и слегка посыпьте тальком, чтобы они не склеивались (это важно).

Вместо отверстий и их отсутствия мы будем использовать в нашем коде отверстия и небольшие вырезы. Вам следует сделать вырезы в нужных местах, чтобы в сумме получилось число, крупно написанное на карте. Например, на карте 22 есть вырезы напротив 16, 4 и 2, а 16 + 4 + 2 = 22. Чтобы понять происходящее, нужно знать кое-что из простой математики, а именно двоичную систему счисления.

Две системы

Двоичный код – это способ записывать числа, при котором в нашем распоряжении 0 и 1 вместо 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9, которыми мы обычно пользуемся. Наша обычная система называется десятичной. В двоичной системе всего два символа, и на перфокартах мы будем использовать круглые отверстия для 0 и щели для 1. Двоичная и десятичная системы – просто две разные системы представления чисел. Выбрать правильное представление информации – еще один важный элемент вычислительного мышления.

Давайте сначала рассмотрим десятичную систему и сравним ее с двоичной. В десятичной системе, чтобы досчитать до 9, мы используем цифры, но они заканчиваются, и в этот момент мы переходим в новый столбик. Мы возвращаемся к 0, но переносим 1 в следующий столбик, и 1 теперь обозначает 10, как показано на рис. 9.

Любая цифра во втором столбике обозначает на 10 больше, чем та же цифра в первом столбике. В десятичной системе 16 – это один десяток (1 в столбике десятков) и шесть единиц (6 в столбике единиц). Мы добавляем 10 к 6, чтобы получить число 16. Подобным образом, 987 обозначает 9 раз по 100, 8 раз по 10 и 7 раз по одному, сложенные вместе.

Двоичная система работает точно так же, только у нас раньше заканчиваются цифры. Дойдя до 1, мы уже переходим в новый столбик, до 9 нам не добраться (рис. 10). Это значит, что столбцы теперь предназначены для единиц, двоек, четверок, восьмерок и так далее – вместо единиц, десятков и сотен. То есть в двоичной системе (используя только 1 и 0) мы записываем, например, число 5 как 101. Это 1 в разряде четверок плюс 0 в разряде двоек и плюс 1 в разряде единиц.

Если распределить это на пять колонок (как мы сделаем это на перфокартах), то 5 в двоичной системе будет выглядеть как 00101.

Подобным образом, 16 в двоичной системе – это 10000.

Отметим, что, помимо колонки единиц, все остальные колонки обозначают степени двойки, то есть четные числа. Поэтому единственный способ представить нечетное число в двоичной системе – поставить 1 в колонку единиц. У всех нечетных чисел в ней будет 1, а у четных – 0. Насколько это важно, мы увидим ниже.

Двоичные перфокарты

Какое отношения это имеет к нашим перфокартам? На них мы можем записывать числа в двоичной системе, используя отверстия для 0 и вырезы для 1. Чтобы записать на перфокарту число 5, начиная слева, нам нужно отверстие (0), еще отверстие (0), потом вырез (1), снова отверстие (0) и, наконец, вырез (1). Для числа 16 (10000) нам нужен один вырез и 4 отверстия. Если у нас есть место для пяти отверстий, мы можем записать на карту любое число до 31. Имея достаточно места (то есть достаточно степеней двойки и, соответственно, разрядов), мы можем записать любое число. Описанные примеры перфокарт приведены на рис. 11а и 11b.

Как только мы записали на карту число в двоичном коде в виде отверстий и вырезов, можно с легкостью найти любую карту. И здесь наступает черед метода «шиворот-навыворот».

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

Например, мы ищем карту с номером 16. В двоичной системе это 10000. При движении слева направо выходит:

ВЫРЕЗ 1: 0 – СБРОСЬТЕ упавшие карты.

ВЫРЕЗ 2: 0 – СБРОСЬТЕ упавшие карты.

ВЫРЕЗ 4: 0 – СБРОСЬТЕ упавшие карты.

ВЫРЕЗ 8: 0 – СБРОСЬТЕ упавшие карты.

ВЫРЕЗ 16: 1 – ОСТАВЬТЕ упавшие карты.

Многократно сбрасывайте нижнюю стопку, пока, в пятом раунде, ее не нужно будет оставить. У вас останется карта с номером 16. Таким образом, прорабатывая двоичный код, можно найти любую карту. Попробуйте найти карту 5. В двоичной системе это 00101. При движении справа налево получаем:

ВЫРЕЗ 1: 1 – ОСТАВЬТЕ упавшие карты.

ВЫРЕЗ 2: 0 – СБРОСЬТЕ упавшие карты.

ВЫРЕЗ 4: 1 – ОСТАВЬТЕ упавшие карты.

ВЫРЕЗ 8: 0 – СБРОСЬТЕ упавшие карты.

ВЫРЕЗ 16: 0 – СБРОСЬТЕ упавшие карты.

У вас останется карта 5.

Как же это работает?

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

Возьмите первый раунд, когда вы сбрасываете карты и одновременно ищете номер 16. Стряхнув первые перфокарты и затем избавившись от них, вы отметаете все карты с вырезом (1) в первой позиции двоичного числа. Это столбик единиц. У чисел 1, 3, 5, 7 будет вырез (1) в этой позиции – все это нечетные числа. Происходит то же самое, что и в первом раунде «шиворот-навыворот», когда мы сбрасываем каждую вторую карту. Как вы видели выше, мы переводим число из двоичной системы в десятичную, складывая числа в соответствующих разрядах (например, 5 = 4 + 0 + 1). Этот последний разряд единиц полностью определяет нечетные числа, в то время как все остальные – четные (2, 4, 8, 16, …).

Вот еще один способ понять, почему двоичное представление ведет к тому, что нечетные числа отбрасываются, – он поможет нам понять, как работает остальная часть фокуса. Подумайте, как мы считаем в двоичной системе: 0, 1, 2, 3, 4, … – это 000, 001, 010, 011, 100, … В колонке единиц во время счета значение меняется через раз, то есть в этой последней позиции по очереди оказываются 0, 1, 0, 1 – и так далее. Это значит, что если мы отбросим все единицы, то избавимся от каждой второй карты.

То есть мы показали, что в первом раунде происходит то же самое, что и в фокусе. Отбросив все карты с нечетными цифрами, мы переходим к следующему отверстию на перфокарте и, таким образом, к следующей позиции в двоичном числе. Эта операция убирает все числа, в составе которых есть разряд двоек. Например, это 6 (110 в двоичной системе), поскольку 6 = 4 + 2 + 0. На этот раз уходят 2 (10 в двоичной системе), 3 (11), 6 (110), 7 (111), 10 (1010), 11 (1011) и так далее. Однако нечетные числа уже были удалены, значит, на этот раз мы стряхнем 2, 6, 10…. То есть остается каждая вторая карта. Это та же последовательность карт, которую мы удаляем во втором раунде «шиворот-навыворот».

Причина становится очевидной, если посмотреть на второй столбик в числах, записанных двоичным кодом. Там мы видим 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1 …

Получается, что в двоичной записи второй символ меняется только в том случае, если в первой позиции уже были и 0, и 1. Но если убрать каждую вторую карту в этой последовательности, у нас остается не 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1…, а 0, 1, 0, 1, 0, 1…. И мы получаем:

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

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

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

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

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