Алгоритмы

Джефф Эриксон

Алгоритмы

Algorithms

Jeff Erickson

Москва 2023

Алгоритмы

Джефф Эриксон

УДК   004.021
ББК   32.973.05
Э77

Э77   Джефф Эриксон
Алгоритмы / пер. с англ. А. В. Снастина, П. Б. Иванова. – М.: ДМК Пресс, 
2023. – 526 с.: ил.

            ISBN 978-5-97060-981-1

В этом руководстве содержатся основные сведения об алгоритмах: 
анализируются различные типы алгоритмов, рассматриваются методы их построения (рекурсия, динамическое программирование и др.), 
приводятся практические примеры. В конце каждой главы приводятся 
упражнения, направленные на закрепление пройденного.
Для изучения материала требуется знание основ дискретной математики и методов доказательств, а также представление об основных 
вычислительных задачах и алгоритмах. Желателен практический опыт 
работы с языком программирования, поддерживающим косвенную 
адресацию и рекурсию.
Издание адресовано студентам и преподавателям технических вузов, 
а также тем, кто хочет изучить основы алгоритмизации.

 
 
 
 
 
 
 
 
    УДК  004.021

 
 
 
 
 
 
 
 
     ББК  32.973.05

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

ISBN 978-1-79264-483-2 (англ.)                       © Copyright Jeff Erickson, 2019
ISBN 978-5-97060-981-1 (рус.)                         © Оформление, перевод на русский язык,
 
                    издание, ДМК Пресс, 2023

Ким, Кей и Ханне
с любовью и восхищением.

И Ирин
с благодарностью за нарушение ее обещания.

Оглавление

Предисловие от издательства ............................................................................................12

Предисловие ..........................................................................................................................13

Об этой книге ......................................................................................................................................13
Обязательный минимум .................................................................................................................13
Дополнительные ссылки ................................................................................................................15
Упражнения в этой книге ...............................................................................................................17
Стащите эту книгу ..............................................................................................................................18
Благодарности ....................................................................................................................................19
Предостережение для преподавателя .....................................................................................20

Глава 0. Введение ..................................................................................................................22

0.1. Что такое алгоритм ...................................................................................................................22
0.2. Умножение ...................................................................................................................................24

Умножение методом решетки ........................................................................................................24
Удваивание и усреднение ................................................................................................................27
Циркуль и линейка ..............................................................................................................................29

0.3. Распределение мест в Конгрессе США .............................................................................30
0.4. Отрицательный пример ..........................................................................................................32
0.5. Описание алгоритмов .............................................................................................................33

Определение конкретной задачи .................................................................................................34
Описание алгоритма ..........................................................................................................................35

0.6. Анализ алгоритмов ...................................................................................................................37

Корректность .........................................................................................................................................37
Время выполнения ..............................................................................................................................37

Упражнения .........................................................................................................................................40

Глава 1. Рекурсия ...................................................................................................................45

1.1. Сведéние .......................................................................................................................................45
1.2. Упрощение и делегирование ...............................................................................................46
1.3. Ханойские башни ......................................................................................................................48
1.4. Сортировка слиянием..............................................................................................................51

Корректность .........................................................................................................................................52
Анализ ......................................................................................................................................................53

1.5. Быстрая сортировка .................................................................................................................54

Корректность .........................................................................................................................................55
Анализ ......................................................................................................................................................55

1.6. Шаблон ..........................................................................................................................................57
1.7. Рекурсивные деревья ..............................................................................................................57

♥Исключение нижних и верхних границ – это правильный подход,  
даю честное слово ...................................................................................................................60

Оглавление  7

♥1.8. Линейный алгоритм выбора .................................................................................................62

Алгоритм быстрого выбора .............................................................................................................62
Правильные опорные элементы ...................................................................................................63
Анализ ......................................................................................................................................................64
Проверка достоверности ..................................................................................................................66

1.9. Быстрое умножение .................................................................................................................67
1.10. Возведение в степень ...........................................................................................................70
Упражнения .........................................................................................................................................72

Ханойские башни ................................................................................................................................72
Рекурсивные деревья ........................................................................................................................77
Сортировка .............................................................................................................................................78
Выбор ........................................................................................................................................................82
Арифметика ............................................................................................................................................85
Массивы ...................................................................................................................................................89
Деревья ....................................................................................................................................................95

Глава 2. Поиск с возвратом ................................................................................................102

2.1. Задача об n ферзях ............................................................................................................... 103
2.2. Деревья игры ........................................................................................................................... 105
2.3. Задача о сумме подмножеств ........................................................................................... 108

