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

Этот фокус получается потому, что, если несколько раз сбросить каждую вторую карту, у вас обязательно останется 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. Численное моделирование — это создание моделей вычислительных процессов с целью их изучения. Здесь мы прибегли к моделированию, чтобы посмотреть, всегда ли получается фокус, но подобным образом можно провести и обобщение. Наша модель показывает принцип, лежащий в основе фокуса. Главное в нем — не игральные карты. Мы абстрагировались от них, как и от многих других деталей. Выявив этот базовый принцип, мы можем придумать другие варианты фокуса, основанные на нем. Мы еще вернемся к этому позже.

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

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

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