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

Содержание книги «Алгоритмы. Руководство по разработке»:

• 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. Упражнения
• 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. Упражнения
• 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. Упражнения
• 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. Упражнения
• 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. Упражнения
• 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. Упражнения
• 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. Упражнения
• 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. Профессиональные консалтинговые услуги
• 675 Список литературы
• 713 Предметный указатель