Содержание
Предисловие 14
I Основы 23
Введение 24
1 Роль алгоритмов в вычислениях 26
1.1 Что такое алгоритмы 26
1.2 Алгоритмы как технология 32
2 Приступаем к изучению 38
2.1 Сортировка вставкой 38
2.2 Анализ алгоритмов 45
2.3 Разработка алгоритмов 52
3 Рост функций 67
3.1 Асимптотические обозначения 68
3.2 Стандартные обозначения и часто встречающиеся функции 78
4 Разделяй и властвуй 90
4.1 Задача поиска максимального подмассива 93
4.2 Алгоритм Штрассена для умножения матриц 100
4.3 Метод подстановки решения рекуррентных соотношений 108
4.4 Метод деревьев рекурсии 113
4.5 Основной метод 119
⋆ 4.6 Доказательство основной теоремы 123
5 Вероятностный анализ и рандомизированные алгоритмы 140
5.1 Задача о найме 140
5.2 Индикаторная случайная величина 144
5.3 Рандомизированные алгоритмы 148
⋆ 5.4 Вероятностный анализ и дальнейшее применение индикаторных
случайных величин 156
Стр. 7
8 Содержание
II Сортировка и порядковая статистика 173
Введение 174
6 Пирамидальная сортировка 179
6.1 Пирамиды 179
6.2 Поддержка свойства пирамиды 182
6.3 Построение пирамиды 185
6.4 Алгоритм пирамидальной сортировки 188
6.5 Очереди с приоритетами 190
7 Быстрая сортировка 198
7.1 Описание быстрой сортировки 198
7.2 Производительность быстрой сортировки 202
7.3 Рандомизированная быстрая сортировка 207
7.4 Анализ быстрой сортировки 208
8 Сортировка за линейное время 220
8.1 Нижние границы для алгоритмов сортировки 220
8.2 Сортировка подсчетом 223
8.3 Поразрядная сортировка 226
8.4 Карманная сортировка 230
9 Медианы и порядковые статистики 243
9.1 Минимум и максимум 244
9.2 Выбор в течение линейного ожидаемого времени 245
9.3 Алгоритм выбора с линейным временем работы в наихудшем случае
250
III Структуры данных 259
Введение 260
10 Элементарные структуры данных 264
10.1 Стеки и очереди 264
10.2 Связанные списки 268
10.3 Реализация указателей и объектов 273
10.4 Представление корневых деревьев 277
11 Хеширование и хеш-таблицы 285
11.1 Таблицы с прямой адресацией 286
11.2 Хеш-таблицы 288
11.3 Хеш-функции 294
11.4 Открытая адресация 302
⋆ 11.5 Идеальное хеширование 310
Стр. 8
Содержание 9
12 Бинарные деревья поиска 319
12.1 Что такое бинарное дерево поиска 319
12.2 Работа с бинарным деревом поиска 322
12.3 Вставка и удаление 327
⋆ 12.4 Случайное построение бинарных деревьев поиска 332
13 Красно-черные деревья 341
13.1 Свойства красно-черных деревьев 341
13.2 Повороты 345
13.3 Вставка 348
13.4 Удаление 356
14 Расширение структур данных 372
14.1 Динамические порядковые статистики 372
14.2 Расширение структур данных 378
14.3 Деревья отрезков 381
IV Усовершенствованные методы разработки и анализа 389
Введение 390
15 Динамическое программирование 392
15.1 Разрезание стержня 393
15.2 Перемножение цепочки матриц 403
15.3 Элементы динамического программирования 412
15.4 Наидлиннейшая общая подпоследовательность 424
15.5 Оптимальные бинарные деревья поиска 431
16 Жадные алгоритмы 448
16.1 Задача о выборе процессов 449
16.2 Элементы жадной стратегии 457
16.3 Коды Хаффмана 463
⋆ 16.4 Матроиды и жадные методы 471
⋆ 16.5 Планирование заданий как матроид 479
17 Амортизационный анализ 487
17.1 Групповой анализ 488
17.2 Метод бухгалтерского учета 492
17.3 Метод потенциалов 495
17.4 Динамические таблицы 500
Стр. 9
10 Содержание
V Сложные структуры данных 517
Введение 518
18 B-деревья 521
18.1 Определение B-деревьев 525
18.2 Основные операции с B-деревьями 528
18.3 Удаление ключа из B-дерева 536
19 Фибоначчиевы пирамиды 542
19.1 Структура фибоначчиевых пирамид 544
19.2 Операции над объединяемыми пирамидами 547
19.3 Уменьшение ключа и удаление узла 555
19.4 Оценка максимальной степени 559
20 Деревья ван Эмде Боаса 568
20.1 Предварительные подходы 569
20.2 Рекурсивная структура 573
20.3 Дерево ван Эмде Боаса 582
21 Структуры данных для непересекающихся множеств 597
21.1 Операции над непересекающимися множествами 597
21.2 Представление непересекающихся множеств
с помощью связанных списков 600
21.3 Леса непересекающихся множеств 604
⋆ 21.4 Анализ объединения по рангу со сжатием пути 608
VI Алгоритмы для работы с графами 623
Введение 624
22 Элементарные алгоритмы для работы с графами 626
22.1 Представление графов 626
22.2 Поиск в ширину 630
22.3 Поиск в глубину 639
22.4 Топологическая сортировка 649
22.5 Сильно связные компоненты 652
23 Минимальные остовные деревья 661
23.1 Выращивание минимального остовного дерева 662
23.2 Алгоритмы Крускала и Прима 667
24 Кратчайшие пути из одной вершины 680
24.1 Алгоритм Беллмана–Форда 688
24.2 Кратчайшие пути из одной вершины в ориентированных
ациклических графах 693
24.3 Алгоритм Дейкстры 696
24.4 Разностные ограничения и кратчайшие пути 702
24.5 Доказательства свойств кратчайших путей 709
Стр. 10
Содержание 11
25 Кратчайшие пути между всеми парами вершин 722
25.1 Задача о кратчайших путях и умножение матриц 724
25.2 Алгоритм Флойда–Уоршелла 731
25.3 Алгоритм Джонсона для разреженных графов 738
26 Задача о максимальном потоке 747
26.1 Транспортные сети 748
26.2 Метод Форда–Фалкерсона 753
26.3 Максимальное паросочетание 771
⋆ 26.4 Алгоритмы проталкивания предпотока 775
⋆ 26.5 Алгоритм “поднять-в-начало” 788
VII Избранные темы 807
Введение 808
27 Многопоточные алгоритмы 811
27.1 Основы динамической многопоточности 813
27.2 Многопоточное умножение матриц 832
27.3 Многопоточная сортировка слиянием 836
28 Работа с матрицами 852
28.1 Решение систем линейных уравнений 852
28.2 Обращение матриц 866
28.3 Симметричные положительно определенные матрицы
и метод наименьших квадратов 872
29 Линейное программирование 883
29.1 Стандартная и каноническая формы задачи линейного
программирования 891
29.2 Формулировка задач в виде задач линейного программирования 899
29.3 Симплекс-алгоритм 905
29.4 Двойственность 921
29.5 Начальное базисное допустимое решение 927
30 Полиномы и быстрое преобразование Фурье 940
30.1 Представление полиномов 942
30.2 ДПФ и БПФ 949
30.3 Эффективные реализации БПФ 957
Стр. 11
12 Содержание
31 Теоретико-числовые алгоритмы 968
31.1 Элементарные понятия теории чисел 970
31.2 Наибольший общий делитель 976
31.3 Модульная арифметика 982
31.4 Решение модульных линейных уравнений 990
31.5 Китайская теорема об остатках 994
31.6 Степени элемента 997
31.7 Криптосистема с открытым ключом RSA 1002
⋆ 31.8 Проверка простоты 1009
⋆ 31.9 Целочисленное разложение 1021
32 Поиск подстрок 1031
32.1 Простейший алгоритм поиска подстрок 1034
32.2 Алгоритм Рабина–Карпа 1036
32.3 Поиск подстрок с помощью конечных автоматов 1041
⋆ 32.4 Алгоритм Кнута–Морриса–Пратта 1048
33 Вычислительная геометрия 1060
33.1 Свойства отрезков 1061
33.2 Определение наличия пересекающихся отрезков 1068
33.3 Поиск выпуклой оболочки 1075
33.4 Поиск пары ближайших точек 1086
34 NP-полнота 1096
34.1 Полиномиальное время 1102
34.2 Проверка за полиномиальное время 1110
34.3 NP-полнота и приводимость 1115
34.4 Доказательства NP-полноты 1127
34.5 NP-полные задачи 1136
35 Приближенные алгоритмы 1157
35.1 Задача о вершинном покрытии 1159
35.2 Задача о коммивояжере 1163
35.3 Задача о покрытии множества 1169
35.4 Рандомизация и линейное программирование 1175
35.5 Задача о сумме подмножества 1180
VIII Приложения: математические основы 1195
Введение 1196
А Суммы и ряды 1198
А.1 Суммы и их свойства 1198
А.2 Оценки сумм 1202
Стр. 12
Содержание 13
Б Множества и прочие художества 1210
Б.1 Множества 1210
Б.2 Отношения 1215
Б.3 Функции 1218
Б.4 Графы 1221
Б.5 Деревья 1226
В Комбинаторика и теория вероятности 1235
В.1 Основы комбинаторики 1235
В.2 Вероятность 1241
В.3 Дискретные случайные величины 1248
В.4 Геометрическое и биномиальное распределения 1254
⋆ В.5 Хвосты биномиального распределения 1260
Г Матрицы 1269
Г.1 Матрицы и матричные операции 1269
Г.2 Основные свойства матриц 1274
Литература 1282
Предметный указатель 1299
Стр. 13