- Артикул:00-01027143
- Автор: Стивен С. Скиена
- ISBN: 978-5-9775-0560-4
- Тираж: 1000 экз.
- Обложка: Твердый переплет
- Издательство: БХВ-Петербург (все книги издательства)
- Город: СПб
- Страниц: 720
- Формат: 70х100 1/16
- Год: 2019
- Вес: 1480 г
Развернуть ▼
Книга является наиболее полным руководством по разработке эффективных алгоритмов.
Первая часть книги содержит практические рекомендации по разработке алгоритмов: приводятся основные понятия, дается анализ алгоритмов, рассматриваются типы структур данных, основные алгоритмы сортировки, операции обхода графов и алгоритмы для работы со взвешенными графами, примеры использования комбинаторного поиска, эвристических методов и динамического программирования.
Вторая часть книги содержит обширный список литературы и каталог из 75 наиболее распространенных алгоритмических задач, для которых перечислены существующие программные реализации.
Приведены многочисленные примеры задач.
Книгу можно использовать в качестве справочника по алгоритмам для программистов, исследователей и в качестве учебного пособия для студентов соответствующих специальностей.
Для программистов, исследователей и студентов
Оглавление
Предисловие
Читателю
Преподавателю
Благодарности
Ограничение ответственности
Часть I. Практическая разработка алгоритмов
Глава 1. Введение в разработку алгоритмов
1.1. Оптимизация маршрута робота
1.2. Задача календарного планирования
1.3. Обоснование правильности алгоритмов
1.3.1. Представление алгоритмов
1.3.2. Задачи и свойства
1.3.3. Демонстрация неправильности алгоритма
1.3.4. Индукция и рекурсия
1.3.5. Суммирование
1.4. Моделирование задачи
1.4.1. Комбинаторные объекты
1.4.2. Рекурсивные объекты
1.5. Истории из жизни
1.6. История из жизни. Моделирование проблемы ясновидения
1.7. Упражнения
Глава 2. Анализ алгоритмов
2.1. Модель вычислений RAM
2.1.1. Анализ сложности наилучшего, наихудшего и среднего случая.
2.2. Асимптотические обозначения
2.3. Скорость роста и отношения доминирования
2.3.1. Отношения доминирования
2.4. Работа с асимптотическими обозначениями
2.4.1. Сложение функций
2.4.2. Умножение функций
2.5. Оценка эффективности
2.5.1. Сортировка методом выбора
2.5.2. Сортировка вставками
2.5.3. Сравнение строк
2.5.4. Умножение матриц
2.6. Логарифмы и их применение
2.6.1. Логарифмы и двоичный поиск
2.6.2. Логарифмы и деревья
2.6.3. Логарифмы и биты
2.6.4. Логарифмы и умножение
2.6.5. Быстрое возведение в степень
2.6.6. Логарифмы и сложение
2.6.7. Логарифмы и система уголовного судопроизводства
2.7. Свойства логарифмов
2.8. История из жизни. Загадка пирамид
2.9. Анализ высшего уровня (*)
2.9.1. Малораспространенные функции
2.9.2. Пределы и отношения доминирования
2.10. Упражнения
Глава 3. Структуры данных
3.1. Смежные и связные структуры данных
3.1.1. Массивы
3.1.2. Указатели и связные структуры данных
3.1.3. Сравнение
3.2. Стеки и очереди
3.3. Словари
3.4. Двоичные деревья поиска
3.4.1. Реализация двоичных деревьев
3.4.2. Эффективность двоичных деревьев поиска
3.4.3. Сбалансированные деревья поиска
3.5. Очереди с приоритетами
3.6. История из жизни. Триангуляция
3.7. Хэширование и строки
3.7.1. Коллизии
3.7.2. Эффективный метод поиска строк посредством хэширования
3.7.3. Выявление дубликатов с помощью хэширования
3.8. Специализированные структуры данных
3.9. История из жизни. Геном человека
3.10. Упражнения
Глава 4. Сортировка и поиск
4.1. Применение сортировки
4.2. Практические аспекты сортировки
4.3. Пирамидальная сортировка
4.3.1. Пирамиды
4.3.2. Создание пирамиды
4.3.3. Наименьший элемент пирамиды
4.3.4. Быстрый способ создания пирамиды (*)
4.3.5. Сортировка вставками
4.4. История из жизни. Билет на самолет
4.5. Сортировка слиянием. Метод "разделяй и властвуй"
4.6. Быстрая сортировка. Рандомизированная версия
4.6.1. Ожидаемое время исполнения алгоритма быстрой сортировки
4.6.2. Рандомизированные алгоритмы
4.6.3. Действительно ли алгоритм быстрой сортировки работает быстро?
4.7. Сортировка распределением. Метод блочной сортировки
4.7.1. Нижние пределы для сортировки
4.8. История из жизни. Адвокат Скиена
4.9. Двоичный поиск и связанные с ним алгоритмы
4.9.1. Частота вхождения элемента
4.9.2. Односторонний двоичный поиск
4.9.3. Корни числа
4.10. Метод "разделяй и властвуй"
4.10.1. Рекуррентные соотношения
4.10.2. Рекуррентные соотношения метода "разделяй и властвуй"
4.10.3. Решение рекуррентных соотношений типа "разделяй и властвуй"
4.11. Упражнения
Глава 5. Обход графов
5.1. Разновидности графов
5.1.1. Граф дружеских отношений
5.2. Структуры данных для графов
5.3. История из жизни. Жертва закона Мура
5.4. История из жизни. Создание графа
5.5. Обход графа
5.6. Обход в ширину
5.6.1. Применение обхода
5.6.2. Поиск путей
5.7. Применение обхода в ширину
5.7.1. Компоненты связности
5.7.2. Раскраска графов двумя цветами
5.8. Обход в глубину
5.9. Применение обхода в глубину
5.9.1. Поиск циклов
5.9.2. Шарниры графа
5.10. Обход в глубину ориентированных графов
5.10.1. Топологическая сортировка
5.10.2. Сильно связные компоненты
5.11. Упражнения
Глава 6. Алгоритмы для работы со взвешенными графами
6.1. Минимальные остовные деревья
6.1.1. Алгоритм Прима
6.1.2. Алгоритм Крускала
6.1.3. Поиск-объединение
6.1.4. Разновидности остовных деревьев
6.2. История из жизни. И все на свете только сети
6.3. Поиск кратчайшего пути
6.3.1. Алгоритм Дейкстры
6.3.2. Кратчайшие пути между всеми парами вершин
6.3.3. Транзитивное замыкание
6.4. История из жизни. Печатаем с помощью номеронабирателя
6.5. Потоки в сетях и паросочетание в двудольных графах
6.5.1. Паросочетание в двудольном графе
6.5.2. Вычисление потоков в сети
6.6. Разрабатывайте не алгоритмы, а графы
6.7. Упражнения
Глава 7. Комбинаторный поиск и эвристические методы
7.1. Перебор с возвратом
7.1.1. Генерирование всех подмножеств
7.1.2. Генерирование всех перестановок
7.1.3. Генерирование всех путей в графе
7.2. Отсечение вариантов поиска
7.3. Судоку
7.4. История из жизни. Покрытие шахматной доски
7.5. Эвристические методы перебора
7.5.1. Произвольная выборка
7.5.2. Локальный поиск
7.5.3. Имитация отжига
7.5.4. Применение метода имитации отжига
7.6. История из жизни. Только это не радио
7.7. История из жизни. Отжиг массивов
7.8. Другие эвристические методы поиска
7.9. Параллельные алгоритмы
7.10. История из жизни. ’’Торопиться в никуда”
7.11. Упражнения
Глава 8. Динамическое программирование
8.1. Кэширование и вычисления
8.1.1. Генерирование чисел Фибоначчи методом рекурсии
8.1.2. Генерирование чисел Фибоначчи посредством кэширования
8.1.3. Генерирование чисел Фибоначчи посредством динамического программирования
8.1.4. Биномиальные коэффициенты
8.2. Поиск приблизительно совпадающих строк
8.2.1. Применение рекурсии для вычисления расстояния редактирования
8.2.2. Применение динамического программирования для вычисления расстояния редактирования
8.2.3. Восстановление пути
8.2.4. Разновидности расстояния редактирования
8.3. Самая длинная возрастающая последовательность
8.4. История из жизни. Эволюция омара
8.5. Задача разбиения
8.6. Синтаксический разбор
8.6.1. Триангуляция с минимальным весом
8.7. Ограничения динамического программирования. Задача коммивояжера
8.7.1. Вопрос правильности алгоритмов динамического программирования.
8.7.2. Эффективность алгоритмов динамического программировгшия
8.8. История из жизни. Динамическое программирование и язык Prolog
8.9. История из жизни. Сжатие текста для штрих-кодов
8.10. Упражнения
Глава 9. Труднорешаемые задачи и аппроксимирующие алгоритмы
9.1. Сведение задач
9.1.1. Ключевая идея
9.1.2. Задачи разрешимости
9.2. Сведение для создания новых алгоритмов
9.2.1. Поиск ближайшей пары
9.2.2. Максимальная возрастающая подпоследовательность
9.2.3. Наименьшее общее кратное
9.2.4. Выпуклая оболочка (*)
9.3. Простые примеры сведения сложных задач
9.3.1. Гамильтонов цикл
9.3.2. Независимое множество и вершинное покрытие
9.3.3. Задача о клике
9.4. Задача выполнимости булевых формул
9.4.1. Задача выполнимости в 3-конъюнктивной нормальной форме
9.5. Нестандартные сведения
9.5.1. Целочисленное программирование
9.5.2. Вершинное покрытие
9.6. Искусство доказательства сложности
9.7. История из жизни. Наперегонки со временем
9.8. История из жизни. Полный провал
9.9. Сравнение классов сложности Р и NP
9.9.1. Верификация решения и поиск решения
9.9.2. Классы сложности Р и NP
9.9.3. Почему задача выполнимости является самой сложной из всех сложных задач?
9.9.4. NP-сложность по сравнению с NP-полнотой
9.10. Решение NP-полных задач
9.10.1. Аппроксимация вершинного покрытия
9.10.2. Задача коммивояжера в евклидовом пространстве
9.10.3. Максимальный бесконтурный подграф
9.10.4. Задача о покрытии множества
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.1.1. Библиотека LEDA
19.1.2. Библиотека CGAL
19.1.3. Библиотека Boost
19.1.4. Библиотека GOBLIN
19.1.5. Библиотека Netlib
19.1.6. Коллекция алгоритмов ассоциации ACM
19.1.7. Сайты SourceForge и CPAN
19.1.8. Система Stanford GraphBase
19.1.9. Пакет Combinatorica
19.1.10. Программы из книг
19.2. Источники данных
19.3. Библиографические ресурсы
19.4. Профессиональные консалтинговые услуги
Список литературы
Предметный указатель
Рекомендуем
