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

1.Мы добавили новые главы, посвященные деревьям ван Эмде Боаса и многопоточным алгоритмам, и убрали из приложений материал о матрицах.
2.Мы пересмотрели главу, посвященную рекуррентности, в сторону большего охвата метода “разделяй и властвуй” и ее первых двух разделов, посвященных применению этого метода для решения двух задач. Во втором разделе этой главы описан алгоритм Штрассена умножения матриц, которые был перенесен сюда из главы об операциях с матрицами.
3.Мы убрали две главы с достаточно редко изучаемым материалом: биномиальными пирамидами и сортирующими сетями. Одна из ключевых идей главы, посвященной сортирующим сетям, а именно 0-1 принцип, в этом издании находится в задаче 8.7 в виде леммы 0-1 сортировки для алгоритмов, работающих путем сравнения и обмена. Рассмотрение пирамид Фибоначчи больше не основывается на биномиальных пирамидах как на предшественницах пирамид Фибоначчи.
4.Мы пересмотрели подход к динамическому программированию и жадным алгоритмам. Динамическое программирование теперь иллюстрируется более интересной задачей разрезания стержня, чем задача сборочного конвейера во втором издании. Кроме того, мы сделали больший, чем во втором издании, акцент на технологии запоминания и ввели понятие графа подзадачи как способа улучшения определения времени работы алгоритма динамического программирования. В нашем вводном примере для жадных алгоритмов — в задаче о выборе процессов — мы переходим к жадным алгоритмам более прямым путем, чем во втором издании.
5.Способ удаления узла из бинарных деревьев поиска (включающих красно-чер-ные деревья) теперь гарантирует, что будет удален именно тот узел, который нужно удалить. В двух первых изданиях в некоторых случаях удалялся некоторый другой узел с перемещением его содержимого в узел, переданный процедуре удаления. При таком, новом, способе удаления узлов в случае, когда другие компоненты программы поддерживают указатели на узлы дерева, они не окажутся в ситуации с устаревшими указателями на удаленные из дерева узлы.
6.В материале, посвященном транспортным сетям, потоки теперь полностью базируются на ребрах, что представляет более интуитивно понятный подход, чем в первых двух изданиях.
7.Поскольку материал об основах работы с матрицами и алгоритм Штрассена перенесены в другие главы, глава, посвященная матричным операциям, стала существенно меньше по сравнению со вторым изданием.
8.Изменено рассмотрение алгоритма сравнения строк Кнута-Морриса-Пратта.
9.Исправлен ряд ошибок. Информация о большинстве из них (но не обо всех) была получена нами через наш сайт, посвященный второму изданию книги.
10.Идя навстречу многочисленным пожеланиям, мы заменили синтаксис нашего псевдокода. Теперь для указания присвоения мы используем “ = ” а для проверки на равенство — ’ как это делается в С, C++, Java и Python. Точнотак же мы удалили ключевые слова do и then и приняли в качестве символов начала комментария до окончания строки “//”. Кроме того, для указания атрибутов объектов используется запись с точкой. Но мы не зашли настолько далеко, чтобы сделать псевдокод объектно-ориентированным; он остался процедурным. Другими словами, вместо выполнения методов объектов мы просто вызываем процедуры, передавая им объекты в качестве параметров.
11.Мы добавили 100 новых упражнений и 28 новых задач. Мы также обновили и расширили библиографию.
12.Наконец мы прошлись по всей книге и переписали многие разделы, абзацы и отдельные предложения, делая изложение более понятным.

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

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

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

V Сложные структуры данных 517
Введение 518

18 В-деревья 521
18.1 Определение В-деревьев 525
18.2 Основные операции с В-деревьями 528
18.3 Удаление ключа из В-дерева 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

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

21.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

31 Теоретико-числовые алгоритмы 968
31.1 Элементарные понятия теории чисел 970
31.2 Наибольший общий делитель 976
31.3 Модульная арифметика 982
31.4 Решение модульных линейных уравнений 990
31.5 Китайская теорема об остатках 994
31.6 Степени элемента 997
31.7 Криптосистема с открытым ключом RSА 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

Б. Множества и прочие художества 1210
Б.1 Множества 1210
Б.2 Отношения 1215
Б.З Функции 1218
Б.4 Графы 1221
Б.5 Деревья 1226

В Комбинаторика и теория вероятности 1235
В.1 Основы комбинаторики 1235
В.2 Вероятность 1241
В.З Дискретные случайные величины 1248
В.4 Геометрическое и биномиальное распределения 1254
В.5 Хвосты биномиального распределения 1260

Г Матрицы 1269
Г.1 Матрицы и матричные операции 1269
Г.2 Основные свойства матриц 1274
Техническая литература 1282
Предметный указатель 1299