Алгоритмы

Содержание книги "Алгоритмы "

Предисловие от издательства
Предисловие
Об этой книге
Обязательный минимум
Дополнительные ссылки
Упражнения в этой книге
Стащите эту книгу
Благодарности
Предостережение для преподавателя
Глава 0. Введение
0.1. Что такое алгоритм
0.2. Умножение
0.3. Распределение мест в Конгрессе США
0.4. Отрицательный пример
0.5. Описание алгоритмов
0.6. Анализ алгоритмов
Упражнения
Глава 1. Рекурсия
1.1. Сведéние
1.2. Упрощение и делегирование
1.3. Ханойские башни
1.4. Сортировка слиянием
1.5. Быстрая сортировка
1.6. Шаблон
1.7. Рекурсивные деревья
1.8. Линейный алгоритм выбора
1.9. Быстрое умножение
1.10. Возведение в степень
Упражнения
Глава 2. Поиск с возвратом
2.1. Задача об n ферзях
2.2. Деревья игры
2.3. Задача о сумме подмножеств
2.4. Общий шаблон
2.5. Сегментация текста (Interpunctio Verborum)
2.6. Максимальная возрастающая подпоследовательность
2.7. Максимальная возрастающая подпоследовательность, дубль 2
2.8. Оптимальные двоичные деревья поиска
Упражнения
Глава 3. Динамическое программирование
3.1. Mātrāv.rtta
3.2. Небольшое отступление: еще более быстрое определение чисел Фибоначчи
3.3. Interpunctio verborum redux (И снова о пунктуации)
3.4. Шаблон: интеллектуальная рекурсия
3.5. Внимание: жадность – это глупость
3.6. Максимальная возрастающая подпоследовательность
3.7. Расстояние редактирования
3.8. Задача о сумме подмножеств
3.9. Оптимальные двоичные деревья поиска
3.10. Динамическое программирование для деревьев
Упражнения
Глава 4. Жадные алгоритмы
4.1. Сохранение файлов на магнитной ленте
4.2. Планирование учебных курсов
4.3. Общий шаблон
4.4. Коды Хаффмана
4.5. Задача о стабильных браках
Упражнения
Глава 5. Основные графовые алгоритмы
5.1. Введение и историческая справка
5.2. Основные определения
5.3. Представления и примеры
5.4. Структуры данных
5.5. Поиск в любом направлении
5.6. Важные варианты
5.7. Редукция графа: сплошная заливка
Упражнения
Глава 6. Поиск в глубину
6.1. Обход в прямом и обратном порядке
6.2. Обнаружение циклов
6.3. Топологическая сортировка
6.4. Мемоизация и динамическое программирование
6.5. Сильная связность
6.6. Сильные компоненты за линейное время
Упражнения
Глава 7. Минимальные остовные деревья
7.1. Различные веса ребер
7.2. Единственный алгоритм минимального остовного дерева
7.3. Алгоритм Борувки
7.4. Алгоритм Ярника (Прима)
7.5. Алгоритм Краскала
Упражнения
Глава 8. Кратчайшие пути
8.1. Деревья кратчайшего пути
8.2. Отрицательные ребра
8.3. Единственный алгоритм SSSP
8.4. Невзвешенные графы: поиск в ширину
8.5. Направленный ациклический граф: поиск в глубину
8.6. Поиск по первому наилучшему совпадению: алгоритм Дейкстры
8.7. Ослабление напряжения всех ребер: алгоритм Беллмана–Форда
Упражнения
Глава 9. Кратчайшие пути между всеми парами вершин в графе
9.1. Введение
9.2. Множество отдельных источников
9.3. Изменение весов
9.4. Алгоритм Джонсона
9.5. Динамическое программирование
9.6. Разделяй и властвуй
9.7. Странное умножение матриц
9.8. Алгоритм (Клини–Роя–)Флойда–Уоршелла(–Ингермана)
Упражнения
Глава 10. Максимальные потоки и наименьшие разрезы
10.1. Потоки
10.2. Разрезы
10.3. Теорема о максимальном потоке и наименьшем разрезе (Maxflow-Mincut)
10.4. Алгоритм увеличивающего пути Форда и Фалкерсона
10.5. Объединения и разбиения потоков
10.6. Алгоритмы Эдмондса и Карпа
10.7. Дальнейшее развитие
Упражнения
Глава 11. Приложения потоков и разрезов
11.1. Реберно-непересекающиеся пути
11.2. Пропускные способности вершин и вершинно-непересекающиеся пути
11.3. Задача о паросочетании в двудольном графе
11.4. Выбор кортежа
11.5. Покрытия непересекающихся путей
11.6. Алгоритм исключения для бейсбола
11.7. Выбор проекта
Упражнения
Глава 12. NP-трудность
12.1. Игра, которую невозможно выиграть
12.2. P против NP
12.3. NP-трудная, NP-легкая и NP-полная задача
12.4. Формальные определения (HC SVNT DRACONES – Тут [обитают] драконы)
12.5. Редукции и задача Sat
12.6. 3Sat (от CircuitSat)
12.7. Максимальное независимое множество (от 3Sat)
12.8. Общий шаблон
12.9. Клика и вершинное покрытие (от независимого множества)
12.10. Раскраска графа (от 3Sat)
12.11. Гамильтонов цикл
12.12. Задача о сумме подмножеств (от задачи вершинного покрытия)
12.13. Другие полезные NP-трудные задачи
12.14. Выбор правильной задачи
12.15. Простой пример из реальной жизни
12.16. Что дальше
Упражнения
Предметный указатель
Список алгоритмов на псевдокоде