Оглавление

Предисловие 14
Часть I. Основы 23
Глава 1. Роль алгоритмов в вычислениях 26
Глава 2. Приступаем к изучению 38
Глава 3. Рост функций 67
Глава 4. Разделяй и властвуй 90
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 140
Часть II. Сортировка и порядковая статистика 173
Глава 6. Пирамидальная сортировка 179
Глава 7. Быстрая сортировка 198
Глава 8. Сортировка за линейное время 220
Глава 9. Медианы и порядковые статистики 243
Часть III. Структуры данных 259
Глава 10. Элементарные структуры данных 264
Глава 11. Хеширование и хеш-таблицы 285
Глава 12. Бинарные деревья поиска 319
Глава 13. Красно-черные деревья 341
Глава 14. Расширение структур данных 372
Часть IV. Усовершенствованные методы разработки и анализа 389
Глава 15. Динамическое программирование 392
Глава 16. Жадные алгоритмы 448
Глава 17. Амортизационный анализ 487
Часть V. Сложные структуры данных 517
Глава 18. B-деревья 521
Глава 19. Фибоначчиевы пирамиды 542
Глава 20. Деревья ван Эмде Боаса 568
Глава 21. Структуры данных для непересекающихся множеств 597
Часть VI. Алгоритмы для работы с графами 623
Глава 22. Элементарные алгоритмы для работы с графами 626
Глава 23. Минимальные остовные деревья 661
Глава 24. Кратчайшие пути из одной вершины 680
Глава 25. Кратчайшие пути между всеми парами вершин 722
Глава 26. Задача о максимальном потоке 747
Часть VII. Избранные темы 807
Глава 27. Многопоточные алгоритмы 811
Глава 28. Работа с матрицами 852
Глава 29. Линейное программирование 883
Глава 30. Полиномы и быстрое преобразование Фурье 940
Глава 31. Теоретико-числовые алгоритмы 968
Глава 32. Поиск подстрок 1031
Глава 33. Вычислительная геометрия 1060
Глава 34. NP-полнота 1096
Глава 35. Приближенные алгоритмы 1157
Часть VIII. Приложения: математические основы 1195
Приложение А. Суммы и ряды 1198
Приложение Б. Множества и прочие художества 1210
Приложение В. Комбинаторика и теория вероятности 1235
Приложение Г. Матрицы 1269
Литература 1282
Предметный указатель 1299