Корректность .......................................................................................................................................109
Анализ ....................................................................................................................................................109
Варианты ...............................................................................................................................................110

2.4. Общий шаблон ........................................................................................................................ 111
2.5. Сегментация текста (Interpunctio Verborum) ............................................................... 113
2.6. Максимальная возрастающая подпоследовательность ......................................... 120
2.7. Максимальная возрастающая подпоследовательность, дубль 2 ........................ 124
2.8. Оптимальные двоичные деревья поиска ..................................................................... 126
Упражнения ...................................................................................................................................... 129

Глава 3. Динамическое программирование ...................................................................134

3.1. Mātrāv.rtta .................................................................................................................................. 134

Алгоритм поиска с возвратом может быть медленным .....................................................136
Мемоизация (запоминание): помнить все ...............................................................................137
Динамическое программирование: осмысленное заполнение .....................................138
И все же не следует запоминать все подряд .........................................................................140

♥3.2. Небольшое отступление: еще более быстрое определение  
чисел Фибоначчи ...................................................................................................................... 140

Стоп! Не так быстро ..........................................................................................................................142

3.3. Interpunctio verborum redux (И снова о пунктуации) ............................................. 143
3.4. Шаблон: интеллектуальная рекурсия ............................................................................ 144
3.5. Внимание: жадность – это глупость ................................................................................ 146
3.6. Максимальная возрастающая подпоследовательность ......................................... 147

Первое рекуррентное выражение: кто следующий? ..........................................................147

 Оглавление

Второе рекуррентное выражение: что дальше? ...................................................................149

3.7. Расстояние редактирования............................................................................................... 150

Рекурсивная структура ....................................................................................................................151
Рекуррентное выражение ..............................................................................................................152
Динамическое программирование ............................................................................................153

3.8. Задача о сумме подмножеств ........................................................................................... 155
3.9. Оптимальные двоичные деревья поиска ..................................................................... 157
3.10. Динамическое программирование для деревьев ................................................. 161
Упражнения ...................................................................................................................................... 163

Последовательности/Массивы .....................................................................................................164
Разделение последовательностей/массивов .........................................................................185
Деревья и поддеревья .....................................................................................................................197

Глава 4. Жадные алгоритмы ..............................................................................................205

4.1. Сохранение файлов на магнитной ленте ..................................................................... 205
4.2. Планирование учебных курсов ........................................................................................ 208
4.3. Общий шаблон ........................................................................................................................ 211
4.4. Коды Хаффмана ...................................................................................................................... 212
4.5. Задача о стабильных браках ............................................................................................. 218

Некоторые неудачные идеи ..........................................................................................................219
Алгоритмы Boston Pool и Гэйла–Шепли ...................................................................................221
Время выполнения ............................................................................................................................223
Корректность .......................................................................................................................................223
Оптимальность ....................................................................................................................................224

Упражнения ...................................................................................................................................... 225

Глава 5. Основные графовые алгоритмы ........................................................................238

5.1. Введение и историческая справка.................................................................................. 238
5.2. Основные определения ....................................................................................................... 242
5.3. Представления и примеры ................................................................................................. 244
5.4. Структуры данных .................................................................................................................. 248

Списки смежных вершин ................................................................................................................248
Матрицы смежности .........................................................................................................................249
Сравнение .............................................................................................................................................250

5.5. Поиск в любом направлении ............................................................................................ 252

Анализ ....................................................................................................................................................255

5.6. Важные варианты .................................................................................................................. 255

Стек: поиск в глубину .......................................................................................................................255
Очередь: поиск в ширину ...............................................................................................................255
Очередь с приоритетами: поиск по первому наилучшему совпадению .....................256
Несвязные графы ...............................................................................................................................257
Направленные графы.......................................................................................................................259

5.7. Редукция графа: сплошная заливка ................................................................................ 259

Оглавление  9

Упражнения ...................................................................................................................................... 261

Графы ......................................................................................................................................................261
Алгоритмы обхода .............................................................................................................................263
Сведéния ...............................................................................................................................................267

Глава 6. Поиск в глубину ....................................................................................................281

6.1. Обход в прямом и обратном порядке ........................................................................... 283

Классификация вершин и ребер .................................................................................................284

6.2. Обнаружение циклов ........................................................................................................... 287
6.3. Топологическая сортировка ............................................................................................... 288

Неявная топологическая сортировка ........................................................................................289

6.4. Мемоизация и динамическое программирование .................................................. 291

Динамическое программирование в НАГ ...............................................................................292

