загрузка...

АЛГОРИТМЫ - Разработка и применение - 2016 год

Предисловие

Глава 1. Введение: некоторые типичные задачи

1.1. Первая задача: устойчивые паросочетания

1.2. Пять типичных задач

Упражнения с решениями

Глава 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.4. Кратчайшие пути в графе

4.5. Задача нахождения минимального остовного дерева

4.6. Реализация алгоритма Крускала: структура Union-Find

4.7. Кластеризация

4.8. Коды Хаффмана и сжатие данных

4.9. Ориентированные деревья с минимальном стоимостью: многофазный жадный алгоритм

Упражнения с решениями

Глава 5. Разделяй и властвуй

5.1. Первое рекуррентное отношение: алгоритм сортировки слиянием

5.2. Другие рекуррентные отношения

5.3. Подсчет инверсий

5.4. Поиск ближайшей пары точек

5.5. Целочисленное умножение

5.6. Свертки и быстрое преобразование Фурье

Упражнения с решениями

Глава 6. Динамическое программирование

6.1. Взвешенное интервальное планирование: рекурсивная процедура

6.2. Принципы динамического программирования: мемоизация или итерации с подзадачами

6.3. Сегментированные наименьшие квадраты: многовариантный выбор

6.4. Задача о сумме подмножеств и задача о рюкзаке: добавление переменной

6.5. Вторичная структура РНК: динамическое программирование по интервалам

6.6. Выравнивание последовательностей

6.7. Выравнивание последовательностей в линейном пространстве по принципу «разделяй и властвуй»

6.8. Кратчайшие пути в графе

6.9. Кратчайшие пути и дистанционно-векторные протоколы

6.10. Отрицательные циклы в графе

Упражнения с решениями

Глава 7. Нахождение потока в сети

7.1. Задача о максимальном потоке и алгоритм Форда-Фалкерсона

7.2. Максимальные потоки и минимальные разрезы

7.3. Выбор хороших увеличивающих путей

7.4. Алгоритм проталкивания предпотока

7.5. Первое применение: задача о двудольном паросочетании

7.6. Непересекающиеся пути в направленных и ненаправленных графах

7.7. Расширения задачи о максимальном потоке

7.8. Планирование опроса

7.9. Планирование авиаперелетов

7.10. Сегментация изображений

7.11. Выбор проекта

7.12. Выбывание в бейсболе

7.13. Добавление стоимостей в задачу паросочетаний

Упражнения с решениями

Глава 8. NP-полнота и вычислительная неразрешимость

8.1. Полиномиальное сведение

8.2. Сведение с применением «регуляторов»: задача выполнимости

8.3. Эффективная сертификация и определение NP

8.4. NР-полные задачи

8.5. Задачи упорядочения

8.6. Задачи о разбиении

8.7. Задача о раскраске графа

8.8. Численные задачи

8.9. Co-NP и асимметрия NP

8.10. Частичная классификация сложных задач

Упражнения с решениями

Глава 9. PSPACE: класс задач за пределами NP

9.1. PSPACE

9.2. Некоторые сложные задачи из PSPACE

9.3. Решение задач с кванторами и игровых задач в полиномиальном пространстве

9.4. Решение задачи построения плана с полиномиальным пространством

9.5. Доказательство PSPACE-полноты задач

Упражнения с решениями

Глава 10. Расширение пределов разрешимости

10.1. Поиск малых вершинных покрытий

10.2. Решение NP-сложных задач для деревьев

10.3. Раскраска множества дуг

10.4. Декомпозиция графа в дерево

10.5. Построение древовидной декомпозиции

Упражнения с решениями

Глава 11. Аппроксимирующие алгоритмы

11.1. Жадные алгоритмы и ограничения оптимума: задача распределения нагрузки

11.2. Задача о выборе центров

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. Рандомизация кэширования

13.9. Границы Чернова

13.10. Распределение нагрузки

13.11. Маршрутизация пакетов

13.12. Основные вероятностные определения

Упражнения с решениями

Эпилог: алгоритмы, которые работают бесконечно


загрузка...
загрузка...