Книга является наиболее полным руководством по разработке эффективных алгоритмов. Первая часть книги содержит практические рекомендации по разработке алгоритмов: приводятся основные понятия, дается анализ алгоритмов, рассматриваются типы структур данных, основные алгоритмы сортировки, операции обхода графов и алгоритмы для работы со взвешенными графами, примеры использования комбинаторного поиска, эвристических методов и динамического программирования. Вторая часть книги содержит обширный список литературы и каталог из 75 наиболее распространенных алгоритмических задач, для которых перечислены существующие программные реализации. Приведены многочисленные примеры задач.
Книгу можно использовать в качестве справочника по алгоритмам для программистов, исследователей и в качестве учебного пособия для студентов соответствующих специальностей.
Предисловие Читателю Преподавателю Благодарности Ограничение ответственности ЧАСТЬ I. ПРАКТИЧЕСКАЯ РАЗРАБОТКА АЛГОРИТМОВ Глава 1. Введение в разработку алгоритмов 1.1. Оптимизация маршрута робота 1.2. Задача календарного планирования 1.3. Обоснование правильности алгоритмов 1.4. Моделирование задачи 1.5. Истории из жизни 1.6. История из жизни. Моделирование проблемы ясновидения 1.7. Упражнения Глава 2. Анализ алгоритмов 2.1. Модель вычислений RAM 2.2. Асимптотические обозначения 2.3. Скорость роста и отношения доминирования 2.4. Работа с асимптотическими обозначениями 2.4.1. Сложение функций 2.4.2. Умножение функций 2.5. Оценка эффективности 2.6. Логарифмы и их применение 2.7. Свойства логарифмов 2.8. История из жизни. Загадка пирамид 2.9. Анализ высшего уровня 2.10. Упражнения Глава 3. Структуры данных 3.1. Смежные и связные структуры данных 3.2. Стеки и очереди 3.3. Словари 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. Сортировка слиянием. Метод "разделяй и властвуй" 4.6. Быстрая сортировка. Рандомизированная версия 4.7. Сортировка распределением. Метод блочной сортировки 4.8. История из жизни. Адвокат Скиена 4.9. Двоичный поиск и связанные с ним алгоритмы 4.10. Метод "разделяй и властвуй" 4 11. Упражнения Глава 5. Обход графов 5.1 Разновидности графов 5.2. Структуры данных для графов 5.3. История из жизни. Жертва закона Мура 5.4 История из жнзни. Создание графа 5.5. Обход графа 5.6. Обход в ширину 5.7. Применение обхода в ширину 5.8. Обход в глубину 5.9. Применение обхода в глубину 5.10. Обход в глубину ориентированных графов 5.11. Упражнения Глава 6. Алгоритмы для работы со взвешенными графами 6.1. Минимальные остовные деревья 6.2. История из жизни. И все на свете только сети 6.3. Поиск кратчайшего пути 6.4. История из жизни. Печатаем с помощью номеронабирателя 6.5. Потоки в сетях и паросочетание в двудольных графах 6.6. Разрабатывайте не алгоритмы, а графы 6.7. Упражнения Глава 7. Комбинаторный поиск и эвристические методы 7.1. Перебор с возвратом 7.2. Отсечение вариантов поиска 7.3. Судоку 7.4. История из жизни. Покрытие шахматной доски 7.5. Эвристические методы перебора 7.6. История из жизни. Только это не радио 7.7. История из жизни. Отжиг массивов 7.8. Другие эвристические методы поиска 7.9. Параллельные алгоритмы 7.10. История из жизни. "Торопиться в никуда" 7.11. Упражнения Глава 8. Динамическое программирование 8.1. Кэширование и вычисления 8.2. Поиск приблизительно совпадающих строк 8.3. Самая длинная возрастающая последовательность 8.4. История из жизни. Эволюция омара 8.5. Задача разбиения 8.6. Синтаксический разбор 8.7. Ограничения динамического программирования. Задача коммивояжера 8.8. История из жизни. Динамическое программирование и язык Prolog 8.9. История из жизни. Сжатие текста для штрих-кодов 8.10. Упражнения Глава 9. Трудно решаемые задачи и аппроксимирующие алгоритмы 9.1. Сведение задач 9.2. Сведение для создания новых алгоритмов 9.3. Простые примеры сведения сложных задач 9.4. Задача выполнимости булевых формул 9.5. Нестандартные сведения 9.6. Искусство доказательства сложности 9.7. История из жизни. Наперегонки со временем 9.8. История из жизни. Полный провал 9.9. Сравнение классов сложности Р и NP 9.10. Решение NP-полных задач 9.11. Упражнения Глава 10. Как разрабатывать алгоритмы ЧАСТЬ II. КАТАЛОГ АЛГОРИТМИЧЕСКИХ ЗАДАЧ Глава 11. Описание каталога Глава 12. Структуры данных 12.1. Словарь 12.2. Очереди с приоритетами 12.3. Суффиксные деревья и массивы 12.4. Графы 12.5. Множества 12.6. Kd-деревья Глава 13. Числепиые задачи 13.1. Решение системы линейных уравнений 13.2. Уменьшение ширины ленты матрицы 13.3. Умножение матриц 13.4. Определители и перманенты 13.5. Условная и безусловная оптимизация 13.6. Линейное программирование 13.7. Генерирование случайных чисел 13.8. Разложение на множители и проверка чисел на простоту 13.9. Арифметика произвольной точности 13.10. Задача о рюкзаке 13.11. Дискретное преобразование Фурье Глава 14. Комбинаторные задачи 14.1. Сортировка 14.2. Поиск 14.3. Поиск медианы и выбор элементов 14.4. Генерирование перестановок 14.5. Генерирование подмножеств 14.6. Генерирование разбиений 14.7. Генерирование графов 14.8. Календарные вычисления 14.9. Календарное планирование 14.10. Выполнимость Глава 15. Задачи на графах с полиномиальным временем исполнения 15.1. Компоненты связности 15.2. Топологическая сортировка 15.3. Минимальные остовные деревья 15.4. Поиск кратчайшего пути 15.5. Транзитивное замыкание и транзитивная редукция 15.6. Паросочетание 15.7. Задача поиска эйлерова цикла и задача китайского почтальона 15.8. Реберная и вершинная связность 15.9. Потоки в сети 15.10. Рисование графов 15.11. Рисование деревьев 15.12. Планарность Глава 16. Сложные задачи на графах 16.1. Задача о клике 16.2. Независимое множество 16.3. Вершинное покрытие 16.4. Задача коммивояжера 16.5. Гамильтонов цикл 16 6. Разбиение графов 16.7. Вершинная раскраска 16.8. Реберная раскраска 16.9. Изоморфизм графов 16.10. Дерево Штейнера 16.11. Разрывающее множество ребер или вершин Глава 17. Вычислительная геометрия 17.1. Элементарные задачи вычислительной геометрии 17.2. Выпуклая оболочка 17.3. Триангуляция 17.4. Диаграммы Вороного 17.5. Поиск ближайшей точки 17.6. Поиск в области 17.7. Местоположение точки 17.8. Выявление пересечений 17.9. Разложение по контейнерам 17.10. Преобразование к срединной оси 17.11. Разбиение многоугольника на части 17.12. Упрощение многоугольников 17.13. Выявление сходства фигур 17.14. Планирование перемещений 17.15. Конфигурации прямых 17.16. Сумма Минковского Глава 18. Множества и строки 18.1. Поиск покрытия множества 18.2. Задача укладки множества 18.3. Сравнение строк 18.4. Нечеткое сравнение строк 18.5. Сжатие текста 18.6. Криптография 18.7. Минимизация конечного автомата 18.8. Максимальная общая подстрока 18.9. Поиск минимальной обшей надстроки Глава 19. Ресурсы 19.1. Программные системы 19.2. Источники данных 19.3. Библиографические ресурсы 19.4. Профессиональные консалтинговые услуги Список литературы Предметный указатель
Автор: Скиена С. Язык: Русский Издательство: СПб.: БХВ-Петербург Жанр: Информатика Год: 2011 Формат: djvu Размер: 10 mb
