1626435697-9d9ede204f9baad60159c2d6531787c7 (Хопкрофт, Ульман 1979 - Построение и анализ вычислительных алгоритмов)

А. АХО, Дж, ХОПКРОфТ, Дж. УЛЬМАН ПОСТРОЕНИЕ И АНАЛИЗ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ Перевод с английского А. О. Слисенко под редакцией 1О. В. Матиясевича ИЗДАТЕЛЬСТВО <сМИРэ МОСКВА 1979 УДК 519.882.! + 681.142.2 Редакция литературы ло математическим наукам 2 405 000 ООО йр 1974, Адд!зоп-Ъгез1еу Рнй!!гй!пй Согпрапу © Перевод на русский язык, «Мирт !979 20205-023 А 041 1011 79 23-™ В монографии с единых позиций излагаются результаты теоретических и прикладных исследований по построению быстрых алгоритмов и доказательству их отсутствия. Рассмотрены задачи перебора, упорядочения массивов данных, умножения чисел, умножения матриц; обсуждаются алгоритмы на графах. Многие результаты ранее были рассеяны в труднодоступных источвиках и в монографнчесхом виде публикуются впервые.

Книга рассчитана на специалистов по современному програм. мированню, разработчиков вычислительных систем и алгоритмов; она может быть использована кан учебное пособие студентами и аспирантами, специализирующимися в области вычислительной математики. аль доминАтОРы В ОРиентиРОВАнных ГРАФАХ торая строится в п. 1, помогает эффективно применить лемму 5.!4. С другой стороны, ие надо полностью выполнять и.

1 до устранения поперечных ребер, поскольку каждое устраненное поперечное ребро становится прямым. На самом деле мы должны добавить шаги обработки поперечных ребер к тому прохождению в порядке, обратном к прямому, которое было описано применительно к прямым ребрам. Заметим, что в п. 1 требуется (из-за применения леммы 5.13), чтобы в определенные моменты времени в определенные узлы не входили поперечные ребра.

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

Вначале для каждого поперечного ребра (и, в) вычисляем общего предка узлов о и Гв с наибольшим номером. Каждому узлу о припишем множество 5[о! упорядоченных пар (и, Гп), где (и, Гв), и)ГВ, представляет запрос о предке узлов и и Гп с наибольшим номером. Вначале Цо[= =((о, Гп)! есть поперечное ребро (о, гв), п)ГВ). Во время прохождения дереве о в соответствии с процедурой в п.

! делаем следующее. 1) При прохождении древесного реора (о, Гп), о ГВ, удаляем из Цо! каждую пару (х, у), в которой у)иА Узел о — общий предок с наибольшим номером узлов х и у. 2) По возвращении к и по ребру (о, Гп) остовного дерева заме- НяЕМ 1,[О! На О[О! 0 а.[ГП!. Вычисление предков с наибольшим номером можно осущест. вить не более чем за 0(еб(е)) шагов '), где а — число ребер графа 6; для этого можно воспользоваться обобщением М!!а-алгоритма, работающим в свободном режиме, о котором упоминается в упр. 4.21. Обработка поперечных ребер состоит в том, что они преобразуются в прямые по лемме 5.14.

Процесс преобразования поперечных ребер в прямые надо выполнять во время обработки прямых ребер. Каждому узлу о ставим в соответствие некоторое множество С[о! составных ребер. Вначале С[о! ((о, (й„..., !Г„))[(о, Ь~) — поперечное ребро при 1(1(ВГ). По возвращении в узел о вдоль древесного ребра (о, Гп) совершаем помимо шагов, связанных с обработкой прямых ребер, следующие шаги.

1) Заменяем С[о! на С[о! ОС[в!. 2) Удаляем каждое поперечное ребро (х, у), для которого о— предок с наибольшим номером узлов х и у, из составного ребра, где оно представлено в данный момент. Если 1 — начало этого составного ребра, заменяем поперечное ребро (х, у) а) См.

прамечааае аа стр. 202. — Прпа. Рад, ПРВДИСЛОВИБ К РУССКОМУ ПБРВВОДУ отражающие публикации тех же результатов в более доступных изданиях. Книга написана живым языком, близким тому, который ис зуется в разговоре с коллегой — специалистом по данному вопросу. Это имеет и свои негативные стороны: авторы иногда отступают, не оговаривая специально, от принятых ранее соглашений, а также употребляют некоторые обозначения без пояснений. У читателя, активно изучающего зту книгу, такие места не должны вызывать трудностей, и они никак не комментируются. Здесь мы разъясним лишь два обозначения: знак Р наряду с ° и х используется в качестве знака умножения; О' обозначает а-кратную конкатенацию символа О. Ю.

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

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

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

В гл. 2 вводятся основные структуры данных и техника программирования, часто применяемые в эффективных алгоритмах. Оиа охватывает списки, магазины, очереди, деревья и графы. Приведено подробное объяснение рекурсии, приема "разделяй и властвуй" и динамического программирования вместе с примерами их применения. ПРЕДИСЛОВИЕ В гл. 3 — 9 указаны Разнообразные области, в которых может применяться основополагающая техника гл. 2. В этих главах мы уделяем главное внимание построению алгоритмов, асимптотическн наилучших среди известных, По этой причине некоторые нз рассматриваемых алгоритмов хороши лишь для входных данных, длина которых много больше, чем у обычно встречающихся на практике.

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

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

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

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