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

Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн

Фундаментальный труд известных специалистов в области кибернетики достоин занять место на полке любого человека, чья деятельность так или иначе связана с информатикой и алгоритмами. Для профессионала эта книга может служить настольным справочником, для преподавателя — пособием для подготовки к лекциям и источником интересных нетривиальных задач, для студентов и аспирантов — отличным учебником. Каждый может найти в ней именно тот материал, который касается интересующей его темы, и изложенный именно с тем уровнем сложности и строгости, который требуется читателю.

Описание алгоритмов на естественном языке дополняется псевдокодом, который позволяет любому имеющему хотя бы начальные знания и опыт программирования, реализовать алгоритм на используемом им языке программирования. Строгий математический анализ и обилие теорем сопровождаются большим количеством иллюстраций, элементарными рассуждениями и простыми приближенными оценками. Широта охвата материала и степень строгости его изложения дают основания считать эту книгу одной из лучших книг, посвященных разработке и анализу алгоритмов.

Издательский дом «Вильямс», 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 220 Глава 8. Сортировка за линейное время
    • 221 8.1 Нижние оценки алгоритмов сортировки
      • 221 Модель дерева решений
      • 222 Нижняя оценка для наихудшего случая
      • 223 Упражнения
    • 224 8.2 Сортировка подсчетом
      • 226 Упражнения
    • 226 8.3 Поразрядная сортировка
      • 230 Упражнения
    • 230 8.4 Карманная сортировка
      • 234 Упражнения
    • 234 Задачи
    • 238 Заключительные замечания
  • 240 Глава 9. Медианы и порядковые статистики
    • 241 9.1 Минимум и максимум
      • 241 Одновременный поиск минимума и максимума
      • 242 Упражнения
    • 243 9.2 Выбор в течение линейного ожидаемого времени
      • 247 Упражнения
    • 247 9.3 Алгоритм выбора с линейным временем работы в наихудшем случае
      • 250 Упражнения
    • 252 Задачи
    • 254 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 336 Глава 13. Красно-черные деревья
    • 336 13.1 Свойства красно-черных деревьев
      • 339 Упражнения
    • 340 13.2 Повороты
      • 341 Упражнения
    • 342 13.3 Вставка
      • 350 Анализ
      • 350 Упражнения
    • 351 13.4 Удаление
      • 356 Анализ
      • 356 Упражнения
    • 357 Задачи
    • 364 Заключительные замечания
  • 365 Глава 14. Расширение структур данных
    • 366 14.1 Динамические порядковые статистики
      • 367 Выборка элемента с заданным рангом
      • 368 Определение ранга элемента
      • 369 Поддержка размера поддеревьев
      • 371 Упражнения
    • 372 14.2 Расширение структур данных
      • 373 Расширение красно-черных деревьев
      • 374 Упражнения
    • 375 14.3 Деревья отрезков
      • 380 Упражнения
    • 381 Задачи
    • 382 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 644 Глава 23. Минимальные остовные деревья
    • 645 23.1 Построение минимального остовного дерева
      • 649 Упражнения
    • 651 23.2 Алгоритмы Крускала и Прима
      • 651 Алгоритм Крускала
      • 653 Алгоритм Прима
      • 656 Упражнения
    • 658 Задачи
    • 661 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 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 Заключительные замечания
  • 1257 Библиография
  • 1277 Предметный указатель

Инструкция как скачать книгу Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн: Алгоритмы. Построение и анализ в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.
Алгоритмы. Построение и анализ
Рейтинг книги:
5 голосов
227

Поиск книг:




При поиске учитываются только слова, длина которых больше 3-х символов.

Статистика: