Читать «Вычислительное мышление: Метод решения сложных задач» онлайн - страница 39

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

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

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

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

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

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

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

Почему это легко?

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

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

Это не важно!

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

Упрощаем

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