Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013)

Томас Нормен Чарльз Лейзерсон Рональд Ривест Клиффорд Штайн АЛ ГО РИТМ Ы ПОСТРОЕНИЕ И АНАЛИЗ ТРЕТЬЕ ИЗДАНИЕ й$ Москва Санкт-Петербург Киев го13 ББК 32.973.26-018.2.75 А45 УДК б8!.3,07 Издательский дом "Вильямс" Зан. Редакцией С. Н. Тригуб Перевод с английского и редакция канд. техн. наум И, В. Красикова По общим вопросам обращайтесь в Издательский дом "Вильямс" по адресу: хпгойн2122пшлрц)утхллгпй.ссш,лййрг//нин.их122пширпггтхиЬГпд.сош Кормен, Томас Х. и др. А45 Алгоритмы: построение и анализ, 3-е изд.: Пер, с англ. — М.: ООО мИ. Д. Вильямс", 2013.

— 1328 с.: ил. — Парал. тит. англ. 18В)ч( 978-5-8459-1794-2 (рус.) ББК 32.973.26-018.2.75 Научно-популярное нгдогше томас Х Кермен, Чарльз И. Лейзерсон, Рональд Л. Рннест, Клнффорд Штайн Алгоритмы: Построение и анализ 3-е издание Литературный редактор П.

Н. Краслажам Верстка Д Н. Лачммчик Художественный редактор Е. Н дммммк Корректор И. В Красиков Паламскма в аачьть 31.06 20! 3. Формат усх ЮОП 6. Гарма!ура Тамаз. Печать афактмак Усв, печ а. 125.1. Уч -мьх а 96,2 Тарам 1500 эю. Звккг № 3726. Псовка Акахаммческак тнлагсафмк "Наука", 199034, Скмкг-Петербург, 9-к кмюм, 12ПЗ *мсз гнои, г.

Магам, у . Леем *, а 43, ств. 1 (с) Нздатсвьский дом "Вильямс", 2013 (с) МюзасЬазе\и 1пзп!аге оГ ТссЬпо!ойу, 2009 18ВН 978-5-8459-1794-2 (рус.) !ЗВН 978-0-2620-3384-8 (англ.) Все названия программных продуктов являются зарепютрированными торговыми марками соотвстствуюших фирм Никакая часть настоящею издания ни в каких целях не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами, будь то злеатронные няи механические, включая фотокопирование и запись на магнитный носитель, если на зто нег письменного рюрешения изаательства М1Т Ргсю.

Алгйогыо( папз1айоп Ггош бге Епййзь (зпйгмйе амбал роЫ!зйед Ьу М1Т Ргезз, Сорупйм 49 2009 Ьу Мазавсйозспз !пацане а( ТссЬпо1ойу. АП пйьи гшегчсб. Р(о рап оГ 03)з Ьоа1г шау Ье гарик!оса! !л впу Гопп ог Ьу апу е!се!гоше ог шасЬапюв! гпеапз (гпс!шйпй РЬавюорулщ, гесопйщ, ог )пГоптшпол нашйе аш( ш1печа1) ч (тоош реплазюп ш чпйщ йоги бю роЫ(зЬес 1Ьзз(ап 1впйгмйе пйпап раЫмЬа5 Ьу рдйшпм РоЫЬЫпй Ноозе ассогбшй ю гье Айгюшепг ччтв йа! Ел!провез !п!егпабопа1, Саруп81и ® 2013 Оглавление Предисловие 14 Часть 1.

Основы 23 Глава 1. Роль алгоритмов в вычислениях 26 Глава 2. Приступаем к изучению 38 Глава 3. Рост функций 67 Глава 4. Разделяй и властвуй 90 Глава 5. Вероятностный анализ и рандомизированные алгоритмы 140 Часть 11. Сортировка н порядковая статистика 173 Глава 6. Пирамидальная сортировка 179 Глава 7. Быстрая сортировка 198 Глава 8.

Сортировка за линейное время 220 Глава 9. Медианы и порядковые статистики 243 Часть 11!. Структуры данных 259 Глава 10. Элементарные структуры данных 264 Глава 11. Хеширование и хеш-таблицы 285 Глава 12. Бинарные деревья поиска 319 Глава 13. Красно-черные деревья 341 Глава 14. Расширение структур данных 372 Часть 1У. Усовершенствованные методы разработки и анализа 389 Глава 15. Динамическое программирование 392 Глава 16. Жадные алгоритмы 448 Глава 17. Амортизационный анализ 487 Часть У. Сложные структуры данных 517 Глава 18.

В-деревья 521 Оглавление Глава 19. Фибоначчиевы пирамиды 542 Глава 20. Деревья ван Эмде Боаса 568 Глава 21. Структуры данных для непересекающихся множеств 597 Часть Ъ'1. Алгоритмы для работы с графами 623 Глава 22. Элементарные алгоритмы для работы с графами 626 Глава 23. Минимальные остовные деревья 661 Глава 24. Кратчайшие пути из одной вершины 680 Глава 25. Кратчайшие пути между всеми парами вершин 722 Глава 26. Задача о максимальном потоке 747 Часть УП. Избранные темы 807 Глава 35.

Приближенные алгоритмы 1!57 Часть УП1. Приложения: математические основы 1195 Приложение А. Суммы и ряды П98 Приложение Б. Множества и прочие художества 1210 Приложение В. Комбинаторика и теория вероятности 1235 Приложение Г. Матрицы 1269 Литература 1282 Предметный указатель 1299 Глава Глава Глава Глава Глава Глава Глава Глава 27. Многопоточные алгоритмы 8П 28.

Работа с матрицами 852 29. Линейное программирование 883 30. Полиномы и быстрое преобразование Фурье 940 31, Теоретико-числовые алгоритмы 968 32. Поиск подстрок 1031 33. Вычислительная геометрия 1060 34. ХР-полнота 1096 Содержание Предисловие 14 Основы 23 Введение 24 Роль алгоритмов в вычислениях 2б 1.! Что такое алгоритмы 2б 1.2 Алгоритмы как технология 32 Приступаем к изучению 38 2.1 Сортировка вставкой 38 2.2 Анализ алгоритмов 45 2.3 Разработка алгоритмов 52 Рост функций 67 3.1 Асимптотические обозначения б8 3.2 Стандартные обозначения и часто встречающиеся функции 78 Разделяй и властвуй 90 4.1 Задача поиска максимального подмассива 93 4.2 Алгоритм Штрассена для умножения матриц 100 4.3 Метод подстановки решения рекуррентных соотношений 108 4.4 Метод деревьев рекурсии 113 4.5 Основной метод !19 * 4.6 Доказательство основной теоремы 123 Вероятностный анализ н рандомязированные алгоритмы 140 5.! Задача о найме 140 5.2 Индикаторная случайная величина 144 5.3 Рандомизированные алгоритмы 148 * 5.4 Вероятностный анализ и дальнейшее применение индикаторных случайных величин 15б Содержание Сортировка и порядковая статистика 173 Введение 174 Пирамидальная сортировка 179 6.1 Пирамиды 179 6.2 Поддержка свойства пирамиды 182 6.3 Построение пирамиды 185 6.4 Алгоритм пирамидальной сортировки 188 6.5 Очереди с приоритетами 190 Быстрая сортировка 198 7.1 Описание быстрой сортировки 198 7.2 Производительность быстрой сортировки 202 7.3 Рандомизироаанная быстрая сортировка 207 7.4 Анализ быстрой сортировки 208 Сортировка за линейное время 220 8.1 Нижние границы для алгоритмов сортировки 220 8.2 Сортировка подсчетом 223 8.3 Поразрядная сортировка 226 8.4 Карманная сортировка 230 Медианы и порядковые статистики 243 9.1 Минимум и максимум 244 9.2 Выбор в течение линейного ожидаемого времени 245 9.3 Алгоритм выбора с линейным временем работы в наихудшем случае 250 Структуры данных 259 Введение 260 Элементарные структуры данных 264 10.1 Стеки и очереди 264 10.2 Связанные списки 268 10.3 Реализация указателей и объектов 2?3 10.4 Представление корневых деревьев 277 Хеширование и хеш-таблицы 285 11.1 Таблицы с прямой адресацией 286 11.2 Хеш-таблицы 288 11.3 Хеш-функции 294 11.4 Открытая адресация 302 11.5 Идеальное хеширование 310 Содержание 14 Введение 390 * !6.4 Матроиды и жадные методы 471 * 16.5 Планирование заданий как матронд 479 17 Амортизационный анализ 487 17.1 Групповой анализ 488 !7.2 Метод бухгалтерского учета 492 17.3 Метод потенциалов 495 ! 7.4 Динамические таблицы 500 12 13 15 Гб Бинарные деревья поиска 319 !2.1 Что такое бинарное дерево поиска 319 12.2 Работа с бинарным деревом поиска 322 12.3 Вставка и удаление 327 12.4 Случайное построение бинарных деревьев поиска 332 Красно-черные деревья 341 !3.! Свойства красно-черных деревьев 341 13.2 Повороты 345 13.3 Вставка 348 13.4 Удаление 35б Расширение структур данных 372 !4.! Динамические порядковые статистики 372 !4.2 Расширение структур данных 378 14.3 Деревья отрезков 381 Усовершенствованные методы разработки и анализа 389 Динамическое программирование 392 15.1 Разрезание стержня 393 15.2 Перемножение цепочки матриц 403 15.3 Элементы динамического программирования 412 15.4 Наидлиннейшая общая подпоследовательность 424 !5.5 Оптимальные бинарные деревья поиска 431 Жадные алгоритмы 448 16.1 Задача о выборе процессов 449 16.2 Элементы жадной стратегии 457 16.3 Коды Хаффмана 463 Содержание Сложные структуры данных 517 Введение 518 В-деревья 521 18.1 Определение В-деревьев 525 18.2 Основные операции с В-деревьямн 528 18.3 Удаление ключа из В-дерева 536 Фнбоначчиевы пирамиды 542 19.1 Структура фибоначчиевых пирамид 544 !9.2 Операции над объединяемыми пирамидами 547 19.3 Уменьшение ключа и удаление узла 555 19.4 Оценка максимальной степени 559 18 19 20 21 Деревья ван Эмде Бааса 568 20.1 Предварительные подходы 569 20.2 Рекурсивная структура 573 20.3 Дерево ван Эмде Боаса 582 Структуры данных для непересекающихся множеств 597 21.1 Операции над непересекающимися множествами 597 21.2 Представление непересекающихся множеств с помощью связанных списков 600 21.3 Леса непересекающихся множеств 604 21.4 Анализ объединения по рангу со сжатием пути 608 Алгоритмы длн работы с графами б23 Введение 624 Элементарные алгоритмы для работы с графами 626 22.1 Представление графов 626 22.2 Поиск в ширину 630 22.3 Поиск в глубину 639 22.4 Топологическая сортировка 649 22.5 Сильно связные компоненты 652 22 23 24 Минимальные останные деревья 661 23.1 Выращивание минимального остовного дерева 662 23.2 Алгоритмы Крускала и Прима 667 Кратчайшие пути нз одной вершины 680 24.1 Алгоритм Беллмана-Форда 688 24.2 Кратчайшие пути из одной вершины в ориентированных ациклических графах 693 24.3 Алгоритм Дейкстры 696 24.4 Разностные ограничения и кратчайшие пути 702 24.5 Доказательства свойств кратчайших путей 709 Содержание 25 Кратчайшие пути между всеми парами вершин 722 25.! Задача о кратчайших путях и умножение матриц 724 25.2 Алгоритм Флойда-Уоршелла 731 25.3 Алгоритм Джонсона для разреженных графов 738 26 Задача о максимальном потоке 747 26.1 Транспортные сети 748 26.2 Метод Форда-Фалкерсона 753 26.3 Максимальное паросочетание 771 * 26.4 Алгоритмы проталкивания предпотока 775 * 26.5 Алгоритм "поднять-в-начало" 788 И1 Иэбранные темы 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 Содержание 31 Теоретико-числовые алгоритмы 968 31.1 Элементарные понятия теории чисел 970 31.2 Наибольший общий делитель 976 31.3 Модульная арифметика 982 3!.4 Решение модульных линейных уравнений 990 31.5 Китайская теорема об остатках 994 31.6 Степени элемента 997 31.7 Криптосистема с открытым ключом КЗА 1002 * 31.8 Проверка простоты 1009 * 31.9 Целочисленное разложение 102! 32 Поиск подстрок 1031 32.1 Простейший алгоритм поиска подстрок 1034 32.2 Алгоритм Рабина-Карпа !036 32.3 Поиск подстрок с помощью конечных автоматов !041 * 32.4 Алгоритм Кнута-Морриса-Пратта 1048 ЗЗ Вычислительная геометрия 1060 33,1 Свойства отрезков 1061 33.2 Определение наличия пересекающихся отрезков 1068 33.3 Поиск выпуклой оболочки 1075 33.4 Поиск пары ближайших точек 1086 34 ХР-полнота 1096 34.1 Полиномиальное время П02 34.2 Проверка за полиномиальное время П!О 34.3 ХР-полнота и приводимость П!5 34.4 Доказательства ХР-полноты П27 34.5 ХР-полные задачи ПЗб 35 Приближенные алгоритмы 1157 35.1 Задача о вершинном покрытии П59 35.2 Задача о коммивояжере П63 35.3 Задача о покрытии множества П69 35,4 Рандомизация и линейное программирование П75 35.5 Задача о сумме подмножества П80 У1П Приложенилг математические основы 1195 Введение 1196 А Суммы и ряды 1198 А.1 Суммы и их свойства П98 А.2 Оценки сумм !202 Содержание Б Множества и прочие художества 1210 Б.1 Множества 1210 Б.2 Отношения 1215 Б.З Функции 1218 Б.4 Графы 1221 Б.5 Деревья 122б В Комбинаторика и теория вероятности 1235 В.1 Основы комбинаторики 1235 В,2 Вероятность 1241 В.З Дискретные случайные величины 1248 В.4 Геометрическое и биномиальное распределения 1254 * В.5 Хвосты биномиального распределения 1200 Г Матрицы 1269 Г.1 Матрицы и матричные операции 12б9 Г.2 Основные свойства матриц 1274 Литература 1282 Предметный указатель 1299 Предисловие Вначале были компьютеры, но перед компьютерами были алгоритмы.