Алгоритмы - Разработка и применение - Джон Клейнберг 2016 год
Глава 1. Введение: некоторые типичные задачи
1.1. Первая задача: устойчивые паросочетания
Глава 2. Основы анализа алгоритмов
2.1. Вычислительная разрешимость
2.2. Асимптотический порядок роста
2.3. Реализация алгоритма устойчивых паросочетаний со списками и массивами
2.4. Обзор типичных вариантов времени выполнения
2.5. Более сложная структура данных: приоритетная очередь
Глава 3. Графы
3.1. Основные определения и применения
3.2. Связность графа и обход графа
3.3. Реализация перебора графа с использованием очередей и стеков
3.4. Проверка двудольности: практическое применение поиска в ширину
3.5. Связность в направленных графах
3.6. Направленные ациклические графы и топологическое упорядочение
Глава 4. Жадные алгоритмы
4.1. Интервальное планирование: жадный алгоритм опережает
4.2. Планирование для минимизации задержки: метод замены
4.3. Оптимальное кэширование: более сложный пример замены
4.5. Задача нахождения минимального остовного дерева
4.6. Реализация алгоритма Крускала: структура Union-Find
4.8. Коды Хаффмана и сжатие данных
4.9. Ориентированные деревья с минимальном стоимостью: многофазный жадный алгоритм
Глава 5. Разделяй и властвуй
5.1. Первое рекуррентное отношение: алгоритм сортировки слиянием
5.2. Другие рекуррентные отношения
5.4. Поиск ближайшей пары точек
5.6. Свертки и быстрое преобразование Фурье
Глава 6. Динамическое программирование
6.1. Взвешенное интервальное планирование: рекурсивная процедура
6.2. Принципы динамического программирования: мемоизация или итерации с подзадачами
6.3. Сегментированные наименьшие квадраты: многовариантный выбор
6.4. Задача о сумме подмножеств и задача о рюкзаке: добавление переменной
6.5. Вторичная структура РНК: динамическое программирование по интервалам
6.6. Выравнивание последовательностей
6.7. Выравнивание последовательностей в линейном пространстве по принципу «разделяй и властвуй»
6.9. Кратчайшие пути и дистанционно-векторные протоколы
6.10. Отрицательные циклы в графе
Глава 7. Нахождение потока в сети
7.1. Задача о максимальном потоке и алгоритм Форда-Фалкерсона
7.2. Максимальные потоки и минимальные разрезы
7.3. Выбор хороших увеличивающих путей
7.4. Алгоритм проталкивания предпотока
7.5. Первое применение: задача о двудольном паросочетании
7.6. Непересекающиеся пути в направленных и ненаправленных графах
7.7. Расширения задачи о максимальном потоке
7.9. Планирование авиаперелетов
7.13. Добавление стоимостей в задачу паросочетаний
Глава 8. NP-полнота и вычислительная неразрешимость
8.2. Сведение с применением «регуляторов»: задача выполнимости
8.3. Эффективная сертификация и определение NP
8.10. Частичная классификация сложных задач
Глава 9. PSPACE: класс задач за пределами NP
9.2. Некоторые сложные задачи из PSPACE
9.3. Решение задач с кванторами и игровых задач в полиномиальном пространстве
9.4. Решение задачи построения плана с полиномиальным пространством
9.5. Доказательство PSPACE-полноты задач
Глава 10. Расширение пределов разрешимости
10.1. Поиск малых вершинных покрытий
10.2. Решение NP-сложных задач для деревьев
10.4. Декомпозиция графа в дерево
10.5. Построение древовидной декомпозиции
Глава 11. Аппроксимирующие алгоритмы
11.1. Жадные алгоритмы и ограничения оптимума: задача распределения нагрузки
11.3. Покрытие множества: обобщенная жадная эвристика
11.4. Метод назначения цены: вершинное покрытие
11.5. Максимизация методом назначения цены: задача о непересекающихся путях
11.6. Линейное программирование и округление: применение к задаче о вершинном покрытии
11.7. Снова о распределении нагрузки: более сложное применение LP
11.8. Аппроксимации с произвольной точностью: задача о рюкзаке
Глава 12. Локальный поиск
12.1. Задача оптимизации в перспективе
12.2. Алгоритм Метрополиса и имитация отжига
12.3. Применение локального поиска в нейронных сетях Хопфилда
12.4. Аппроксимация задачи о максимальном разрезе с применением локального поиска
12.5. Выбор соседского отношения
12.6. Классификация на базе локального поиска
12.7. Динамика наилучших ответов и равновесия Нэша
Глава 13. Рандомизированные алгоритмы
13.1. Первое применение: разрешение конфликтов
13.2. Нахождение глобального минимального разреза
13.3. Случайные переменные и ожидания
13.4. Рандомизированный аппроксимирующий алгоритм для задачи MAX 3-SAT
13.5. Рандомизация принципа «разделяй и властвуй»: нахождение медианы и быстрая сортировка
13.6. Хеширование: рандомизированная реализация словарей
13.7. Нахождение ближайшей пары точек: рандомизированный метод
13.8. Рандомизация кэширования