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

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

Как и в случае с «Ходом конем», задача — найти алгоритмическое решение. Убедитесь, что ваше решение действительно работает. Сколько времени у вас ушло? Оказалась ли эта задача легче, чем предыдущая (то есть вы решили ее быстрее)?

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

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

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

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

Для задачи экскурсовода нужно проверить, удовлетворяет ли итог следующим требованиям.

1. Экскурсия начинается в отеле.

2. Туристы посещают все достопримечательности.

3. Они не проходят одно и то же место дважды.

4. Экскурсия завершается в отеле.

Вернитесь назад и запишите список требований к головоломке «Ход конем». Видите что-нибудь похожее? Мы вернемся к этому ниже.

Возможно, вам показалось, что задача «Ход конем» сложнее, но на деле это не обязательно так. Решить ее будет очень легко, если использовать еще некоторые приемы из компьютерного мышления.

Почему задача экскурсовода легкая? Карта метро дает важную информацию, незначительные детали опущены. Это хороший пример абстракции— решение легко увидеть. Без карты было бы сложнее, даже если бы мы знали, где что находится. Карта метро — особый способ предоставления информации. Это особый вид схемы под названием граф.В информатике под графом подразумевают несколько кружков (мы называем их вершинамиграфа) и линий, которые их объединяют ( ребраграфа). Вершины и ребра представляют те аспекты данных, которые нас интересуют. Ребра показывают, какие вершины объединены таким образом, что это важно для решения нашей задачи. Туристические достопримечательности, вероятно, соединены автомобильными дорогами, но по-другому. В этом случае граф пути был бы другим — и он понадобился бы нам, если бы мы организовывали автобусный тур!

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

Графы часто используются, чтобы представить информацию о связях между объектами. Это маршруты на автобусных остановках, карты поездов и метро. Граф — очень хорошее представлениев ситуации, когда нужно проложить маршрут из одного места в другое, как в нашем случае. Упрощенный граф облегчает составление маршрута по сравнению с максимально точной картой, где трудно выделить нужную информацию среди многочисленных подробностей.

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

Возможно, вы уже заметили, что головоломка «Ход конем» и задача экскурсовода очень похожи друг на друга. Если вы записали требования для «Хода конем», то, вероятно, увидели полное совпадение.

1. Тур начинается в заданной точке.

2. Необходимо посетить все точки.

3. Нельзя проходить уже посещенную точку.

4. Необходимо закончить в начальной точке.

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

Итак, задача экскурсовода оказалась легкой, потому что мы представили ее в виде графа. Так почему бы нам не сделать то же самое и с задачей «Ход конем»?

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

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