Алгоритмы. Руководство по разработке
Стивен Скиена
Книга является наиболее полным руководством по разработке эффективных алгоритмов. Первая часть книги содержит практические рекомендации по разработке алгоритмов: приводятся основные понятия, дается анализ алгоритмов, рассматриваются типы структур данных, основные алгоритмы сортировки, операции обхода графов и алгоритмы для работы со взвешенными графами, примеры использования комбинаторного поиска, эвристических методов и динамического программирования. Вторая часть книги содержит обширный список литературы и каталог из 75 наиболее распространенных алгоритмических задач, для которых перечислены существующие программные реализации. Приведены многочисленные примеры задач.
Книгу можно использовать в качестве справочника по алгоритмам для программистов, исследователей и в качестве учебного пособия для студентов соответствующих специальностей.
Издательство: БХВ-Петербург, 2011 г.
ISBN 978-5-9775-0560-4, 978-1-84800-069-8
Количество страниц: 720.
Содержание книги «Алгоритмы. Руководство по разработке»:
- 13 Предисловие
- 13 Читателю
- 15 Преподавателю
- 16 Благодарности
- 17 Ограничение ответственности
- 19 ЧАСТЬ I. ПРАКТИЧЕСКАЯ РАЗРАБОТКА АЛГОРИТМОВ
- 21 Глава 1. Введение в разработку алгоритмов
- 22 1.1. Оптимизация маршрута робота
- 26 1.2. Задача календарного планирования
- 29 1.3. Обоснование правильности алгоритмов
- 30 1.3.1. Представление алгоритмов
- 31 1.3.2. Задачи и свойства
- 32 1.3.3. Демонстрация неправильности алгоритма
- 33 1.3.4. Индукция и рекурсия
- 35 1.3.5. Суммирование
- 37 1.4. Моделирование задачи
- 37 1.4.1. Комбинаторные объекты
- 39 1.4.2. Рекурсивные объекты
- 40 1.5. Истории из жизни
- 41 1.6. История из жизни. Моделирование проблемы ясновидения
- 45 1.7. Упражнения
- 49 Глава 2. Анализ алгоритмов
- 49 2.1. Модель вычислений RAM
- 50 2.1.1. Анализ сложности наилучшего, наихудшего и среднего случая
- 52 2.2. Асимптотические обозначения
- 55 2.3. Скорость роста и отношения доминирования
- 56 2.3.1. Отношения доминирования
- 58 2.4. Работа с асимптотическими обозначениями
- 58 2.4.1. Сложение функций
- 58 2.4.2. Умножение функций
- 59 2.5. Оценка эффективности
- 59 2.5.1. Сортировка методом выбора
- 60 2.5.2. Сортировка вставками
- 61 2.5.3. Сравнение строк
- 63 2.5.4. Умножение матриц
- 64 2.6. Логарифмы и их применение
- 64 2.6.1. Логарифмы и двоичный поиск
- 64 2.6.2. Логарифмы и деревья
- 65 2.6.3. Логарифмы и биты
- 65 2.6.4. Логарифмы и умножение
- 66 2.6.5. Быстрое возведение в степень
- 66 2.6.6. Логарифмы и сложение
- 67 2.6.7. Логарифмы и система уголовного судопроизводства
- 68 2.7. Свойства логарифмов
- 69 2.8. История из жизни. Загадка пирамид
- 72 2.9. Анализ высшего уровня (*)
- 73 2.9.1. Малораспространенные функции
- 74 2.9.2. Пределы и отношения доминирования
- 75 2.10. Упражнения
- 49 2.1. Модель вычислений RAM
- 84 Глава 3. Структуры данных
- 84 3.1. Смежные и связные структуры данных
- 85 3.1.1. Массивы
- 86 3.1.2. Указатели и связные структуры данных
- 89 3.1.3. Сравнение
- 90 3.2. Стеки и очереди
- 91 3.3. Словари
- 95 3.4. Двоичные деревья поиска
- 96 3.4.1. Реализация двоичных деревьев
- 100 3.4.2. Эффективность двоичных деревьев поиска
- 101 3.4.3. Сбалансированные деревья поиска
- 102 3.5. Очереди с приоритетами
- 104 3.6. История из жизни. Триангуляция
- 107 3.7. Хэширование и строки
- 108 3.7.1. Коллизии
- 110 3.7.2. Эффективный метод поиска строк посредством хэширования
- 112 3.7.3. Выявление дубликатов с помощью хэширования
- 113 3.8. Специализированные структуры данных
- 114 3.9. История из жизни. Геном человека
- 118 3.10. Упражнения
- 84 3.1. Смежные и связные структуры данных
- 123 Глава 4. Сортировка и поиск
- 123 4.1. Применение сортировки
- 126 4.2. Практические аспекты сортировки
- 128 4.3. Пирамидальная сортировка
- 129 4.3.1. Пирамиды
- 132 4.3.2. Создание пирамиды
- 133 4.3.3. Наименьший элемент пирамиды
- 135 4.3.4. Быстрый способ создания пирамиды (*)
- 137 4.3.5. Сортировка вставками
- 138 4.4. История из жизни. Билет на самолет
- 141 4.5. Сортировка слиянием. Метод «разделяй и властвуй»
- 143 4.6. Быстрая сортировка. Рандомизированная версия
- 146 4.6.1. Ожидаемое время исполнения алгоритма быстрой сортировки
- 147 4.6.2. Рандомизированные алгоритмы
- 150 4.6.3. Действительно ли алгоритм быстрой сортировки работает быстро?
- 150 4.7. Сортировка распределением. Метод блочной сортировки
- 151 4.7.1. Нижние пределы для сортировки
- 152 4.8. История из жизни. Адвокат Скиена
- 154 4.9. Двоичный поиск и связанные с ним алгоритмы
- 155 4.9.1. Частота вхождения элемента
- 155 4.9.2. Односторонний двоичный поиск
- 156 4.9.3. Корни числа
- 156 4.10. Метод «разделяй и властвуй»
- 157 4.10.1. Рекуррентные соотношения
- 158 4.10.2. Рекуррентные соотношения метода «разделяй и властвуй»
- 159 4.10.3. Решение рекуррентных соотношений типа «разделяй и властвуй» (*)
- 161 4.11. Упражнения
- 168 Глава 5. Обход графов
- 169 5.1. Разновидности графов
- 172 5.1.1. Граф дружеских отношений
- 174 5.2. Структуры данных для графов
- 178 5.3. История из жизни. Жертва закона Мура
- 181 5.4. История из жизни. Создание графа
- 184 5.5. Обход графа
- 185 5.6. Обход в ширину
- 187 5.6.1. Применение обхода
- 188 5.6.2. Поиск путей
- 189 5.7. Применение обхода в ширину
- 189 5.7.1. Компоненты связности
- 191 5.7.2. Раскраска графов двумя цветами
- 192 5.8. Обход в глубину
- 195 5.9. Применение обхода в глубину
- 196 5.9.1. Поиск циклов
- 196 5.9.2. Шарниры графа
- 200 5.10. Обход в глубину ориентированных графов
- 202 5.10.1. Топологическая сортировка
- 203 5.10.2. Сильно связные компоненты
- 207 5.11. Упражнения
- 169 5.1. Разновидности графов
- 213 Глава 6. Алгоритмы для работы со взвешенными графами
- 214 6.1. Минимальные остовные деревья
- 215 6.1.1. Алгоритм Прима
- 218 6.1.2. Алгоритм Крускала
- 220 6.1.3. Поиск-объединение
- 223 6.1.4. Разновидности остовных деревьев
- 224 6.2. История из жизни. И все на свете только сети
- 227 6.3. Поиск кратчайшего пути
- 228 6.3.1. Алгоритм Дейкстры
- 231 6.3.2. Кратчайшие пути между всеми парами вершин
- 233 6.3.3. Транзитивное замыкание
- 234 6.4. История из жизни. Печатаем с помощью номеронабирателя
- 239 6.5. Потоки в сетях и паросочетание в двудольных графах
- 239 6.5.1. Паросочетание в двудольном графе
- 240 6.5.2. Вычисление потоков в сети
- 244 6.6. Разрабатывайте не алгоритмы, а графы
- 246 6.7. Упражнения
- 214 6.1. Минимальные остовные деревья
- 251 Глава 7. Комбинаторный поиск и эвристические методы
- 251 7.1. Перебор с возвратом
- 254 7.1.1. Генерирование всех подмножеств
- 255 7.1.2. Генерирование всех перестановок
- 256 7.1.3. Генерирование всех путей в графе
- 258 7.2. Отсечение вариантов поиска
- 259 7.3. Судоку
- 264 7.4. История из жизни. Покрытие шахматной доски
- 267 7.5. Эвристические методы перебора
- 268 7.5.1. Произвольная выборка
- 271 7.5.2. Локальный поиск
- 274 7.5.3. Имитация отжига
- 278 7.5.4. Применение метода имитации отжига
- 280 7.6. История из жизни. Только это не радио
- 283 7.7. История из жизни. Отжиг массивов
- 286 7.8. Другие эвристические методы поиска
- 287 7.9. Параллельные алгоритмы
- 289 7.10. История из жизни. «Торопиться в никуда
- 290 7.11. Упражнения
- 251 7.1. Перебор с возвратом
- 293 Глава 8. Динамическое программирование
- 294 8.1. Кэширование и вычисления
- 294 8.1.1. Генерирование чисел Фибоначчи методом рекурсии
- 295 8.1.2. Генерирование чисел Фибоначчи посредством кэширования
- 297 8.1.3. Генерирование чисел Фибоначчи посредством динамического программирования
- 298 8.1.4. Биномиальные коэффициенты
- 300 8.2. Поиск приблизительно совпадающих строк
- 301 8.2.1. Применение рекурсии для вычисления расстояния редактирования
- 302 8.2.2. Применение динамического программирования для вычисления расстояния редактирования
- 304 8.2.3. Восстановление пути
- 306 8.2.4. Разновидности расстояния редактирования
- 310 8.3. Самая длинная возрастающая последовательность
- 312 8.4. История из жизни. Эволюция омара
- 315 8.5. Задача разбиения
- 318 8.6. Синтаксический разбор
- 320 8.6.1. Триангуляция с минимальным весом
- 322 8.7. Ограничения динамического программирования. Задача коммивояжера
- 323 8.7.1. Вопрос правильности алгоритмов динамического программирования
- 324 8.7.2. Эффективность алгоритмов динамического программирования
- 325 8.8. История из жизни. Динамическое программирование и язык Prolog
- 328 8.9. История из жизни. Сжатие текста для штрих-кодов
- 332 8.10. Упражнения
- 294 8.1. Кэширование и вычисления
- 338 Глава 9. Труднорешаемые задачи и аппроксимирующие алгоритмы
- 338 9.1. Сведение задач
- 339 9.1.1. Ключевая идея
- 340 9.1.2. Задачи разрешимости
- 341 9.2. Сведение для создания новых алгоритмов
- 341 9.2.1. Поиск ближайшей пары
- 342 9.2.2. Максимальная возрастающая подпоследовательность
- 343 9.2.3. Наименьшее общее кратное
- 344 9.2.4. Выпуклая оболочка (*)
- 345 9.3. Простые примеры сведения сложных задач
- 345 9.3.1. Гамильтонов цикл
- 347 9.3.2. Независимое множество и вершинное покрытие
- 350 9.3.3. Задача о клике
- 351 9.4. Задача выполнимости булевых формул
- 352 9.4.1. Задача выполнимости в 3-конъюнктивной нормальной форме
- 353 9.5. Нестандартные сведения
- 354 9.5.1. Целочисленное программирование
- 356 9.5.2. Вершинное покрытие
- 358 9.6. Искусство доказательства сложности
- 360 9.7. История из жизни. Наперегонки со временем
- 362 9.8. История из жизни. Полный провал
- 364 9.9. Сравнение классов сложности P и NP
- 365 9.9.1. Верификация решения и поиск решения
- 365 9.9.2. Классы сложности P и NP
- 366 9.9.3. Почему задача выполнимости является самой сложной из всех сложных задач?
- 367 9.9.4. NP-сложность по сравнению с NP-полнотой
- 367 9.10. Решение NP-полных задач
- 368 9.10.1. Аппроксимация вершинного покрытия
- 370 9.10.2. Задача коммивояжера в евклидовом пространстве
- 371 9.10.3. Максимальный бесконтурный подграф
- 372 9.10.4. Задача о покрытии множества
- 375 9.11. Упражнения
- 338 9.1. Сведение задач
- 380 Глава 10. Как разрабатывать алгоритмы
- 385 ЧАСТЬ II. КАТАЛОГ АЛГОРИТМИЧЕСКИХ ЗАДАЧ
- 387 Глава 11. Описание каталога
- 389 Глава 12. Структуры данных
- 389 12.1. Словарь
- 395 12.2. Очереди с приоритетами
- 398 12.3. Суффиксные деревья и массивы
- 402 12.4. Графы
- 406 12.5. Множества
- 410 12.6. Kd-деревья
- 415 Глава 13. Численные задачи
- 416 13.1. Решение системы линейных уравнений
- 419 13.2. Уменьшение ширины ленты матрицы
- 422 13.3. Умножение матриц
- 425 13.4. Определители и перманенты
- 427 13.5. Условная и безусловная оптимизация
- 431 13.6. Линейное программирование
- 435 13.7. Генерирование случайных чисел
- 440 13.8. Разложение на множители и проверка чисел на простоту
- 443 13.9. Арифметика произвольной точности
- 448 13.10. Задача о рюкзаке
- 451 13.11. Дискретное преобразование Фурье
- 455 Глава 14. Комбинаторные задачи
- 456 14.1. Сортировка
- 461 14.2. Поиск
- 465 14.3. Поиск медианы и выбор элементов
- 468 14.4. Генерирование перестановок
- 472 14.5. Генерирование подмножеств
- 475 14.6. Генерирование разбиений
- 479 14.7. Генерирование графов
- 484 14.8. Календарные вычисления
- 486 14.9. Календарное планирование
- 489 14.10. Выполнимость
- 493 Глава 15. Задачи на графах c полиномиальным временем исполнения
- 494 15.1. Компоненты связности
- 497 15.2. Топологическая сортировка
- 500 15.3. Минимальные остовные деревья
- 505 15.4. Поиск кратчайшего пути
- 511 15.5. Транзитивное замыкание и транзитивная редукция
- 514 15.6. Паросочетание
- 517 15.7. Задача поиска эйлерова цикла и задача китайского почтальона
- 521 15.8. Реберная и вершинная связность
- 524 15.9. Потоки в сети
- 528 15.10. Рисование графов
- 531 15.11. Рисование деревьев
- 534 15.12. Планарность
- 538 Глава 16. Сложные задачи на графах
- 539 16.1. Задача о клике
- 542 16.2. Независимое множество
- 544 16.3. Вершинное покрытие
- 547 16.4. Задача коммивояжера
- 551 16.5. Гамильтонов цикл
- 554 16.6. Разбиение графов
- 557 16.7. Вершинная раскраска
- 561 16.8. Реберная раскраска
- 563 16.9. Изоморфизм графов
- 568 16.10. Дерево Штейнера
- 572 16.11. Разрывающее множество ребер или вершин
- 576 Глава 17. Вычислительная геометрия
- 577 17.1. Элементарные задачи вычислительной геометрии
- 581 17.2. Выпуклая оболочка
- 585 17.3. Триангуляция
- 589 17.4. Диаграммы Вороного
- 592 17.5. Поиск ближайшей точки
- 596 17.6. Поиск в области
- 599 17.7. Местоположение точки
- 603 17.8. Выявление пересечений
- 607 17.9. Разложение по контейнерам
- 610 17.10. Преобразование к срединной оси
- 613 17.11. Разбиение многоугольника на части
- 615 17.12. Упрощение многоугольников
- 619 17.13. Выявление сходства фигур
- 621 17.14. Планирование перемещений
- 625 17.15. Конфигурации прямых
- 628 17.16. Сумма Минковского
- 631 Глава 18. Множества и строки
- 631 18.1. Поиск покрытия множества
- 635 18.2. Задача укладки множества
- 638 18.3. Сравнение строк
- 641 18.4. Нечеткое сравнение строк
- 647 18.5. Сжатие текста
- 651 18.6. Криптография
- 656 18.7. Минимизация конечного автомата
- 659 18.8. Максимальная общая подстрока
- 663 18.9. Поиск минимальной общей надстроки
- 666 Глава 19. Ресурсы
- 666 19.1. Программные системы
- 666 19.1.1. Библиотека LEDA
- 667 19.1.2. Библиотека CGAL
- 668 19.1.3. Библиотека Boost
- 668 19.1.4. Библиотека GOBLIN
- 668 19.1.5. Библиотека Netlib
- 669 19.1.6. Коллекция алгоритмов ассоциации ACM
- 669 19.1.7. Сайты SourceForge и CPAN
- 669 19.1.8. Система Stanford GraphBase
- 670 19.1.9. Пакет Combinatorica
- 670 19.1.10. Программы из книг
- 672 19.2. Источники данных
- 673 19.3. Библиографические ресурсы
- 673 19.4. Профессиональные консалтинговые услуги
- 666 19.1. Программные системы
- 675 Список литературы
- 713 Предметный указатель
Инструкция как скачать книгу Стивен Скиена: Алгоритмы. Руководство по разработке в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.