Решение проблемы можно облегчить, выбрав для нее хорошее представление, котороеявляется способом организации информации. Есть на удивление много возможностей представить одну и ту же информацию, и, как только вы это осознаете и с самого начала сосредоточитесь на выборе хорошего представления, задачи станут проще. Как мы видели на примере задач с составлением графа и игры «Бусы, хлеб, баня», хорошее представление значительно облегчает весь процесс как для людей, так и для компьютеров. Однако оно может полностью поменять используемый алгоритм. Порой очевидно, что благодаря верному представлению открываются возможности использовать простой и быстрый алгоритм вместо медленного и сложного. В этой книге мы ознакомились с разными представлениями — например, растровые изображения, состоящие из большого количества пикселов, формирующих решетку, и векторные изображения в виде линий и фигур. Мы узнали, что представление в виде сетки открывает самые разные возможности. Также мы увидели, что если числа хранятся в двоичном представлении на перфокартах, то возможен быстрый поиск и применение алгоритма упорядочивания. Представление образца в виде цифрового фильтра позволяет создать алгоритмы, помогающие компьютерам видеть. То есть выбор хорошего представления является важной частью абстрагирования и генерализации.
Абстрагирование
Абстрагирование — это сокрытие деталей разными способами с целью облегчить решение задачи. Есть масса разных способов, которые позволяют спрятать подробности. Этому способствует создание алгоритмов и их оценка.
Один из важных способов использования абстрагирования, который называется абстракция управления, мы рассмотрели на примере фокусов. Он состоит в объединении инструкций, что позволяет получить инструкции для достаточно больших этапов процесса. Идея здесь состоит в том, чтобы спрятать подробности отдельных маленьких шагов. В кулинарных книгах это встречается на каждом шагу. Там даются инструкции вроде «сварите картошку». Сюда входит много этапов: наполнить кастрюлю водой, включить конфорку, довести воду до кипения, положить картошку и так далее. Все эти шаги сведены вместе в одну простую команду «сварите картошку». Чтобы выполнить инструкцию, нужны все детали, но абстрагирование помогает записать инструкции и воспринимать алгоритм (или рецепт) в целом, чтобы работать с большими шагами. Изобилие подробностей мешает думать, пока вы не дойдете до них и не начнете с ними работать. Эта форма абстрагирования очень близка к декомпозиции, которую мы опишем ниже.
Есть еще один тип абстрагирования — абстрагирование данных. В этом случае прячут подробности хранения данных, то есть как они представлены на самом деле. Например, числа в реальности хранятся на компьютере в бинарном коде — как последовательность нолей и единиц. То есть число 16 выглядит как 00010000. Мы игнорируем этот факт, когда думаем о числах. У нас в голове именно 16 — десятичное число, которое мы привыкли использовать. Когда мы пишем программы, то используем в инструкциях десятичные числа, а не двоичные. Но наши программы просят пользователей вводить десятичные числа. При этом компьютер с ними не работает. Пользователям вообще не надо знать, что числа хранятся именно в таком виде, — эта подробность спрятана.
Мы используем абстрагирование не только при создании программ. Оно подходит и для их оценки. Например, как мы видели ранее, оно кстати при выборе алгоритма для помощи пациенту с синдромом «запертого человека». Если нужно решить, какой из двух алгоритмов с одинаковой задачей работает быстрее, не надо думать о времени как таковом. Отвлечемся от этих подробностей и будем думать только о выполненной работе — сколько операций нужно провести, чтобы довести до конца каждый алгоритм и справиться с задачей. Если для одного алгоритма нужно выполнить 100 инструкций, а для другого — только 10, то второй будет быстрее. Проверяем это, просто пересчитывая операции, не засекая время. Мы прячем подробности о временны`х затратах на операции, чтобы облегчить себе задачу.
Обобщение
Идея взять решенную проблему и приспособить ее решение (алгоритм) к другим подобным задачам называется обобщением. Предположим, что нужно найти свое имя в списке рассадки гостей. Этот список — представление имен, из которого мы узнаем, где сидим. Вместо того чтобы искать в случайном порядке, мы начинаем сверху и проверяем каждое имя по очереди, пока мы не дойдем до своего. Другой пример — надо найти на полке CD, и мы понимаем, что это похожая задача. Таким образом мы осуществляем сопоставление с образцом — сравниваем одну задачу с другой. Как только мы осознаем, что две задачи сводятся к одной, то используем для обеих одно и то же решение, и необходимость поиска нового алгоритм отпадает. Мы начинаем с одного конца и ведем пальцем по полке, проверяя каждый диск по очереди, пока не найдем нужный (или не доберемся до конца, что будет означать отсутствие диска). Мы обобщили и преобразили алгоритм (решение для первой задачи) и используем его для решения новой задачи.
