Все новости от 21 декабря 2006 г.

Красно-черные деревья и NP-полные задачи

Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клиффорд.Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. М.: Издательский дом “Вильямс”, 2005. — 1296 с. : ил.

Этот объемный труд хорошо подходит на роль настольной книги профессионального программиста, столь подробно изложены в нем алгоритмы, востребованные в практике каждого разработчика. По алгоритмам и структурам данных сегодня выходит немало книг, однако они подчас излишне ориентированы на конкретные языки и технологии программирования, что лишает их универсальности и глубины. А данное издание предлагает не только описание множества алгоритмов и их исходные тексты на псевдоязыке, напоминающем Паскаль, но и уделяет существенное внимание математическому обоснованию, а также методам разработки алгоритмов и их анализа, под которым подразумевается прогноз требуемых для выполнения ресурсов. Текст сопровождается немалым числом наглядных схем и диаграмм, а также сотнями упражнений. Стоит отметить также аккуратность и ясность перевода.

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

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

Более сложные структуры данных обычно применяются в системах с периферийной памятью с прямым, но не очень быстрым доступом — например, в СУБД, использующих жесткие диски. Такие структуры рассматриваются в пятой части и включают B-деревья (сбалансированные деревья поиска), биномиальные и фибоначчиевы пирамиды, характеризующиеся невысоким временем обращения к содержимому и гарантированным временем выполнения различных операций обработки данных.

Теории графов посвящена шестая часть. Алгоритмы охватывают программное построение и обход графа и его поддеревьев, всевозможные способы нахождения кратчайшего пути. Графы нередко применяются для представления транспортных сетей (от трубопроводных до компьютерных), для оптимизации которых используются алгоритмы решения задачи о максимальном потоке.

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

В нескольких главах обсуждается тема NP-полных задач (сложных и трудноразрешимых). К ним относят задачи, ответ на которые не находится за полиномиальное время. Например, поиск кратчайшего пути на графе можно выполнить немалым числом быстрых алгоритмов, а вот поиск длиннейшего пути считается уже трудноразрешимым.

Поиск ответов для множества NP-полных задач ведется с 1972 г., однако пока ни для одной из них не найдено оптимальное решение. Но если хотя бы для одной NP-полной проблемы удастся разработать полиномиальный алгоритм, то такая возможность станет теоретически вероятной и для других подобных проблем, что приведет к перевороту в мире ИТ. Перед молодыми учеными здесь открывается огромное поле деятельности, так как алгоритмы, выполняющиеся за разумное время, позволят найти ответы на крайне сложные вопросы оптимизации и принятия решений.