Стивен С. Скиена - Алгоритмы. Руководство по разработке

Steven S. Skiena

The Algorithm Design Manual
Тhird

Edition

~ Springer

Стивен С. Скиена

Алгоритмы
Руководство

по разработке
3-е издание

Санкт-Петербург
«БХВ-Петербург»

2022

УДК
ББК

681.3.06
32.973.26-018.2
С42

Скиена С. С.
С42

Алгоритмы. Руководство по разработке.
БХВ-Петербург,

2022. -

848

-

3-е изд.: Пер. с англ.

-

СПб.:

с.: ил.

ISBN 978-5-9775-6799-2
Книга является наиболее полным руководством по разработке эффективных ал­
горитмов. Первая часть книги содержит практические рекомендации по разработке
алгоритмов:

приводятся основные понятия, дается анализ алгоритмов, рассматри­

ваются типы структур данных, основные алгоритмы сортировки, операции обхода

графов и алгоритмы для работы со взвешенными графами, примеры использования
комбинаторного поиска, эвристических методов и динамического программиро­

вания. Вторая часть книги содержит обширный список литературы и каталог из

75

наиболее распространенных алгоритмических задач, для которых перечислены

существующие программные реализации.

В третьем издании расширен набор рандомизированных алгоритмов, алгорит­
мов хеширования,

100

аппроксимации

и квантовых вычислений. Добавлено более

новых задач, даны ссылки к реализациям на С, С++ и

Java.

Книгу можно использовать в качестве справочника по алгоритмам для про­

граммистов, исследователей и в качестве учебного пособия для студентов соответ­
ствующих специальностей.

ББК

УДК 681.3.06
32.973.26-018.2

First puЫished in English under the title
The Algorithm Design Manual
Ьу Steven S. Skiena, edition: 3
Copyright © The Editor(s) (ifapplicaЬle) and The Author(s), under exclusive license to
Springer Nature Switzerland AG, 2020
This edition has been translated and puЫished under licence from
Springer Nature Switzerland AG.
Springer Nature Switzerland AG takes no responsiЬility and shall not Ье made liaЫe for the accuracy ofthe translation.
Впервые опубликовано на английском языке под названием

The Algorithm Design Maпual
Steven S. Skiena, edition: 3
© Springer Nature Switzerland AG, 2020
Издание переведено и опубликовано по лицензии

Springer Nature Switzerland AG

ISBN 978-3-030-54255-9
ISBN 978-5-9775-6799-2

Springer Nature Switzerland AG.

не несет ответственности за точность перевода.

(англ.)
(рус.)

© Springer Nature Switzerland AG, 2020
© П~ревод на русский язык, оформление.
ООО "БХВ", 2022

ООО "БХВ-Петербург",

Оглавление

Предисловие ..... "" ... "" ... ""."" ... ""."" ... " ... "" ..... " ..... " ... "" ... " ... """ ...... " ....... " ..... """17

........................................................................................................................................ 17
Преподавателю ..........................................................................................................•................... 19
Благодарности ................................................................................................................................ 20
Ограничение ответственности ...................................................................................................... 21

Читателю

ЧАСТЬ 1. ПРАКТИЧЕСКАЯ РАЗРАБОТКА АЛГОРИТМОВ""""""""""""""23

Глава 1. Введение в разработку алгоритмов""""""""""""""""""""""""""""".25
1.1. Оптимизация маршрута робота ... " ........... " ..................... " ...... " ............................................ 26
1.2. Задача календарного планирования ...................................................................................... 30
1.3. Обоснование правильности алгоритмов ............................................................................... 33
1.3.1. Задачи и свойства ......................................................................................................... 34
1.3.2. Представление алгоритмов ......................................................................................... 35
1.3.3. Демонстрация неправильности алгоритма ................................................................. 35
ОСТАНОВКА ДЛЯ РАЗМЫШЛЕНИЙ: «Жадные» кинозвезды? ...................................................... 37
1.3.4. Индукция и рекурсия ................................................................................................... 38
ОСТАНОВКА ДЛЯ РАЗМЫШЛЕНИЙ: Правильность инкрементных алгоритмов ........................ 39
1.4. Моделирование задачи .......................................................................................................... .40
1.4 .1. Комбинаторные объекты ............................................................... " ........................... .41
1.4.2. Рекурсивные объекты ................................................................................................. .42
1.5. Доказательство от противного ............................................................................................. .44
1.6. Истории из жизни .................................................................................................................. .45
1.7. История из жизни. Моделирование проблемы ясновидения ............................................. .45
1.8. Прикидка --">