6.5. Сильная связность .................................................................................................................. 294
6.6. Сильные компоненты за линейное время ................................................................... 295

Алгоритм Косараджу–Шарира .....................................................................................................296

♥Алгоритм Тарьяна ...............................................................................................................................298

Упражнения ...................................................................................................................................... 301

Поиск в глубину, топологическая сортировка и сильные компоненты .......................301
Динамическое программирование ............................................................................................308

Глава 7. Минимальные остовные деревья ......................................................................316

7.1. Различные веса ребер .......................................................................................................... 317
7.2. Единственный алгоритм минимального остовного дерева .................................. 318
7.3. Алгоритм Борувки ................................................................................................................... 320

Это тот самый алгоритм МОД, который вам нужен ..............................................................322

7.4. Алгоритм Ярника (Прима) ................................................................................................... 323

♥Улучшенный алгоритм Ярника......................................................................................................324

7.5. Алгоритм Краскала ................................................................................................................ 326
Упражнения ...................................................................................................................................... 328

Глава 8. Кратчайшие пути ..................................................................................................334

8.1. Деревья кратчайшего пути ................................................................................................. 335

♥8.2. Отрицательные ребра .......................................................................................................... 336

8.3. Единственный алгоритм SSSP ........................................................................................... 337
8.4. Невзвешенные графы: поиск в ширину ........................................................................ 340
8.5. Направленный ациклический граф: поиск в глубину ............................................. 344
8.6. Поиск по первому наилучшему совпадению: алгоритм Дейкстры .................... 347

Отсутствие отрицательных ребер ...............................................................................................348

♥Отрицательные ребра ......................................................................................................................352

8.7. Ослабление напряжения всех ребер: алгоритм Беллмана–Форда ................... 354

Улучшение Мура .................................................................................................................................356
Формулировка с использованием динамического программирования .....................358

Упражнения ...................................................................................................................................... 361

 Оглавление

Глава 9. Кратчайшие пути между всеми парами вершин в графе .............................374

9.1. Введение .................................................................................................................................... 374
9.2. Множество отдельных источников ................................................................................. 375
9.3. Изменение весов .................................................................................................................... 376
9.4. Алгоритм Джонсона ............................................................................................................... 377
9.5. Динамическое программирование ................................................................................ 378
9.6. Разделяй и властвуй.............................................................................................................. 380
9.7. Странное умножение матриц ............................................................................................ 382
9.8. Алгоритм (Клини–Роя–)Флойда–Уоршелла(–Ингермана) .................................... 383
Упражнения ...................................................................................................................................... 386

Глава 10. Максимальные потоки и наименьшие разрезы ...........................................393

10.1. Потоки ...................................................................................................................................... 394
10.2. Разрезы .................................................................................................................................... 396
10.3. Теорема о максимальном потоке и наименьшем разрезе  
(Maxflow-Mincut) .................................................................................................................... 397

10.4. Алгоритм увеличивающего пути Форда и Фалкерсона ....................................... 400

♥Иррациональные пропускные способности ...........................................................................401

10.5. Объединения и разбиения потоков ............................................................................. 403
10.6. Алгоритмы Эдмондса и Карпа ........................................................................................ 407

Самые насыщенные увеличивающие пути .............................................................................407
Кратчайшие увеличивающие пути .............................................................................................409

10.7. Дальнейшее развитие ........................................................................................................ 411
Упражнения ...................................................................................................................................... 413

Глава 11. Приложения потоков и разрезов ....................................................................422

11.1. Реберно-непересекающиеся пути ................................................................................ 422
11.2. Пропускные способности вершин и вершинно-непересекающиеся пути ......423
11.3. Задача о паросочетании в двудольном графе ........................................................ 424
11.4. Выбор кортежа ..................................................................................................................... 427

Расписание экзаменов ....................................................................................................................428

11.5. Покрытия непересекающихся путей ........................................................................... 431

Набор минимального преподавательского состава ............................................................432

11.6. Алгоритм исключения для бейсбола ........................................................................... 434
11.7. Выбор проекта ...................................................................................................................... 437
Упражнения ...................................................................................................................................... 439

Глава 12. NP-трудность.......................................................................................................452

12.1. Игра, которую невозможно выиграть .......................................................................... 452
12.2. P против NP ............................................................................................................................ 454
12.3. NP-трудная, NP-легкая и NP-полная задача ............................................................. 456

♥12.4. Формальные определения (HC SVNT DRACONES – Тут [обитают]  
драконы) ....................................................................................................................................... 458

12.5. Редукции и задача Sat ....................................................................................................... 460