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].
