Алгоритмы. Руководство по разработке. - 2-е изд.

Автор: Скиена С.
Год издания: 2011
Издательство: БХВ-Петербург
Язык: русский
Размер: 11,10 Мб
Страниц: 715
Формат: PDF
ISBN: 798-5-9775-0560-4
Второе издание популярного бестселлера "Алгоритмы. Руководство по разработке" раскрывает тайны проектирования алгоритмов, анализа их действенности и эффективности. Развивая успешную концепцию первого издания, книга является отличным практическим руководством по разработке эффективных алгоритмов, содержит практические упражнения и готовые решения 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.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.4.1. Задача выполнимости в 3-конъюнктивной нормальной форме
9.5. Нестандартные сведения
9.6. Искусство доказательства сложности
9.7. История из жизни. Наперегонки со временем
9.8. История из жизни. Полный провал
9.9. Сравнение классов сложности P и 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. Диаграммы Вороного
175. Поиск ближайшей точки
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. Профессиональные консалтинговые услуги
Список литературы
Предметный указатель