Содержание.
Предисловие ко второму изданию
Изменения во втором издании
Целевая аудитория
Соглашения, используемые в данной книге
Использование примеров кода
Благодарности Об авторах
06 изображении на обложке
Ждем ваших отзывов!
Глава 1. Мысли алгоритмически
Понимание проблемы
Прямое решение
Интеллектуальные подходы
Жадный подход
Разделяй и властвуй
Параллельное вычисление
Приближение
Обобщение
Резюме
Глава 2. Математика алгоритмов
Размер экземпляра задачи
Скорость роста функций
Анализ наилучшего, среднего и наихудшего случаев
Наихудший случай
Средний случай
Наилучший случай
Нижняя и верхняя границы
Семейства производительности
Константное поведение
Логарифмическое поведение
Сублинейное поведение
Линейная производительность
Линейно-логарифмическая производительность
Квадратичная производительность
Менее очевидные производительности
Экспоненциальная производительность
Резюме по асимптотическому росту
Эталонные операции
Глава 3. Строительные блоки алгоритмов
Формат представления алгоритма
Название и краткое описание
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Формат шаблона псевдокода
Формат эмпирических оценок
Вычисления с плавающей точкой
Производительность
Ошибка округления
Сравнение значений с плавающей точкой
Специальные значения
Пример алгоритма
Название и краткое описание
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Распространенные подходы
Жадная стратегия
Разделяй и властвуй
Динамическое программирование
Глава 4. Алгоритмы сортировки
Терминология
Представление
Сравниваемость элементов
Устойчивая сортировка
Критерии выбора алгоритма сортировки
Сортировки перестановкой
Сортировка вставками
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Сортировка выбором
Пирамидальная сортировка
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Сортировка, основанная на разбиении
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Сортировка без сравнений
Блочная сортировка
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Сортировка с использованием дополнительной памяти
Сортировка слиянием
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Результаты хронометража для строк
Анализ методов
Глава 5. Поиск
Последовательный поиск
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Бинарный поиск
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Поиск на основе хеша
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Фильтр Блума
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Бинарное дерево поиска
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Глава 6. Алгоритмы на графах
Графы
Проектирование структуры данных
Поиск в глубину
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Поиск в ширину
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Кратчайший путь из одной вершины
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма
Алгоритм Дейкстры для плотных графов
Вариации алгоритма
Сравнение вариантов поиска кратчайших путей из одной вершины
Данные хронометража
Плотные графы
Разреженные графы
Кратчайшие пути между всеми парами вершин
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма
Алгоритмы построения минимального остовного дерева
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Заключительные мысли о графах
Вопросы хранения
Анализ графа
Глава 7. Поиск путей в ИИ
Дерево игры
Функции статических оценок
Концепции поиска путей
Представление состояния
Вычисление доступных ходов
Максимальная глубина расширения Minimax
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма NegMax
Реализация алгоритма
Анализ алгоритма
AlphaBeta
Реализация алгоритма
Анализ алгоритма
Деревья поиска
Эвристические функции длины пути
Поиск в глубину
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Поиск в ширину
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
A*Search
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Сравнение алгоритмов поиска в дереве
Глава 8. Алгоритмы транспортных сетей
Транспортная сеть
Максимальный поток
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма
Оптимизация
Связанные алгоритмы
Паросочетания в двудольном графе
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма
Размышления об увеличивающих путях
Поток минимальной стоимости
Перегрузка
Реализация алгоритма
Перевозка
Реализация алгоритма
Назначение
Реализация алгоритма
Линейное программирование
Глава 9. Вычислительная геометрия
Классификация задач
Входные данные
Вычисления
Природа задачи
Предположения
Выпуклая оболочка
Сканирование выпуклой оболочки
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Вычисление пересечения отрезков LineSweep
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Диаграмма Вороного
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма
Глава 10. Пространственные древовидные структуры
Запросы ближайшего соседа
Запросы диапазонов
Запросы пересечения
Структуры пространственных деревьев
k-d-деревья
Дерево квадрантов
R-дерево
Задача о ближайшем соседе
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма Анализ алгоритма
Вариации алгоритма Запрос диапазона
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Деревья квадрантов
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
R-деревья
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Глава 11. Дополнительные категории алгоритмов
Вариации на тему алгоритмов
Приближенные алгоритмы
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Параллельные алгоритмы
Вероятностные алгоритмы
Оценка размера множества
Оценка размера дерева поиска
Глава 12. Эпилог: алгоритмические принципы
Используемые данные
Разложение задачи на задачи меньшего размера
Выбор правильной структуры данных
Пространственно-временной компромисс
Построение поиска
Приведение задачи к другой задаче
Тестировать алгоритмы труднее, чем писать
Допустимость приближенных решений
Повышение производительности с помощью параллелизма
Приложение. Хронометраж
Статистические основы Пример
Решение для java Решение для Linux
Хронометраж с использованием Python
Вывод результатов
Точность
Техническая литература
Предметный указатель
Добавить комментарий