Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 2
Текст из файла (страница 2)
Красно-черные деревья 13.1 Свойства красно-черных деревьев Упражнения 13.2 Повороты Упражнения 13.3 Вставка Анализ Упражнения 13.4 Удаление Анализ Упражнения Задачи Заключительные замечания 1!зава 14. Расширение структур данных 14.1 Динамические порядковые статистики Выборка элемента с заданным рангом Определение ранга элемента Поддержка размера поддеревьев Упражнения 14.2 Расширение структур данных Расширение красно-черных деревьев Упражнения 14.3 Деревья отрезков Упражнения Задачи Заключительные замечания Часть 1У. Усовершенствованные методы разработки н анализа Введение Глава 15. Динамическое программирование 15.1 Расписание работы конвейера Первый этап: структура самой быстрой сборки Второй этап: рекурсивное решение 336 336 339 340 341 342 350 350 351 356 356 357 364 365 366 367 368 369 371 372 373 374 375 380 381 382 14 Содержание Третий этап: вычисление минимальных промежутков времени Четвертый этап: построение самого быстрого пути Упражнения 15.2 Перемножение цепочки матриц Подсчет количества способов расстановки скобок Первый этап: структура оптимальной расстановки скобок Второй этап: рекурсивное решение Третий этап: вычисление оптимальной стоимости Четвертый этап: конструирование оптимального решения Упражнения 15.3 Элементы динамического программирования Оптимальная подструктура Перекрытие вспомогательных задач Построение оптимального решения Запоминание Упражнения 15.4 Самая длинная общая подпоследовательность Этап 1: характеристика самой длинной общей подпоследовательности Этап 2: рекурсивное решение Этап 3: вычисление длины самой длинной общей подпоследовательности Этап 4: построение самой длинной общей подпоследовательности Улучшение кода Упражнения 15.5 Оптимальные бинарные деревья поиска Этап 1: структура оптимального бинарного дерева поиска Этап 2: рекурсивное решение Этап 3: вычисление математического ожидания стоимости поиска в оптимальном бинарном дереве поиска Упражнения Задачи Заключительные замечания Глава 16.
Жадные алгоритмы 16.1 Задача о выборе процессов Оптимальная подструктура задачи о выборе процессов Рекурсивное решение 393 394 395 395 397 398 399 400 403 404 404 405 411 414 414 417 418 419 421 422 423 424 425 425 429 430 431 433 434 440 442 443 444 446 Содержание 15 Преобразование решения динамического программирования в жадное решение Рекурсивный жадный алгоритм Итерационный жадный алгоритм Упражнения 16.2 Элементы жадной стратегии Свойство жадного выбора Оптимальная подструктура Сравнение жадных алгоритмов и динамического программирования Упражнения 16.3 Коды Хаффмана Префиксные коды Построение кода Хаффмана Корректность алгоритма Хаффмана Упражнения * 16.4 Теоретические основы жадных методов Матроиды Жадные алгоритмы на взвешенном матроиде Упражнения * 16.5 Планирование заданий Упражнения Задачи Заключительные замечания Глава 17.
Амортизационный анализ 17.1 Групповой анализ Стековые операции Приращение показаний бинарного счетчика Упражнения 17.2 Метод бухгалтерского учета Стековые операции Приращение показаний бинарного счетчика Упражнения 17.3 Метод потенциалов Стековые операции Увеличение показаний бинарного счетчика Упражнения 17.4 Динамические таблицы 17.4.1 Расширение таблицы 17.4.2 Расширение и сжатие таблицы 446 449 451 452 453 454 455 456 458 459 460 462 464 466 467 467 470 474 474 478 478 481 482 483 483 485 487 487 489 490 490 491 492 493 494 495 496 499 Содержание 16 504 505 510 Упражнения Задачи Заключительные замечания 511 512 Часть У.
Сложные структуры данных Введение Глава 18. В-деревья Структуры данных во вторичной памяти 18.1 Определение В-деревьев Высота В-дерева Упражнения 18.2 Основные операции с В-деревьями Поиск в В-дереве Создание пустого В-дерева Вставка ключа в В-дерево Упражнения 18.3 Удаление ключа из В-дерева Упражнения Задачи Заключительные замечания йтава 19.
Биномиальиые пирамиды 19.1 Биномиальные деревья и биномиальные пирамиды 19.1.1 Биномиальные деревья 19.1.2 Биномиальные пирамиды Упражнения 19.2 Операции над биномиальными пирамидами Создание новой биномиальной пирамиды Поиск минимального ключа Слияние двух биномиальных пирамид Вставка узла Извлечение вершины с минимальным ключом Уменьшение ключа Удаление ключа Упражнения Задачи Заключительные замечания 515 516 519 521 522 522 522 523 524 528 530 533 533 536 537 539 539 541 543 544 544 544 545 550 551 552 554 554 555 557 Содержание 17 Глава 20.
Фнбоначчиевы пирамиды 20.1 Структура фибоначчиевых пирамид Потенциальная функция Максимальная степень 20.2 Операции над сливаемыми пирамидами Создание новой фибоначчиевой пирамиды Вставка узла Поиск минимального узла Обьединение двух фибоначчиевых пирамид Извлечение минимального узла Упражнения 20.3 Уменьшение ключа и удаление узла Уменьшение ключа Удаление узла Упражнения 20.4 Оценка максимальной степени Упражнения Задачи Заключительные замечания Глава 21. Структуры данных для непересекающихся множеств 21.1 Операции над непересекающимися множествами Приложение структур данных для непересекающихся множеств Упражнения 21.2 Представление непересекающихся множеств с помощью связанных списков Простая реализация объединения Весовая эвристика Упражнения 21.3 Лес непересекающихся множеств Эвристики для повышения эффективности Псевдокоды Влияние эвристик на время работы Упражнения * 21.4 Анализ объединения по рангу со сжатием пути Очень быстро и очень медленно растущая функция Свойства рангов Доказательство границы времени работы Потенциальная функция 558 559 561 562 562 563 563 564 564 565 57! 571 571 575 575 575 578 578 579 581 582 583 584 585 586 587 588 589 589 590 592 592 592 593 594 595 596 Содержание 18 598 601 601 605 607 608 644 645 649 651 651 653 656 658 661 663 664 665 666 Изменения потенциала и амортизированная стоимость операций Упражнения Задачи Заключительные замечания Часть У1.
Алгоритмы для работы с графами Введение Глава 22. Элементарные алгоритмы для работы с графами 22.1 Представление графов Упражнения 22.2 Поиск в ширину Анализ Кратчайшие пути Деревья поиска в ширину Упражнения 22.3 Поиск в глубину Свойства поиска в глубину Классификация ребер Упражнения 22.4 Топологическая сортировка Упражнения 22.5 Сильно связные компоненты Упражнения Задачи Заключительные замечания Глава 23. Минимальные остовные деревья 23.1 Построение минимального остовного дерева Упражнения 23.2 Алгоритмы Крускала и Прима Алгоритм Крускала Алгоритм Прима Упражнения Задачи Заключительные замечания Глава 24.
Кратчайшие пути из одной вершины Варианты Оптимальная структура задачи о кратчайшем пути Ребра с отрицательным весом 609 609 612 613 616 617 620 621 622 626 628 630 632 634 635 640 641 643 Содержание 19 Циклы Представление кратчайших путей Ослабление Свойства кратчайших путей и ослабления Краткое содержание главы 24.1 Алгоритм Беллмана-Форда Упражнения 24.2 Кратчайшие пути из одной вершины в ориентированных ациклических графах Упражнения 24.3 Алгоритм Дейкстры Анализ Упражнения 24.4 Разностные ограничения и кратчайшие пути Линейное программирование Системы разностных ограничений Графы ограничений Решение систем разностиых ограничений Упражнения 24.5 Доказательства свойств кратчайших путей Неравенство треугольника Влияние ослабления на оценки кратчайшего пути Ослабление и деревья кратчайших путей Упражнения Задачи Заключительные замечания Глава 25.
Кратчайшие пути между всеми парами вершин Краткое содержание главы 25.1 Задача о кратчайших путях н умножение матриц Структура кратчайшего пути Рекурсивное решение задачи о кратчайших путях между всеми парами вершин Вычисление весов кратчайших путей в восходящем порядке Улучшение времени работы Упражнения 25.2 Алгоритм Флойда-Варшалла Структура кратчайшего пути Рекурсивное решение задачи о кратчайших путях между всеми парами вершин 667 668 669 671 672 672 676 677 679 680 684 686 687 687 688 690 692 692 694 694 695 697 700 702 706 708 710 711 711 712 712 714 716 718 718 719 20 Содержание Вычисление весов кратчайших путей в восходящем порядке Построение кратчайшего пути Транзитивное замыкание ориентированного графа Упражнения 25.3 Алгоритм Джонсона для разреженных графов Сохранение кратчайших путей Генерация неотрицательных весов путем их изменения Вычисление кратчайших путей между всеми парами вершин Упражнения Задачи Заключительные замечания Глава 26.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
