Наверх

Э.Рейнгольд, Ю.Нивергельт, Н.Део, 1980 (Rus)
Комбинаторные алгоритмы. Теория и практика

ПРЕДИСЛОВИЕ

1. ЧТО ТАКОЕ КОМБИНАТОРНЫЕ ВЫЧИСЛЕНИЯ?
   1.1 Пример. Подсчет числа единиц в двоичном наборе
   1.2 Проблема представления: коды, сохраняющие разности
   1.3 Способы композиции
   1.4 Способы декомпозиции
   1.5 Классы алгоритмов
   1.6 Анализ алгоритмов
   1.7 Комментарии и ссылки
   1.8 Упражнения


2. ПРЕДСТАВЛЕНИЕ КОМБИНАТОРНЫХ ОБЪЕКТОВ
   2.1 Целые
   2.2 Последовательности
        2.2.1 Последовательное распределение
        2.2.2 Связанное распределение
        2.2.3 Стеки и очереди
   2.3 Деревья
        2.3.1 Представления
        2.3.2 Прохождения
        2.3.3 Длина путей
   2.4 Множества и мультимножества
   2.5 Комментарии и ссылки


3. ПОДСЧЕТ И ОЦЕНИВАНИЕ
   3.1 Асимптотики
   3.2 Рекуррентные соотношения
        3.2.1 Линейные рекуррентные соотношения с постоянными коэффициентами
        3.2.2 Общие рекуррентные соотношения
   3.3 Производящие функции
   3.4 Подсчет классов эквивалентности: теорема Пойа
        3.4.1 Пример: раскраска бинарного дерева
        3.4.2 Теорема Пойа и лемма Берисайда
   3.5 Комментарии и ссылки
   3.6 Упражнения


4. ИСЧЕРПЫВАЮЩИЙ ПОИСК
   4.1 Поиск с возвращением
       4.1.1 Общий алгоритм
       4.1.2 Усовершенствования
       4.1.3 Оценка сложности выполнения
       4.1.4 Два способа программирования
       4.1.5 Пример. Оптимальные коды, сохраняющие разности
       4.1.6 Метод ветвей и границ
       4.1.7 Динамическое программирование
   4.2 Методы решета
       4.2.1 Нерекурсивное модульное решето
       4.2.2 Рекурсивное решето
       4.2.3 Решето, отбраковывающее изоморфные объекты
   4.3 Приближения исчерпывающего поиска
   4.4 Комментарии и ссылки
   4.5 Упражнения


5. ПОРОЖДЕНИЕ ЭЛЕМЕНТАРНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ
   5.1 Перестановки различных элементов
       5.1.1 Лексикографический порядок
       5.1.2 Векторы инверсий
       5.1.3 Вложенные циклы
       5.1.4 Транспозиция смежных элементов
       5.1.5 Случайные перестановки
   5.2 Подмножества множеств
       5.2.1 Коды Грея
       5.2.2 k-подмножества (сочетания)
   5.3 Композиции и разбиения целых чисел
       5.3.1 Композиции
       5.3.2 Разбиения
   5.4 Комментарии и ссылки
   5.5 Упражнения


6. БЫСТРЫЙ ПОИСК
   6.1 Поиск и другие операции над таблицами
   6.2 Последовательный поиск
   6.3 Логарифмический поиск в статистических таблицах
       6.3.1 Бинарный поиск
       6.3.2 Оптимальные деревья бинарного поиска
       6.3.3 Почти оптимальные деревья бинарного поиска
       6.3.4 Цифровой поиск
   6.4 Логарифмический поиск в динамических таблицах
       6.4.1 Случайные деревья бинарного поиска
       6.4.2 Бинарные деревья, сбалансированные по высоте

      
6.4.3 Бинарные деревья, сбалансированные по весу
       6.4.4 Сбалансированные сильно ветвящиеся деревья
   6.5 Методы вычисления адреса
       6.5.1 Хеширование и его варианты
       6.5.2 Хеш-функции
       6.5.3 Разрешение коллизий
       6.5.4 Влияние коэффициента загрузки
   6.6 Комментарии и ссылки
   6.7 Упражнения


7. СОРТИРОВКА
   7.1 Внутренняя сортировка
       7.1.1 Вставка
       7.1.2 Обменная сортировка
       7.1.3 Выбор
       7.1.4 Распределяющая сортировка
   7.2 Внешняя сортировка
   7.3 Частичная сортировка
       7.3.1 Выбор
       7.3.2 Слияние
   7.4 Комментарии и ссылки
   7.5 Упражнения


8. АЛГОРИТМЫ НА ГРАФАХ
   8.1 Представления
   8.2 Связность и расстояние
       8.2.1 Остовные деревья
       8.2.2 Поиск в глубину
       8.2.3 Двусвязность
       8.2.4 Сильная связность
       8.2.5 Транзитивное замыкание
       8.2.6. Кратчайшие пути
   8.3 Циклы
       8.3.1 Фундаментальные множества циклов
       8.3.2 Порождение всех циклов
   8.4 Клики
   8.5 Изоморфизм
   8.6 Планарность
   8.7 Комментарии и ссылки
   8.8 Упражнения


9. ЭКВИВАЛЕНТНОСТЬ НЕКОТОРЫХ КОМБИНАТОРНЫХ ЗАДАЧ
   9.1 Классы P и NP
  
9.2 NP-трудные и NP-полные задачи
       9.2.1 Выполнимость
       9.2.2 Некоторые NP-полные задачи
       9.2.3 Еще раз о задаче коммивояжера
   9.3 Комментарии и ссылки
   9.4 Упражнения

  
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