Алгоритмы. Построение и анализ
Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн
Фундаментальный труд известных специалистов в области кибернетики достоин занять место на полке любого человека, чья деятельность так или иначе связана с информатикой и алгоритмами. Для профессионала эта книга может служить настольным справочником, для преподавателя — пособием для подготовки к лекциям и источником интересных нетривиальных задач, для студентов и аспирантов — отличным учебником. Каждый может найти в ней именно тот материал, который касается интересующей его темы, и изложенный именно с тем уровнем сложности и строгости, который требуется читателю.
Описание алгоритмов на естественном языке дополняется псевдокодом, который позволяет любому имеющему хотя бы начальные знания и опыт программирования, реализовать алгоритм на используемом им языке программирования. Строгий математический анализ и обилие теорем сопровождаются большим количеством иллюстраций, элементарными рассуждениями и простыми приближенными оценками. Широта охвата материала и степень строгости его изложения дают основания считать эту книгу одной из лучших книг, посвященных разработке и анализу алгоритмов.
Издательский дом «Вильямс», 2005.
ISBN 978-5-8459-0857-4, 0-07-013151-1, (978-5-8459-0857-5 - издание 2012 г.)
Количество страниц: 1296.
Содержание книги «Алгоритмы. Построение и анализ»:
- 30 Введение
- 43 Часть I. Основы
- 44 Введение
- 46 Глава 1. Роль алгоритмов в вычислениях
- 46 1.1 Алгоритмы
- 47 Какие задачи решаются с помощью алгоритмов?
- 50 Структуры данных
- 50 Методические указания
- 51 Сложные задачи
- 52 Упражнения
- 52 1.2 Алгоритмы как технология
- 52 Эффективность
- 54 Алгоритмы и другие технологии
- 55 Упражнения
- 55 Задачи
- 56 Заключительные замечания
- 46 1.1 Алгоритмы
- 57 Глава 2. Приступаем к изучению
- 57 2.1 Сортировка вставкой
- 59 Инварианты цикла и корректность сортировки вставкой
- 61 Соглашения, принятые при составлении псевдокода
- 63 Упражнения
- 64 2.2 Анализ алгоритмов
- 66 Анализ алгоритма, работающего по методу вставок
- 69 Наихудшее и среднее время работы
- 70 Порядок возрастания
- 71 Упражнения
- 71 2.3 Разработка алгоритмов
- 72 2.3.1 Метод декомпозиции
- 78 2.3.2 Анализ алгоритмов, основанных на принципе «разделяй и властвуй»
- 78 Анализ алгоритма сортировки слиянием
- 81 Упражнения
- 83 Задачи
- 86 Заключительные замечания
- 57 2.1 Сортировка вставкой
- 87 Глава 3. Рост функций
- 88 3.1 Асимптотические обозначения
- 88 ϴ-обозначения
- 91 O-обозначения
- 92 Ω-обозначения
- 93 Асимптотические обозначения в уравнениях и неравенствах
- 94 о-обозначения
- 95 ω-обозначения
- 96 Сравнение функций
- 97 Упражнения
- 98 3.2 Стандартные обозначения и часто встречающиеся функции
- 98 Монотонность
- 98 Округление в большую и меньшую сторону
- 98 Модульная арифметика
- 99 Полиномы
- 99 Показательные функции
- 100 Логарифмы
- 102 Факториалы
- 102 Функциональная итерация
- 103 Итерированная логарифмическая функция
- 103 Числа Фибоначчи
- 104 Упражнения
- 105 Задачи
- 108 Заключительные замечания
- 88 3.1 Асимптотические обозначения
- 109 Глава 4. Рекуррентные соотношения
- 110 Технические детали
- 111 4.1 Метод подстановки
- 112 Как угадать решение
- 113 Тонкие нюансы
- 114 Остерегайтесь ошибок
- 114 Замена переменных
- 115 Упражнения
- 115 4.2 Метод деревьев рекурсии
- 120 Упражнения
- 121 4.3 Основной метод
- 121 Основная теорема
- 122 Использование основного метода
- 123 Упражнения
- 124 4.4 Доказательство основной теоремы
- 125 4.4.1 Доказательство теоремы для точных степеней
- 130 4.4.2 Учет округления чисел
- 133 Упражнения
- 133 Задачи
- 138 Заключительные замечания
- 140 Глава 5. Вероятностный анализ и рандомизированные алгоритмы
- 140 5.1 Задача о найме сотрудника
- 142 Анализ наихудшего случая
- 142 Вероятностный анализ
- 143 Рандомизированные алгоритмы
- 144 Упражнения
- 144 5.2 Индикаторная случайная величина
- 146 Анализ задачи о найме сотрудника с помощью индикаторных случайных величин
- 148 Упражнения
- 149 5.3 Рандомизированные алгоритмы
- 151 Массивы, полученные в результате случайной перестановки
- 155 Упражнения
- 156 5.4 Вероятностный анализ и дальнейшее применение индикаторных случайных величин
- 157 5.4.1 Парадокс дней рождения
- 158 Анализ с помощью индикаторных случайных величин
- 160 5.4.2 Шары и урны
- 161 5.4.3 Последовательности выпадения орлов
- 165 5.4.4 Задача о найме сотрудника в оперативном режиме
- 167 Упражнения
- 168 Задачи
- 171 Заключительные замечания
- 140 5.1 Задача о найме сотрудника
- 173 Часть II. Сортировка и порядковая статистика
- 174 Введение
- 178 Глава 6. Пирамидальная сортировка
- 179 6.1 Пирамиды
- 181 Упражнения
- 182 6.2 Поддержка свойства пирамиды
- 184 Упражнения
- 184 6.3 Создание пирамиды
- 187 Упражнения
- 187 6.4 Алгоритм пирамидальной сортировки
- 188 Упражнения
- 190 6.5 Очереди с приоритетами
- 193 Упражнения
- 194 Задачи
- 196 Заключительные замечания
- 179 6.1 Пирамиды
- 198 Глава 7. Быстрая сортировка
- 199 7.1 Описание быстрой сортировки
- 199 Разбиение массива
- 203 Упражнения
- 203 7.2 Производительность быстрой сортировки
- 203 Наихудшее разбиение
- 204 Наилучшее разбиение
- 204 Сбалансированное разбиение
- 205 Интуитивные рассуждения для среднего случая
- 207 Упражнения
- 208 7.3 Рандомизированная версия быстрой сортировки
- 209 Упражнения
- 209 7.4 Анализ быстрой сортировки
- 209 7.4.1 Анализ в наихудшем случае
- 210 7.4.2 Математическое ожидание времени работы
- 210 Время работы и сравнения
- 213 Упражнения
- 214 Задачи
- 219 Заключительные замечания
- 199 7.1 Описание быстрой сортировки
- 220 Глава 8. Сортировка за линейное время
- 221 8.1 Нижние оценки алгоритмов сортировки
- 221 Модель дерева решений
- 222 Нижняя оценка для наихудшего случая
- 223 Упражнения
- 224 8.2 Сортировка подсчетом
- 226 Упражнения
- 226 8.3 Поразрядная сортировка
- 230 Упражнения
- 230 8.4 Карманная сортировка
- 234 Упражнения
- 234 Задачи
- 238 Заключительные замечания
- 221 8.1 Нижние оценки алгоритмов сортировки
- 240 Глава 9. Медианы и порядковые статистики
- 241 9.1 Минимум и максимум
- 241 Одновременный поиск минимума и максимума
- 242 Упражнения
- 243 9.2 Выбор в течение линейного ожидаемого времени
- 247 Упражнения
- 247 9.3 Алгоритм выбора с линейным временем работы в наихудшем случае
- 250 Упражнения
- 252 Задачи
- 254 Заключительные замечания
- 241 9.1 Минимум и максимум
- 255 Часть III. Структуры данных
- 256 Введение
- 260 Глава 10. Элементарные структуры данных
- 260 10.1 Стеки и очереди
- 260 Стеки
- 262 Очереди
- 263 Упражнения
- 264 10.2 Связанные списки
- 265 Поиск в связанном списке
- 265 Вставка в связанный список
- 266 Удаление из связанного списка
- 266 Ограничители
- 268 Упражнения
- 269 10.3 Реализация указателей и объектов
- 269 Представление объектов с помощью нескольких массивов
- 270 Представление объектов с помощью одного массива
- 271 Выделение и освобождение памяти
- 273 Упражнения
- 274 10.4 Представление корневых деревьев
- 274 Бинарные деревья
- 275 Корневые деревья с произвольным ветвлением
- 276 Другие представления деревьев
- 276 Упражнения
- 277 Задачи
- 280 Заключительные замечания
- 260 10.1 Стеки и очереди
- 282 Глава 11. Хеш-таблицы
- 283 11.1 Таблицы с прямой адресацией
- 284 Упражнения
- 285 11.2 Хеш-таблицы
- 286 Разрешение коллизий при помощи цепочек
- 288 Анализ хеширования с цепочками
- 290 Упражнения
- 291 11.3 Хеш-функции
- 291 Чем определяется качество хеш-функции
- 292 Интерпретация ключей как целых неотрицательных чисел
- 292 11.3.1 Метод деления
- 293 11.3.2 Метод умножения
- 294 11.3.3 Универсальное хеширование
- 297 Построение универсального множества хеш-функций
- 298 Упражнения
- 300 11.4 Открытая адресация
- 302 Линейное исследование
- 303 Квадратичное исследование
- 303 Двойное хеширование
- 305 Анализ хеширования с открытой адресацией
- 307 Упражнения
- 308 11.5 Идеальное хеширование
- 312 Упражнения
- 313 Задачи
- 315 Заключительные замечания
- 283 11.1 Таблицы с прямой адресацией
- 316 Глава 12. Бинарные деревья поиска
- 317 12.1 Что такое бинарное дерево поиска
- 319 Упражнения
- 319 12.2 Работа с бинарным деревом поиска
- 320 Поиск
- 321 Поиск минимума и максимума
- 321 Предшествующий и последующий элементы
- 323 Упражнения
- 324 12.3 Вставка и удаление
- 324 Вставка
- 325 Удаление
- 327 Упражнения
- 328 12.4 Случайное построение бинарных деревьев поиска
- 331 Упражнения
- 332 Задачи
- 335 Заключительные замечания
- 317 12.1 Что такое бинарное дерево поиска
- 336 Глава 13. Красно-черные деревья
- 336 13.1 Свойства красно-черных деревьев
- 339 Упражнения
- 340 13.2 Повороты
- 341 Упражнения
- 342 13.3 Вставка
- 350 Анализ
- 350 Упражнения
- 351 13.4 Удаление
- 356 Анализ
- 356 Упражнения
- 357 Задачи
- 364 Заключительные замечания
- 336 13.1 Свойства красно-черных деревьев
- 365 Глава 14. Расширение структур данных
- 366 14.1 Динамические порядковые статистики
- 367 Выборка элемента с заданным рангом
- 368 Определение ранга элемента
- 369 Поддержка размера поддеревьев
- 371 Упражнения
- 372 14.2 Расширение структур данных
- 373 Расширение красно-черных деревьев
- 374 Упражнения
- 375 14.3 Деревья отрезков
- 380 Упражнения
- 381 Задачи
- 382 Заключительные замечания
- 366 14.1 Динамические порядковые статистики
- 383 Часть IV. Усовершенствованные методы разработки и анализа
- 384 Введение
- 386 Глава 15. Динамическое программирование
- 387 15.1 Расписание работы конвейера
- 389 Первый этап: структура самой быстрой сборки
- 391 Второй этап: рекурсивное решение
- 393 Третий этап: вычисление минимальных промежутков времени
- 394 Четвертый этап: построение самого быстрого пути
- 395 Упражнения
- 395 15.2 Перемножение цепочки матриц
- 397 Подсчет количества способов расстановки скобок
- 398 Первый этап: структура оптимальной расстановки скобок
- 399 Второй этап: рекурсивное решение
- 400 Третий этап: вычисление оптимальной стоимости
- 403 Четвертый этап: конструирование оптимального решения
- 404 Упражнения
- 404 15.3 Элементы динамического программирования
- 405 Оптимальная подструктура
- 411 Перекрытие вспомогательных задач
- 414 Построение оптимального решения
- 414 Запоминание
- 417 Упражнения
- 418 15.4 Самая длинная общая подпоследовательность
- 419 Этап 1: характеристика самой длинной общей подпоследовательности
- 421 Этап 2: рекурсивное решение
- 422 Этап 3: вычисление длины самой длинной общей подпоследовательности
- 423 Этап 4: построение самой длинной общей подпоследовательности
- 424 Улучшение кода
- 425 Упражнения
- 425 15.5 Оптимальные бинарные деревья поиска
- 429 Этап 1: структура оптимального бинарного дерева поиска
- 430 Этап 2: рекурсивное решение
- 431 Этап 3: вычисление математического ожидания стоимости поиска в оптимальном бинарном дереве поиска
- 433 Упражнения
- 434 Задачи
- 440 Заключительные замечания
- 387 15.1 Расписание работы конвейера
- 442 Глава 16. Жадные алгоритмы
- 443 16.1 Задача о выборе процессов
- 444 Оптимальная подструктура задачи о выборе процессов
- 446 Рекурсивное решение
- 446 Преобразование решения динамического программирования в жадное решение
- 449 Рекурсивный жадный алгоритм
- 451 Итерационный жадный алгоритм
- 452 Упражнения
- 453 16.2 Элементы жадной стратегии
- 454 Свойство жадного выбора
- 455 Оптимальная подструктура
- 456 Сравнение жадных алгоритмов и динамического программирования
- 458 Упражнения
- 459 16.3 Коды Хаффмана
- 460 Префиксные коды
- 462 Построение кода Хаффмана
- 464 Корректность алгоритма Хаффмана
- 466 Упражнения
- 467 Теоретические основы жадных методов
- 467 Матроиды
- 470 Жадные алгоритмы на взвешенном матроиде
- 474 Упражнения
- 474 Планирование заданий
- 478 Упражнения
- 478 Задачи
- 481 Заключительные замечания
- 443 16.1 Задача о выборе процессов
- 482 Глава 17. Амортизационный анализ
- 483 17.1 Групповой анализ
- 483 Стековые операции
- 485 Приращение показаний бинарного счетчика
- 487 Упражнения
- 487 17.2 Метод бухгалтерского учета
- 489 Стековые операции
- 490 Приращение показаний бинарного счетчика
- 490 Упражнения
- 491 17.3 Метод потенциалов
- 492 Стековые операции
- 493 Увеличение показаний бинарного счетчика
- 494 Упражнения
- 495 17.4 Динамические таблицы
- 496 17.4.1 Расширение таблицы
- 499 17.4.2 Расширение и сжатие таблицы
- 504 Упражнения
- 505 Задачи
- 510 Заключительные замечания
- 483 17.1 Групповой анализ
- 511 Часть V. Сложные структуры данных
- 512 Введение
- 515 Глава 18. B-деревья
- 516 Структуры данных во вторичной памяти
- 519 18.1 Определение B-деревьев
- 521 Высота B-дерева
- 522 Упражнения
- 522 18.2 Основные операции с B-деревьями
- 522 Поиск в B-дереве
- 523 Создание пустого B-дерева
- 524 Вставка ключа в B-дерево
- 528 Упражнения
- 530 18.3 Удаление ключа из B-дерева
- 533 Упражнения
- 533 Задачи
- 536 Заключительные замечания
- 537 Глава 19. Биномиальные пирамиды
- 539 19.1 Биномиальные деревья и биномиальные пирамиды
- 539 19.1.1 Биномиальные деревья
- 541 19.1.2 Биномиальные пирамиды
- 543 Упражнения
- 544 19.2 Операции над биномиальными пирамидами
- 544 Создание новой биномиальной пирамиды
- 544 Поиск минимального ключа
- 545 Слияние двух биномиальных пирамид
- 550 Вставка узла
- 551 Извлечение вершины с минимальным ключом
- 552 Уменьшение ключа
- 554 Удаление ключа
- 554 Упражнения
- 555 Задачи
- 557 Заключительные замечания
- 539 19.1 Биномиальные деревья и биномиальные пирамиды
- 558 Глава 20. Фибоначчиевы пирамиды
- 559 20.1 Структура фибоначчиевых пирамид
- 561 Потенциальная функция
- 562 Максимальная степень
- 562 20.2 Операции над сливаемыми пирамидами
- 563 Создание новой фибоначчиевой пирамиды
- 563 Вставка узла
- 564 Поиск минимального узла
- 564 Объединение двух фибоначчиевых пирамид
- 565 Извлечение минимального узла
- 571 Упражнения
- 571 20.3 Уменьшение ключа и удаление узла
- 571 Уменьшение ключа
- 575 Удаление узла
- 575 Упражнения
- 575 20.4 Оценка максимальной степени
- 578 Упражнения
- 578 Задачи
- 579 Заключительные замечания
- 559 20.1 Структура фибоначчиевых пирамид
- 581 Глава 21. Структуры данных для непересекающихся множеств
- 582 21.1 Операции над непересекающимися множествами
- 583 Приложение структур данных для непересекающихся множеств
- 584 Упражнения
- 585 21.2 Представление непересекающихся множеств с помощью связанных списков
- 586 Простая реализация объединения
- 587 Весовая эвристика
- 588 Упражнения
- 589 21.3 Лес непересекающихся множеств
- 589 Эвристики для повышения эффективности
- 590 Псевдокоды
- 592 Влияние эвристик на время работы
- 592 Упражнения
- 592 21.4 Анализ объединения по рангу со сжатием пути
- 593 Очень быстро и очень медленно растущая функция
- 594 Свойства рангов
- 595 Доказательство границы времени работы
- 596 Потенциальная функция
- 598 Изменения потенциала и амортизированная стоимость операций
- 601 Упражнения
- 601 Задачи
- 605 Заключительные замечания
- 582 21.1 Операции над непересекающимися множествами
- 607 Часть VI. Алгоритмы для работы с графами
- 608 Введение
- 609 Глава 22. Элементарные алгоритмы для работы с графами
- 609 22.1 Представление графов
- 612 Упражнения
- 613 22.2 Поиск в ширину
- 616 Анализ
- 617 Кратчайшие пути
- 620 Деревья поиска в ширину
- 621 Упражнения
- 622 22.3 Поиск в глубину
- 626 Свойства поиска в глубину
- 628 Классификация ребер
- 630 Упражнения
- 632 22.4 Топологическая сортировка
- 634 Упражнения
- 635 22.5 Сильно связные компоненты
- 640 Упражнения
- 641 Задачи
- 643 Заключительные замечания
- 609 22.1 Представление графов
- 644 Глава 23. Минимальные остовные деревья
- 645 23.1 Построение минимального остовного дерева
- 649 Упражнения
- 651 23.2 Алгоритмы Крускала и Прима
- 651 Алгоритм Крускала
- 653 Алгоритм Прима
- 656 Упражнения
- 658 Задачи
- 661 Заключительные замечания
- 645 23.1 Построение минимального остовного дерева
- 663 Глава 24. Кратчайшие пути из одной вершины
- 664 Варианты
- 665 Оптимальная структура задачи о кратчайшем пути
- 666 Ребра с отрицательным весом
- 667 Циклы
- 668 Представление кратчайших путей
- 669 Ослабление
- 671 Свойства кратчайших путей и ослабления
- 672 Краткое содержание главы
- 672 24.1 Алгоритм Беллмана-Форда
- 676 Упражнения
- 677 24.2 Кратчайшие пути из одной вершины в ориентированных ациклических графах
- 679 Упражнения
- 680 24.3 Алгоритм Дейкстры
- 684 Анализ
- 686 Упражнения
- 687 24.4 Разностные ограничения и кратчайшие пути
- 687 Линейное программирование
- 688 Системы разностных ограничений
- 690 Графы ограничений
- 692 Решение систем разностных ограничений
- 692 Упражнения
- 694 24.5 Доказательства свойств кратчайших путей
- 694 Неравенство треугольника
- 695 Влияние ослабления на оценки кратчайшего пути
- 697 Ослабление и деревья кратчайших путей
- 700 Упражнения
- 702 Задачи
- 706 Заключительные замечания
- 708 Глава 25. Кратчайшие пути между всеми парами вершин
- 710 Краткое содержание главы
- 711 25.1 Задача о кратчайших путях и умножение матриц
- 711 Структура кратчайшего пути
- 712 Рекурсивное решение задачи о кратчайших путях между всеми парами вершин
- 712 Вычисление весов кратчайших путей в восходящем порядке
- 714 Улучшение времени работы
- 716 Упражнения
- 718 25.2 Алгоритм Флойда-Варшалла
- 718 Структура кратчайшего пути
- 719 Рекурсивное решение задачи о кратчайших путях между всеми парами вершин
- 720 Вычисление весов кратчайших путей в восходящем порядке
- 720 Построение кратчайшего пути
- 722 Транзитивное замыкание ориентированного графа
- 724 Упражнения
- 726 25.3 Алгоритм Джонсона для разреженных графов
- 726 Сохранение кратчайших путей
- 728 Генерация неотрицательных весов путем их изменения
- 728 Вычисление кратчайших путей между всеми парами вершин
- 730 Упражнения
- 731 Задачи
- 732 Заключительные замечания
- 734 Глава 26. Задача о максимальном потоке
- 735 26.1 Транспортные сети
- 735 Транспортные сети и потоки
- 737 Пример потока
- 739 Сети с несколькими источниками и стоками
- 740 Как работать с потоками
- 741 Упражнения
- 742 26.2 Метод Форда-Фалкерсона
- 743 Остаточные сети
- 745 Увеличивающие пути
- 746 Разрезы транспортных сетей
- 749 Базовый алгоритм Форда-Фалкерсона
- 750 Анализ метода Форда-Фалкерсона
- 752 Алгоритм Эдмондса-Карпа
- 755 Упражнения
- 756 26.3 Максимальное паросочетание
- 757 Задача поиска максимального паросочетания в двудольном графе
- 758 Поиск максимального паросочетания в двудольном графе
- 761 Упражнения
- 761 26.4 Алгоритмы проталкивания предпотока
- 762 Интуитивные соображения
- 764 Основные операции
- 764 Операция проталкивания
- 766 Операция подъема
- 766 Универсальный алгоритм
- 768 Корректность метода проталкивания предпотока
- 768 Анализ метода проталкивания предпотока
- 773 Упражнения
- 774 26.5 Алгоритм «поднять-в-начало»
- 775 Допустимые ребра и сети
- 777 Списки соседей
- 777 Разгрузка переполненной вершины
- 780 Алгоритм «поднять-в-начало»
- 783 Анализ
- 785 Упражнения
- 786 Задачи
- 793 Заключительные замечания
- 735 26.1 Транспортные сети
- 795 Часть VII. Избранные темы
- 796 Введение
- 799 Глава 27. Сортирующие сети
- 800 27.1 Сравнивающие сети
- 803 Упражнения
- 805 27.2 Нуль-единичный принцип
- 807 Упражнения
- 808 27.3 Битоническая сортирующая сеть
- 809 Полуфильтр
- 810 Битонический сортировщик
- 812 Упражнения
- 813 27.4 Объединяющая сеть
- 815 Упражнения
- 816 27.5 Сортирующая сеть
- 818 Упражнения
- 819 Задачи
- 822 Заключительные замечания
- 800 27.1 Сравнивающие сети
- 823 Глава 28. Работа с матрицами
- 824 28.1 Свойства матриц
- 824 Матрицы и векторы
- 827 Операции над матрицами
- 828 Обратные матрицы, ранги и детерминанты
- 831 Положительно определенные матрицы
- 831 Упражнения
- 833 28.2 Алгоритм умножения матриц Штрассена
- 833 Обзор алгоритма
- 834 Определение произведений подматриц
- 838 Обсуждение метода
- 839 Упражнения
- 839 28.3 Решение систем линейных уравнений
- 841 Обзор LUP-разложения
- 842 Прямая и обратная подстановки
- 845 Вычисление LU-разложения
- 848 Вычисление LUP-разложения
- 852 Упражнения
- 853 28.4 Обращение матриц
- 853 Вычисление обратной матрицы из LUP-разложения
- 854 Умножение матриц и обращение матрицы
- 857 Упражнения
- 858 28.5 Симметричные положительно определенные матрицы и метод наименьших квадратов
- 861 Метод наименьших квадратов
- 865 Упражнения
- 865 Задачи
- 867 Заключительные замечания
- 824 28.1 Свойства матриц
- 869 Глава 29. Линейное программирование
- 869 Политическая задача
- 872 Общий вид задач линейного программирования
- 872 Краткий обзор задач линейного программирования
- 876 Приложения линейного программирования
- 877 Алгоритмы решения задач линейного программирования
- 877 29.1 Стандартная и каноническая формы задач линейного программирования
- 878 Стандартная форма
- 879 Преобразование задач линейного программирования в стандартную форму
- 882 Преобразование задач линейного программирования в каноническую форму
- 885 Упражнения
- 886 29.2 Формулирование задач в виде задач линейного программирования
- 887 Кратчайшие пути
- 887 Максимальный поток
- 888 Поиск потока с минимальными затратами
- 889 Многопродуктовый поток
- 891 Упражнения
- 892 29.3 Симплекс-алгоритм
- 893 Пример симплекс-алгоритма
- 897 Замещение
- 899 Формальный симплекс-алгоритм
- 905 Завершение
- 907 Упражнения
- 908 29.4 Двойственность
- 914 Упражнения
- 914 29.5 Начальное базисное допустимое решение
- 914 Поиск начального решения
- 920 Основная теорема линейного программирования
- 921 Упражнения
- 922 Задачи
- 924 Заключительные замечания
- 926 Глава 30. Полиномы и быстрое преобразование Фурье
- 926 Полиномы
- 928 Краткое содержание главы
- 928 30.1 Представление полиномов
- 929 Представление, основанное на коэффициентах
- 929 Представление, основанное на значениях в точках
- 932 Быстрое умножение полиномов, заданных в коэффициентной форме
- 934 Упражнения
- 935 30.2 ДПФ и БПФ
- 935 Комплексные корни из единицы
- 938 Дискретное преобразование Фурье
- 938 Быстрое преобразование Фурье
- 941 Интерполяция в точках, являющихся комплексными корнями из единицы
- 942 Упражнения
- 943 30.3 Эффективные реализации БПФ
- 944 Итеративная реализация БПФ
- 947 Параллельная схема БПФ
- 949 Упражнения
- 949 Задачи
- 953 Заключительные замечания
- 954 Глава 31. Теоретико-числовые алгоритмы
- 955 Размер входных наборов данных и стоимость арифметических вычислений
- 956 31.1 Элементарные обозначения, принятые в теории чисел
- 956 Делимость и делители
- 956 Простые и составные числа
- 957 Теорема о делении, остатки и равенство по модулю
- 958 Общие делители и наибольшие общие делители
- 960 Взаимно простые целые числа
- 960 Единственность разложения на множители
- 961 Упражнения
- 962 31.2 Наибольший общий делитель
- 963 Алгоритм Евклида
- 964 Время работы алгоритма Евклида
- 965 Развернутая форма алгоритма Евклида
- 967 Упражнения
- 968 31.3 Модульная арифметика
- 968 Конечные группы
- 969 Группы, образованные сложением и умножением по модулю
- 972 Подгруппы
- 973 Подгруппы, сгенерированные элементом группы
- 975 Упражнения
- 975 31.4 Решение модульных линейных уравнений
- 979 Упражнения
- 979 31.5 Китайская теорема об остатках
- 982 Упражнения
- 983 31.6 Степени элемента
- 985 Возведение в степень путем последовательного возведения в квадрат
- 987 Упражнения
- 987 31.7 Криптосистема с открытым ключом RSA
- 988 Криптографические системы с открытым ключом
- 991 Криптографическая система RSA
- 995 Упражнения
- 995 31.8 Проверка простоты
- 996 Плотность распределения простых чисел
- 997 Проверка псевдопростых чисел
- 999 Рандомизированный тест простоты Миллера-Рабина
- 1002 Частота ошибок в тесте Миллера-Рабина
- 1006 Упражнения
- 1006 31.9 Целочисленное разложение
- 1007 Эвристический ρ-метод Полларда
- 1012 Упражнения
- 1013 Задачи
- 1015 Заключительные замечания
- 1017 Глава 32. Поиск подстрок
- 1019 Обозначения и терминология
- 1020 32.1 Простейший алгоритм поиска подстрок
- 1021 Упражнения
- 1022 32.2 Алгоритм Рабина-Карпа
- 1028 Упражнения
- 1028 32.3 Поиск подстрок с помощью конечных автоматов
- 1029 Конечные автоматы
- 1030 Автоматы поиска подстрок
- 1035 Вычисление функции переходов
- 1036 Упражнения
- 1036 32.4 Алгоритм Кнута-Морриса-Пратта
- 1037 Префиксная функция для образца
- 1040 Анализ времени работы
- 1041 Корректность вычисления префиксной функции
- 1043 Корректность алгоритма Кнута-Морриса-Пратта
- 1044 Упражнения
- 1045 Задачи
- 1046 Заключительные замечания
- 1047 Глава 33. Вычислительная геометрия
- 1048 33.1 Свойства отрезков
- 1049 Векторное произведение
- 1050 Поворот последовательных отрезков
- 1051 Определение того, пересекаются ли два отрезка
- 1053 Другие применения векторного произведения
- 1053 Упражнения
- 1055 33.2 Определение наличия пересекающихся отрезков
- 1056 Упорядочение отрезков
- 1057 Перемещение выметающей прямой
- 1058 Псевдокод, выявляющий пересечение отрезков
- 1060 Корректность
- 1061 Время работы
- 1062 Упражнения
- 1063 33.3 Построение выпуклой оболочки
- 1065 Сканирование по Грэхему
- 1071 Обход по Джарвису
- 1073 Упражнения
- 1074 33.4 Поиск пары ближайших точек
- 1075 Алгоритм декомпозиции
- 1077 Корректность
- 1078 Реализация и время работы алгоритма
- 1079 Упражнения
- 1080 Задачи
- 1083 Заключительные замечания
- 1048 33.1 Свойства отрезков
- 1085 Глава 34. NP-полнота
- 1087 NP -полнота и классы P и NP
- 1088 Как показать, что задача является NP-полной
- 1091 Краткое содержание главы
- 1091 34.1 Полиномиальное время
- 1092 Абстрактные задачи
- 1093 Кодирование
- 1096 Структура формальных языков
- 1100 Упражнения
- 1100 34.2 Проверка за полиномиальное время
- 1101 Гамильтоновы циклы
- 1102 Алгоритмы верификации
- 1103 Класс сложности NP
- 1105 Упражнения
- 1106 34.3 NP-полнота и приводимость
- 1106 Приводимость
- 1108 NP-полнота
- 1110 Выполнимость схем
- 1117 Упражнения
- 1118 34.4 Доказательство NP-полноты
- 1119 Выполнимость формулы
- 1122 3-CNF выполнимость
- 1126 Упражнения
- 1127 34.5 NP-полные задачи
- 1128 34.5.1 Задача о клике
- 1131 34.5.2 Задача о вершинном покрытии
- 1133 34.5.3 Задача о гамильтоновых циклах
- 1138 34.5.4 Задача о коммивояжере
- 1140 34.5.5 Задача о сумме подмножества
- 1144 Упражнения
- 1145 Задачи
- 1149 Заключительные замечания
- 1151 Глава 35. Приближенные алгоритмы
- 1151 Оценка качества приближенных алгоритмов
- 1153 Краткое содержание главы
- 1154 35.1 Задача о вершинном покрытии
- 1157 Упражнения
- 1157 35.2 Задача о коммивояжере
- 1158 35.2.1 Задача о коммивояжере с неравенством треугольника
- 1161 35.2.2 Общая задача о коммивояжере
- 1163 Упражнения
- 1164 35.3 Задача о покрытии множества
- 1166 Жадный приближенный алгоритм
- 1166 Анализ
- 1169 Упражнения
- 1170 35.4 Рандомизация и линейное программирование
- 1170 Рандомизированный приближенный алгоритм для задачи о MAX-3-CNF выполнимости
- 1172 Аппроксимация взвешенного вершинного покрытия с помощью линейного программирования
- 1175 Упражнения
- 1176 35.5 Задача о сумме подмножества
- 1176 Точный алгоритм с экспоненциальным временем работы
- 1178 Схема аппроксимации с полностью полиномиальным временем работы
- 1182 Упражнения
- 1182 Задачи
- 1186 Заключительные замечания
- 1189 Часть VIII. Приложения: математические основы
- 1190 Введение
- 1191 Приложение А. Ряды
- 1192 А.1 Суммы и их свойства
- 1192 Линейность
- 1193 Арифметическая прогрессия
- 1193 Суммы квадратов и кубов
- 1193 Геометрическая прогрессия
- 1194 Гармонический ряд
- 1194 Интегрирование и дифференцирование рядов
- 1194 Суммы разностей
- 1195 Произведения
- 1195 Упражнения
- 1195 А.2 Оценки сумм
- 1196 Математическая индукция
- 1196 Почленное сравнение
- 1198 Разбиение рядов
- 1199 Приближение интегралами
- 1201 Упражнения
- 1201 Задачи
- 1201 Заключительные замечания
- 1192 А.1 Суммы и их свойства
- 1202 Приложение Б. Множества и прочие художества
- 1202 Б.1 Множества
- 1207 Упражнения
- 1207 Б.2 Отношения
- 1209 Упражнения
- 1210 Б.3 Функции
- 1212 Упражнения
- 1213 Б.4 Графы
- 1217 Упражнения
- 1218 Б.5 Деревья
- 1218 Б.5.1 Свободные деревья
- 1220 Б.5.2 Деревья с корнем и упорядоченные деревья
- 1221 Б.5.3 Бинарные и позиционные деревья
- 1223 Упражнения
- 1224 Задачи
- 1225 Заключительные замечания
- 1202 Б.1 Множества
- 1226 Приложение В. Комбинаторика и теория вероятности
- 1226 В.1 Основы комбинаторики
- 1227 Правила суммы и произведения
- 1227 Строки
- 1227 Перестановки
- 1228 Сочетания
- 1229 Биномиальные коэффициенты
- 1229 Оценки биномиальных коэффициентов
- 1230 Упражнения
- 1232 В.2 Вероятность
- 1232 Аксиомы вероятности
- 1233 Дискретные распределения вероятностей
- 1234 Непрерывное равномерное распределение вероятности
- 1234 Условная вероятность и независимость
- 1236 Теорема Байеса
- 1237 Упражнения
- 1238 В.3 Дискретные случайные величины
- 1239 Математическое ожидание случайной величины
- 1242 Дисперсия и стандартное отклонение
- 1243 Упражнения
- 1243 В.4 Геометрическое и биномиальное распределения
- 1244 Геометрическое распределение
- 1245 Биномиальное распределение
- 1248 Упражнения
- 1249 В.5 Хвосты биномиального распределения
- 1254 Упражнения
- 1255 Задачи
- 1256 Заключительные замечания
- 1226 В.1 Основы комбинаторики
- 1257 Библиография
- 1277 Предметный указатель
Инструкция как скачать книгу Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн: Алгоритмы. Построение и анализ в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.