Алгоритмы: построение и анализ

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