2. РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ
Эта глава преследует двойную цель. Во-первых, мы вводим некоторые из основных структур данных, которые полезны при разработке эффективных алгоритмов для обширных классов задач. Во-вторых, описываем некоторую технику "программирования", такую, как рекурсия и динамическое программирование, которая применяется во многих эффективных алгоритмах.
В гл. 1 мы рассмотрели основные модели вычислений. Хотя нашей простейшей моделью является РАМ, мы не хотим, как правило, описывать алгоритмы в терминах подобного устройства. Поэтому мы ввели Упрощенный Алгол (разд. 1.8). Но даже этот язык оказывается слишком примитивным, если не ввести в рассмотрение структуры данных, более сложные, чем массивы. В этой главе мы познакомим читателя с такими элементарными структурами данных, как списки и стеки; они часто используются в эффективных алгоритмах. Мы покажем, что с помощью этих структур можно представлять множества, графы и деревья.
Наше изложение по необходимости будет кратким, и читателю, не знакомому с обработкой списков, следует обратиться к одному из более полных источников, указанных в конце данной главы, или уделить особое внимание упражнениям.
Мы включили также раздел о рекурсии. Один из важных аспектов рекурсии — облегчить понимание алгоритмов. Хотя примеры, приводимые вэтой главе, слишком просты, чтобы полностью подтвердить это заявление, но в последующих главах рекурсия очень поможет в учете организации информации при точном изложении сравнительно сложных алгоритмов. Рекурсия сама по себе не приводит к более эффективным алгоритмам. Но в сочетании с другой техникой, такой, как балансировка, прием "разделяй и властвуй", алгебраические упрощения, она, как мы увидим, часто дает алгоритмы, одновременно и эффективные, и элегантные.
