Language: Russian
Pages: 944
Оглавление......Page 5
Предисловие......Page 12
1.1. Алгоритмы......Page 17
1.2. Анализ результатов......Page 21
1.3.1. Принцип "разделяй и властвуй"......Page 25
1.3.2. Анализ алгоритмов типа "разделяй и властвуй"......Page 27
1.4. О пользе быстрых алгоритмов......Page 28
I. Математические основы анализа алгоритмов......Page 32
Введение......Page 33
2.1. Ассимптотические обозначения......Page 34
2.2. Стандартные функции и обозначения......Page 39
3.1. Суммы и их свойства......Page 47
3.2. Оценки сумм......Page 50
4 Рекуррентные соотношения......Page 57
4.1. Метод подстановки......Page 58
4.2. Метод итераций......Page 61
4.3. Общий рецепт......Page 64
4.4.1. Случай натуральных степеней......Page 66
4.4.2. Целые приближения сверху и снизу......Page 70
5.1. Множества......Page 76
5.2. Отношения......Page 81
5.3. Функции......Page 83
5.4. Графы......Page 86
5.5.1. Деревья без выделенного корня......Page 90
5.5.2. Деревья с корнем. Ориентированные деревья......Page 92
5.5.3. Двоичные деревья. Позиционные деревья......Page 94
6.1. Подсчет количеств......Page 99
6.2. Вероятность......Page 104
6.3. Дискретные случайные величины......Page 110
6.4. Геометрическое и биноминальное распределение......Page 114
6.5. Хвосты биноминального распределения......Page 119
6.6. Вероятностный анализ......Page 123
6.6.1. Парадокс дня рождения......Page 124
6.6.2. Шары и урны......Page 125
6.6.3. Участки повторяющихся исходов......Page 126
II. Сортировка и порядковые статистики......Page 131
Введение......Page 132
7.1. Кучи......Page 135
7.2. Сохранение основного свойства кучи......Page 137
7.3. Построение кучи......Page 139
7.4. Алгоритм сортировки с помощью кучи......Page 142
7.5. Очереди с приоритетами......Page 144
8.1. Описание быстрой сортировки......Page 148
8.2. Работа быстрой сортировки......Page 151
8.3. Вероятностные алгоритмы быстрой сортировки......Page 154
8.4. Анализ быстрой сортировки......Page 156
8.4.2. Анализ среднего времени работы......Page 157
9.1. Нижние оценки для сортировки......Page 165
9.2. Сортировка подсчетом......Page 168
9.3. Цифровая сортировка......Page 170
9.4. Сортировка вычерпыванием......Page 172
10. Медианы и порядковые сортировки......Page 177
10.1. Минимум и максимум......Page 178
10.2. Выбор за линейное в среднем время......Page 179
10.3. Выбор за линейное в хуждшем случае время......Page 181
III Структуры данных......Page 187
Введение......Page 188
11.1. Стеки и очереди......Page 189
11.2. Связанные списки......Page 193
11.3. Реализация указателей и записей с несколькими полями......Page 197
11.4. Представление корневых деревьев......Page 202
12.1. Прямая адресация......Page 208
12.2. Хеш-таблицы......Page 210
12.3. Хеш-функции......Page 215
12.3.1. Деление с остатком......Page 216
12.3.2. Умножение......Page 217
12.3.3. Универсальное хеширование......Page 218
12.4. Открытая адресация......Page 221
13.1. Что такое двоичное дерево поиска......Page 231
13.2. Поиск в двоичном дереве......Page 233
13.3. Добавление и удаление элемента......Page 237
13.4. Случайные двоичные деревья поиска......Page 240
14.1. Свойства красно-черных деревьев......Page 249
14.2. Вращения......Page 251
14.3. Добавление вершины......Page 253
14.4. Удаление......Page 257
15.1. Динамические порядковые статистики......Page 266
15.2. Общая схема работы с дополнительной информацией......Page 271
15.2. Деревья промежутков......Page 273
IV Методы построения и анализа алгоритмов......Page 280
Введение......Page 281
16. Динамическое программирование......Page 282
16.1. Перемножение нескольких матриц......Page 283
16.2. Когда применимо динамическое программирование......Page 290
16.3. Наибольшая общая последовательность......Page 294
16.4. Оптимальная триангуляция многоугольника......Page 299
17.1. Задача о выборе заявок......Page 307
17.2. Когда применим жадный алгоритм......Page 311
17.3. Коды Хаффмена......Page 314
17.4.1. Матроиды......Page 321
17.4.2. Жадные алгоритмы для взвешенного матроида......Page 323
17.5. Задача о расписании......Page 326
18. Амортизационный анализ......Page 331
18.1. Метод группировки......Page 332
18.2. Метод предоплаты......Page 335
18.3. Метод потенциалов......Page 337
18.4.1. Расширение таблицы......Page 340
18.4.2. Расширение и сокращение таблицы......Page 343
V Более сложные структуры данных......Page 349
Введение......Page 350
19. Б-деревья......Page 352
19.1. Определение Б-дерева......Page 354
19.2. Основные операции с Б-деревом......Page 357
19.3. Удаление элемента из Б-дерева......Page 364
20. Биноминальные кучи......Page 369
20.1.1. Биноминальные деревья......Page 370
20.1.2. Биноминальные кучи......Page 372
20.2. Операции с биноминальными кучами......Page 374
21. Фибоначчиевы кучи......Page 388
21.1. Строение фибоначчиевой кучи......Page 389
21.2. Операции, предусмотренные для сливаемых куч......Page 391
21.3. Уменьшение ключа и удаление вершины......Page 399
21.4. Оценка максимальной степени......Page 402
22.1. Операциис непересекающимися множествами......Page 407
22.2. Реализация с помощью списков......Page 410
23.3. Лес непересекающихся множеств......Page 413
22.4. Объединение по рангам со сжатием путей: анализ......Page 417
VI Алгоритмы на графах......Page 427
Введение......Page 428
23.1. Представление графов......Page 429
23.2. Поиск в ширину......Page 432
23.3 Поиск в глубину......Page 439
24.4. Топологическая сортировка......Page 446
23.5. Сильно связанные компоненты......Page 449
24. Минимальные покрывающие деревья......Page 458
24.1. Построение минимального покрывающего дерева......Page 459
24.2. Алгоритмы Крускала и Прима......Page 463
25. Кратчайшие пути из одной вершины......Page 472
25.1. Кратчайшие пути и релаксация......Page 476
25.2. Алгоритм Дейкстры......Page 482
25.3. Алгоритм Беллмана-Форда......Page 487
25.4. Кратчайшие пути в ациклическом ориентированном графе......Page 490
25.5. Ограничения на разности и кратчайшие пути......Page 492
26. Кратчайшие пути для всех пар вершин......Page 502
26.1. Кратчайшие пути и умножение матриц......Page 504
26.2. Алгоритм Флойда-Уоршолла......Page 510
26.3. Алгоритм Джонсона для разреженных графов......Page 516
26.4. Замкнутые полукольца: общая схема для задач о путях......Page 520
27. Максимальный поток......Page 528
27.1. Потоки в сетях......Page 529
27.2. Метод Форда-Фалкерсона......Page 535
27.3. Максимальное паросочетание в двудольном графе......Page 545
27.4. Алгоритм "проталкивания предтока"......Page 549
27.5. Алгоритм "поднять-и-в-начало"......Page 557
VII Дополнительные главы......Page 572
Введение......Page 573
28.1. Сети компараторов......Page 576
28.2. Правило нуля и единицы......Page 580
28.3. Битонический сортировщик......Page 582
28.4. Сливающая сеть......Page 586
28.5. Сортирующая сеть......Page 589
29.1. Схемы из функциональных элементов......Page 594
29.2. Схемы для сложения......Page 599
29.2.2. Сложение с предвычислением переносов......Page 600
29.2.3. Сложение с запоминанием переносов......Page 606
29.3. Схемы для умножения......Page 608
29.3.1. Матричный умножитель......Page 609
29.3.2. Умножение с помощью дерева Уоллеса......Page 612
29.4.1. Устройство побитового сложения......Page 615
29.4.2. Одномерный умножитель......Page 617
30. Алгоритмы параллельных вычислений......Page 624
30.1.1. Номер в списке......Page 627
30.1.2. Параллельная обработка префиксов списка......Page 630
30.1.3. Метод Эйлерова цекла......Page 632
30.2. CRCW и EREW - алгоритмы......Page 635
30.3. Теорема Брента и эффективность по затратам......Page 643
30.4 Эффективная параллельная обработка префиксов......Page 647
30.5. Нарушение симметрии (детерминированный алгоритм)......Page 652
31.1. Матрицы и их свойства......Page 662
31.2. Алгоритм Штрассена умножения матриц......Page 671
31.3. Алгебраические системы и умножение булевых матриц......Page 676
31.4. Решение систем линейных уравнений......Page 680
31.5. Обращение матриц......Page 692
31.6. Положительно определенные симметрические матрицы и метод наименьших квадратов......Page 696
32. Многочлены и быстрое преобразование Фурье......Page 706
32.1. Представление многочленов......Page 708
32.2. Дискретное преобразование Фурье. Быстрый алгоритм......Page 713
32.3. Эффективные реализации быстрого преобразования Фурье......Page 720
33. Теоретико-числовые алгоритмы......Page 728
33.1. Начальные сведения из теории чисел......Page 729
33.2. Наибольший общий делитель......Page 734
33.3 Модулярная арифметика......Page 738
33.4. Решение линейных диофантовых уравнений......Page 742
33.5. Китайская теорема об остатках......Page 745
33.6. Степени элемента......Page 748
33.7. Криптограмма RSA с открытым ключом......Page 751
33.8. Проверка чисел на простоту......Page 757
33.9. Разложение чисел на множители......Page 764
34. Поиск подстрок......Page 772
34.1. Простейший алгоритм......Page 774
34.2. Алгоритм Рабина-Карпа......Page 776
34.3. Поиск подстрок с помощью конечных автоматов......Page 780
34.4. Алгоритм Кнута-Морриса-Пратта......Page 786
34.4.1. Алгоритм Кнута-Морриса-Пратта правилен......Page 791
34.5. Алгортм Бойера-Мура......Page 793
35.1. Свойства отрезков......Page 802
35.2. Есть ли пересекающиеся отрезки......Page 808
35.3. Построение выпуклой оболочки......Page 814
35.4. Отыскание пары ближайших точек......Page 822
36. NP-полнота......Page 829
36.1. Полиноминальное время......Page 830
36.2. Проверка принадлежности языку и класс NP......Page 837
36.3. NP-полнота и сводимость......Page 841
36.4. Доказательства NP-полноты......Page 849
36.5.1. Задача о клике......Page 856
36.5.2. Задача о вершинном покрытии......Page 858
36.5.3. Задача о суммах подмножеств......Page 860
36.5.4. Задача о гамильтоновом цикле......Page 862
36.5.5. Задача коммивояжера......Page 867
37. Приближенные алгоритмы......Page 872
37.1. Задача о вершинном покрытии......Page 874
37.2. Задача коммивояжера......Page 876
37.2.1. Задача коммивояжера (с неравенством треугольника)......Page 877
37.3. Задача о покрытии множествами......Page 881
37.4.1. Экспоненциальный алгоритм......Page 885
38. Литература......Page 892
Предметный указатель......Page 905
Именной указатель......Page 940
