2.9. ЭПИЛОГ

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

с указателями) и позволяют сосредоточиться на общей структуре самого алгоритма. Кроме того, мы увидели, как мощная техника рекурсии и динамического программирования часто приводит к элегантным и естественным алгоритмам. Мы познакомились также с некоторыми общими приемами, такими, как "разделяй и властвуй" и балансировка.

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

Определение. Бесконтекстной грамматикой в нормальной форме Хомского называется четверка где конечное множество нетерминальных символов, (2) 2 — конечное множество терминальных символов, (3) конечное множество пар, называемых продукциями, вида или символы из из и выделенный символ из Мы будем писать если а, (3, у — цепочки, состоящие из терминальных и нетерминальных символов, и принадлежит Языком порождаемым грамматикой называется множество цепочек терминальных символов, где обозначает рефлексивное и транзитивное замыкание отношения

2.34. Напишите алгоритм сложности который определял бы принадлежность данной цепочки языку где бесконтекстная грамматика в нормальной форме Хомского. Указание: Пусть Слово принадлежит языку тогда и только тогда, когда Для вычисления примените динамическое программирование.

2.35. Пусть х и у — цепочки символов и некоторого алфавита. Рассмотрите операции удаления символа из, вставки символа в х и замены символа в х другим символом. Опишите алгоритм нахождения минимального числа таких операций, необходимых для преобразования х в у.

Замечания по литературе

Дополнительную информацию о структурах данных и их реализации можно найти у Кнута [1968] и Стоуна [1972]. Книга Пратта [1975] содержит описание реализации рекурсии в языках, подобных Алголу. Берж [1958] и Харари [1969] излагают теорию графов. Кнут [1968] дает информацию о деревьях и их прохождении. Дальнейшие сведения об алгоритмах прохождения деревьев можно найти у Беркхарда [1973].

Оптимальность алгоритма 2.3 (для нахождения максимума и минимума) показал Поль [1972]. Алгоритм сложности для умножения целых чисел (разд. 2.6) приведен в работе Карацубы, Офмана [1962]. Виноград [1973] рассматривает подобные приемы ускорения с более общей точки зрения.

Понятие динамического программирования популяризировал Беллман [1957], а алгоритм 2.5 — известное приложение этого понятия опубликованное Годбоулом [1973] и Мураокой, Кукком [1973]. Приложением динамического программирования к распознаванию принадлежности бесконтекстному языку (упр. 2.34) независимо друг от друга занимались Касами [1965], Янгер [1967] и Кок. В работе Вагнера, Фишера [1974] содержится решение упр. 2.35.

Дальнейшую информацию о решении рекуррентных уравнений см. Лю [1968] или Слоун [1973].