ПРЕДИСЛОВИЕ

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

Содержание книги

Для анализа работы алгоритма нужна какая-нибудь модель вычислительной машины. Наша книга начинается с определения нескольких таких моделей, достаточно простых для анализа, но в то же время точно отражающих основные черты реальных машин. Эти модели включают машину с произвольным доступом к памяти, машину с произвольным доступом к памяти и хранимой программой, а также некоторые их разновидности. Машина Тьюринга вводится для доказательства экспоненциальных нижних оценок эффективности алгоритмов в гл. 10 и 11. Поскольку общая тенденция в разработке программ состоит в отходе от использования машинно-ориентированных языков, вводится язык высокого уровня, называемый Упрощенным Алголом (Pidgin ALGOL), как основное средство для описания алгоритмов. Сложность программы на Упрощенном Алголе связывается с соответствующей моделью машины.

В гл. 2 вводятся основные структуры данных и техника программирования, часто применяемые в эффективных алгоритмах. Она охватывает списки, магазины, очереди, деревья и графы. Приведено подробное объяснение рекурсии, приема "разделяй и властвуй" и динамического программирования вместе с примерами их применения.

В гл 3-9 указаны разнообразные области, в которых может применяться основополагающая техника гл. 2. В этих главах мы уделяем главное внимание построению алгоритмов, асимптотически наилучших среди известных. По этой причине некоторые из рассматриваемых алгоритмов хороши лишь для входных данных, длина которых много больше, чем у обычно встречающихся на практике. В частности, это относится к некоторым алгоритмам умножения матриц из гл. 6, к принадлежащему Шёнхаге и Штрассену алгоритму умножения целых чисел из гл. 7 и некоторым алгоритмам из гл. 8, работающим с полиномами и целыми числами.

С другой стороны, большая часть алгоритмов сортировки из гл. 3, поиска из гл. 4, алгоритмов на графах из гл. 5, быстрое преобразование Фурье из гл. 7 и алгоритмы идентификации подслов из гл. 9 используются широко, поскольку размеры входов, на которых эти алгоритмы эффективны, достаточно малы, чтобы встретить их во многих практических ситуациях.

В гл. 10—12 обсуждаются нижние границы сложности вычислений. Подлинная вычислительная сложность задачи интересна вообще — и для разработки программ, и для понимания природы вычисления. В гл. 10 изучается важный класс задач — так называемые NP-полные задачи. Все задачи из этого класса эквивалентны по вычислительной сложности в том смысле, что если одна из них имеет эффективное (с полиномиально ограниченным временем) решение, то все они имеют эффективные решения. Так как этот класс содержит много практически важных и долго изучавшихся задач, таких, как задача целочисленного программирования или задача о коммивояжере, то есть основания подозревать, что ни одну из задач этого класса нельзя решить эффективно. Поэтому если разработчик программы знает, что задача, для которой он пытается найти эффективный алгоритм, принадлежит этому классу, то ему, возможно, надо удовлетвориться попытками эвристического подхода к ней. Несмотря на огромное число эмпирических свидетельств в пользу противоположного, до сих пор открыт вопрос, допускают ли NP-полные задачи эффективные решения.

В гл. 11 описаны конкретные задачи, для которых можно доказать, что эффективных алгоритмов для них действительно нет. Материал гл. 10 и 11 существенно опирается на понятие машины Тьюринга, введенное в разд. 1.6 и 1.7.

В последней главе мы устанавливаем связь трудности вычисления с понятием линейной независимости в векторных пространствах. Материал этой главы дает технику доказательства нижних оценок для гораздо более простых задач, чем рассмотренные в гл. 10 и 11.

О пользовании книгой

Эта книга задумана как начальный курс по разработке и анализу алгоритмов. Основной упор сделан на идеи и простоту понимания, а не на проработку деталей реализации или программистские трюки. Часто вместо длинных утомительных доказательств даются лишь неформальные интуитивные объяснения.

Книга замкнута в себе и не предполагает специальной подготовки ни по математике, ни по языкам программирования. Однако желательна определенная зрелость в навыках обращения с математическими понятиями, а также некоторое знакомство с языками программирования высокого уровня, такими, как Фортран или Алгол. Для полного понимания гл. 6—8 и 12 нужны некоторые познания в линейной алгебре.

Эта книга использовалась как основа для спецкурсов по разработке алгоритмов. За один семестр изучался материал, покрывающий большую часть гл. 1—5, 9 и 10 вместе с беглым обзором тематики остальных глав. Во вводных курсах основное внимание уделялось материалу из гл. 1—5, но разд. 1.6, 1.7, 4.13, 5.11 и теорема 4.5 обычно не изучались. Книгу можно также использовать для более глубоких спецкурсов, делая упор на теорию алгоритмов. Основой для этого могли бы служить гл. 6—12.

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

Благодарности

Материал книги основан на набросках лекций для курсов, читавшихся авторами в Корнеллском и Принстонском университетах и в Стивенсонском технологическом институте. Авторы хотели бы поблагодарить многих людей, которые критически прочитали различные части рукописи и внесли полезные предложения. Особенно мы хотели бы поблагодарить Келлога Бута, Стэна Брауна, Стива Чена, Алена Сайфера, Арча Дейвиса, Майка Фишера, Хейнию Гаевску, Майка Гэри, Юдая Гупту, Майка Харрисона, Матта Хекта, Гарри Ханта, Дейва Джонсона, Марка Каплана, Дона Джонсона, Стива Джонсона, Брайана Кернигана, Дона Кнута, Ричарда Лэднера, Аниту Ла-Саль, Дуга Мак-Илроя, Альберта Мейера, Кристоса Пападимитриу, Билла Плогера, Джона Сэвиджа, Ховарда Зигеля, Кена Стейглица, Лэрри Стокмейера, Тома Жимански и Теодора Ена.

Мы выражаем особую благодарность Джеме Карневейл, Полине Камерон, Ханне Крессе, Эдит Персер и Руфи Сузуки за быструю и качественную перепечатку рукописи.

Авторы также благодарны фирме Bell Laboratories и университетам Корнеллскому, Принстонскому и Калифорнийскому (отделение в Беркли) за предоставленные возможности для подготовки рукописи.

Июнь 1974 Альфред Ахо, Джон Хопкрофт Джефри Ульман