[ДМК] Алгоритмы [Эриксон Дж.]

Английский вариант книги доступен свободно согласно Creative Commons Licence. Книга университетского уровня, возможно, для бакалавров, но выше первого курса. В отличие от книги Брасса, круг тем гораздо шире, само изложение проще, меньше математики, больше практики. Примеры на крайне схематичном псевдокоде вроде того, который у Кнута.
Перевёл содержание гуглом:

Спойлер: перевод содержания тут

Оглавление
Предисловие
Об этой книге. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . я
Предпосылки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . я
Дополнительные ссылки. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III
Об упражнениях. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV
Укради эту книгу! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . в
Благодарности. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ви
Осторожно, лектор! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VII
Содержание ix
0 Введение 1
0.1 Что такое алгоритм? . . . . . . . . . . . . . . . . . . . . . . . . . . 1
0.2 Умножение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Решетчатое умножение • Дублирование и посредничество • Циркуль и линейка
0.3 Распределение Конгресса. . . . . . . . . . . . . . . . . . . . . 8
0.4 Плохой пример. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
0.5 Описание алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Определение проблемы • Описание алгоритма
0.6 Анализ алгоритмов. . . . . . . . . . . . . . . . . . . . . . . . . . 14
Правильность • Время работы
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1 Рекурсия 21
1.1 Скидки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2 Упрощайте и делегируйте. . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3 Ханойская башня. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4 Сортировка слиянием. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Корректность • Анализ
1.5 Быстрая сортировка. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Корректность • Анализ
1.6 Шаблон. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.7 Деревья рекурсии. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
♥Игнорировать полы и потолки — это нормально, честное слово
1.8 ♥Выбор линейного времени. . . . . . . . . . . . . . . . . . . . . . . . . . 35
Быстрый выбор • Хорошие сводки • Анализ • Проверка работоспособности
1.9 Быстрое умножение. . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.10 Возведение в степень. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2 Возвращение 71
2.1 N ферзей. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.2 Деревья игр . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
2.3 Сумма подмножества. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Правильность • Анализ • Варианты
2.4 Общая схема. . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.5 Сегментация текста (Interpunctio Verborum). . . . . . . . . . . . . 80
Формулировка индекса • ♥Анализ • Варианты
2.6 Самая длинная возрастающая подпоследовательность . . . . . . . . . . . . . . . . . . . . 86
2.7 Самая длинная возрастающая подпоследовательность, дубль 2 . . . . . . . . . . . . . . . 89
2.8. Оптимальные бинарные деревья поиска. . . . . . . . . . . . . . . . . . . . . . 91
♥ Анализ
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3 Динамическое программирование 97
3.1 Matravritta. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Возврат может быть медленным • Запоминание: запоминать все • Динамично
Программирование: заполняйте намеренно • не запоминайте все после
Все
3.2 ♥Кроме того: еще более быстрые числа Фибоначчи. . . . . . . . . . . . . . . 103
Вау! Не так быстро!
3.3 Interpunctio Verborum Redux. . . . . . . . . . . . . . . . . . . . . . 105
3.4 Шаблон: умная рекурсия. . . . . . . . . . . . . . . . . . . . . 105
3.5 Предупреждение: жадность глупа. . . . . . . . . . . . . . . . . . . . . . . . 107
3.6 Самая длинная возрастающая подпоследовательность. . . . . . . . . . . . . . . . . . . . 109
Первое повторение: это следующее? • Второе повторение: что дальше?
3.7 Редактировать расстояние. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Рекурсивная структура • Повторение • Динамическое программирование
3.8 Сумма подмножества. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.9. Оптимальные бинарные деревья поиска. . . . . . . . . . . . . . . . . . . . . . 117
3.10 Динамическое программирование на деревьях. . . . . . . . . . . . . . . . . . . . 120
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4. Жадные алгоритмы 159
4.1 Хранение файлов на ленте. . . . . . . . . . . . . . . . . . . . . . . . . . . 159
4.2 Расписание занятий . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.3 Общая схема. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.4 Коды Хаффмана. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
4.5 Стабильное сопоставление. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
Несколько плохих идей • Бостонский пул и алгоритм Гейла-Шепли
Бег времени • Правильность • Оптимальность!
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
5 основных графовых алгоритмов 187
5.1 Введение и история. . . . . . . . . . . . . . . . . . . . . . . . 187
5.2 Основные определения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
5.3 Представления и примеры. . . . . . . . . . . . . . . . . . . . . 192
5.4 Структуры данных. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Списки смежности • Матрицы смежности • Сравнение
5.5 Поиск независимо от того, что в первую очередь . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Анализ
5.6 Важные варианты. . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
Стек: первый в глубину • Очередь: первый в ширину • Очередь с приоритетом: лучший
Сначала • Несвязные графы • Направленные графы
5.7 Сокращение графов: заполнение заливкой . . . . . . . . . . . . . . . . . . . . . . 205
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
6 Поиск в глубину 225
6.1 Предзаказ и постзаказ. . . . . . . . . . . . . . . . . . . . . . . . . 227
Классификация вершин и ребер
6.2 Обнаружение циклов. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
6.3 Топологическая сортировка. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
Неявная топологическая сортировка
6.4 Мемоизация и динамическое программирование. . . . . . . . . . . . . . 234
Динамическое программирование в Dags
6.5 Надежная связь. . . . . . . . . . . . . . . . . . . . . . . . . . . 237
6.6 Сильные компоненты в линейном времени. . . . . . . . . . . . . . . . . . 238
Алгоритм Косараджу и Шарира • ♥Алгоритм Тарьяна
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
7 минимальных остовных деревьев 257
7.1 Вес отдельных ребер . . . . . . . . . . . . . . . . . . . . . . . . . . 257
7.2 Единственный алгоритм минимального связующего дерева. . . . . . . . . . . 259
7.3 Алгоритм Борувки. . . . . . . . . . . . . . . . . . . . . . . . . . . 261
Это алгоритм MST, который вам нужен
7.4 Алгоритм Ярника («Прима»). . . . . . . . . . . . . . . . . . . . . . 263
♥Улучшение алгоритма Ярника
7.5 Алгоритм Крускала. . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
8 кратчайших путей 273
8.1. Деревья кратчайших путей. . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
8.2 ♥Отрицательные края. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
8.3 Единственный алгоритм SSSP. . . . . . . . . . . . . . . . . . . . . . . . 276
8.4 Невзвешенные графики: поиск в ширину . . . . . . . . . . . . . . 278
8.5 Направленные ациклические графы: поиск в глубину . . . . . . . . . . . . 282
8.6 Лучший-первый: алгоритм Дейкстры. . . . . . . . . . . . . . . . . . . . . 284
Нет отрицательных краев • ♥Отрицательные края
8.7 Расслабьте ВСЕ грани: Bellman-Ford. . . . . . . . . . . . . . . . . . 289
Улучшение Мура • Формулировка динамического программирования
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
9 кратчайших путей для всех пар 309
9.1 Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
9.2 Множество одиночных источников. . . . . . . . . . . . . . . . . . . . . . . . . . 310
9.3 Повторное взвешивание. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
9.4 Алгоритм Джонсона. . . . . . . . . . . . . . . . . . . . . . . . . . . 312
9.5 Динамическое программирование. . . . . . . . . . . . . . . . . . . . . . . . . 313
9.6 Разделяй и властвуй. . . . . . . . . . . . . . . . . . . . . . . . . . . 315
9.7 Забавное умножение матриц. . . . . . . . . . . . . . . . . . . . . . 316
9.8 (Клин-Рой-)Флойд-Уоршалл(-Ингерман) . . . . . . . . . . . . . . 318
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
10 Максимальные потоки и минимальные разрезы 327
10.1 Потоки. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
10.2 Разрезы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
10.3 Теорема Максфлоу-Минкат. . . . . . . . . . . . . . . . . . . . . 331
10.4. Алгоритм расширяющегося пути Форда и Фалкерсона. . . . . . . . . 334
♥Иррациональные возможности
10.5 Объединение и разделение потоков . . . . . . . . . . . . . . . . . 336
10.6 Алгоритмы Эдмондса и Карпа. . . . . . . . . . . . . . . . . . . . 340
Самые толстые пути увеличения • Кратчайшие пути увеличения
10.7 Дальнейший прогресс. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
11 Применение потоков и разрезов 353
11.1 Пути с непересекающимися краями . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
11.2 Вершинные пропускные способности и вершинно-непересекающиеся пути . . . . . . . . . . . . . 354
11.3 Двудольное сопоставление. . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
11.4 Выбор кортежа. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
задумчивость
11.5 Покрытия с непересекающимися путями . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
Минимальный набор преподавателей
11.6 Бейсбол Выбывание. . . . . . . . . . . . . . . . . . . . . . . . . . . 363
11.7 Выбор проекта. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
12 NP-сложность 379
12.1 Игра, в которой нельзя выиграть. . . . . . . . . . . . . . . . . . . . . . . . . . 379
12.2 P против NP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
12.3 NP-сложный, NP-легкий и NP-полный. . . . . . . . . . . . . . . . . . 382
12.4 ♥Формальные определения (HC SVNT DRACONES). . . . . . . . . . . . . 384
12.5 Скидки и сб. . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
12.6 3Sat (от CircuitSat). . . . . . . . . . . . . . . . . . . . . . . . . 388
12.7 Максимальный независимый набор (от 3Sat) . . . . . . . . . . . . . . . 390
12.8 Общая схема. . . . . . . . . . . . . . . . . . . . . . . . . . . 392
12.9 Клика и вершинное покрытие (из независимого набора) . . . . . . . . . 394
12.10 Раскраска графа (от 3сб) . . . . . . . . . . . . . . . . . . . . . . 395
12.11 Гамильтонов цикл. . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
От Vertex Cover • От 3Sat • Варианты и расширения
12.12 Сумма подмножества (из покрытия вершин) . . . . . . . . . . . . . . . . . . . . 402
Осторожно, редуктор!
12.13 Другие полезные NP-сложные задачи . . . . . . . . . . . . . . . . . . . . 404
12.14 Выбор правильной задачи . . . . . . . . . . . . . . . . . . . . . . 407
12.15 Легкомысленный пример из реальной жизни . . . . . . . . . . . . . . . . . . . . 408
12.16 ♥За Зеброй. . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
Полиномиальное пространство • Экспоненциальное время • Эксельсиор!
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
Индекс 442
Индекс людей 446
Индекс псевдокода 449
Кредиты изображений 451
Колофон 453