Добрая весть из прошлого

Геля Рузайкин
15.02.2001

Четверть века назад вышла книга «The design and analysis of computer algorithms», с переводом которой был хорошо знаком и отечественный читатель. Наряду с «Искусством программирования» Дональда Кнута и «Введением в теоретическое программирование» А.П. Ершова эта книга знаменовала становление computer science как дисциплины. Появление перевода недавнего переиздания книги Ахо, Хопкрофта и Ульмана явилось приятным сюрпризом и позволило познакомиться на современном уровне знаний с важнейшими разделами информационных технологий через призму структур данных и алгоритмов. Восприятие технологий осложнилось тем, что модельное представление систем переместилось с уровня понимания их состояния на уровень процессов, в них происходящих.

Появление перевода недавнего переиздания книги Ахо, Хопкрофта и Ульмана явилось приятным сюрпризом
В конечном счете все это привело к утрате интереса к формулировке задачи и выбору алгоритма на начальной стадии решения практически любой проблемы из области обработки информации. Разумеется, дело не только в том, что ИТ продвинулись весьма далеко вперед в реализации разнообразных процессов, что позволило не заниматься постановками задач, а лишь устанавливать программы, решающие известные классы задач. Однако сегодня все чаще ИТ-специалистам приходится иметь дело не с абстрактными API-интерфейсами, а с конкретными приложениями, следовательно, прежде всего, заниматься постановкой сложных задач и выбором подходящих алгоритмов.

Чем же привлекательна новая книга, выпущенная издательским домом «Вильямс»? Фактически в ней авторы излагают современное состояние материала первых шести глав предыдущего издания. Были опущены главы, посвященные быстрому преобразованию Фурье и его приложениям, арифметическим операциям над целыми числами и полиномами, алгоритмам идентификации, алгоритмам с полиномиальной сложностью и ряду других вопросов. При описании алгоритмов авторы отказались от использования машин Тьюринга и от языка упрощенного Алгола (Pidgin ALGOL). Теперь для представления алгоритмов и структур данных в книге использован Pascal и абстрактные формы.

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

Раздел книги, относящийся к алгоритмам, содержит материалы, посвященные направленным и ненаправленным графам. В него вошли различные алгоритмы работы с графами, в частности, поиска в глубину, нахождения минимального остова дерева, а также кратчайших путей и максимальных паросочетаний. Приведены основные алгоритмы внутренней сортировки: быстрая, пирамидальная, «карманная» и другие, а также описан алгоритм с линейным временем выполнения при нахождении порядковых статистик.

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

Позволю себе сделать замечание в адрес издателей. Досадно, что редактор не сделал дополнения к библиографии, в которую могли бы войти, например, источники последнего десятилетия, в том числе, и отечественные. И все же следует поблагодарить издателей за своевременную и очень полезную для многих книгу.