Комбинаторные алгоритмы. Теория и практика

Рейнгольд Э., Нивергельт Ю., Део Н.

Первые два автора известны советскому читателю по переводу их книги «Машинный подход к решению математических задач» (М.:Мир, 1977), написанной совместно с Дж. Фарраром. В данной книге предпринята попытка систематизации комбинаторных алгоритмов, выявления их общих черт и закономерностей. Подробно рассматриваются конкретные задачи использования комбинаторных алгоритмов, в частности очень важная для программирования задача сортировки данных. Каждая глава сопровождается достаточно подробной исторической справкой и большим числом упражнений.

Книга будет полезной математикам-прикладникам, аспирантам и студентам, имеющим дело с задачами дискретной математики.

ISBN 978-5-458-26101-2

Количество страниц: 477.

Содержание книги «Комбинаторные алгоритмы. Теория и практика»:

6 От редактора перевода
7 Предисловие
11 Глава 1. Что такое комбинаторные вычисления?
- 12 1.1. Пример. Подсчет числа единиц в двоичном наборе
- 17 1.2. Проблема представления: коды, сохраняющие разности
- 21 1.3. Способы композиции
- 23 1.4. Способы декомпозиции
- 26 1.5. Классы алгоритмов
- 36 1.6. Анализ алгоритмов
- 41 1.7. Комментарии и ссылки
- 43 1.8. Упражнения
45 Глава 2. Представление комбинаторных объектов
- 45 2.1. Целые
- 48 2.2. Последовательности
  - 49 2.2.1. Последовательное распределение
  - 52 2.2.2. Связанное распределение
  - 55 2.2.3. Стеки и очереди
- 58 2.3. Деревья
  - 60 2.3.1. Представления
  - 62 2.3.2. Прохождения
  - 66 2.3.3. Длина путей
- 72 2.4. Множества и мультимножества
- 80 2.5. Комментарии и ссылки
- 82 2.6. Упражнения
87 Глава 3. Подсчет и оценивание
- 88 3.1. Асимптотики
- 94 3.2. Рекуррентные соотношения
  - 94 3.2.1. Линейные рекуррентные соотношения с постоянными коэффициентами
  - 98 3.2.2. Общие рекуррентные соотношения
- 103 3.3. Производящие функции
- 109 3.4. Подсчет классов эквивалентности: теорема Пойа
  - 110 3.4.1. Пример: раскраска бинарного дерева
  - 114 3.4.2. Теорема Пойа и лемма Бернсайда
- 118 3.5. Комментарии и ссылки
- 119 3.6. Упражнения
124 Глава 4. Исчерпывающий поиск
- 124 4.1. Поиск с возвращением
  - 125 4.1.1. Общий алгоритм
  - 128 4.1.2. Усовершенствования
  - 131 4.1.3. Оценка сложности выполнения
  - 133 4.1.4. Два способа программирования
  - 136 4.1.5. Пример. Оптимальные коды, сохраняющие разности
  - 140 4.1.6. Метод ветвей и границ
  - 150 4.1.7. Динамическое программирование
- 153 4.2. Методы решета
  - 154 4.2.1. Нерекурсивное модульное решето
  - 158 4.2.2. Рекурсивное решето
  - 161 4.2.3. Решето, отбраковывающее изоморфные объекты
- 162 4.3. Приближения исчерпывающего поиска
- 170 4.4. Комментарии и ссылки
- 175 4.5. Упражнения
182 Глава 5. Порождение элементарных комбинаторных объектов
- 184 5.1. Перестановки различных элементов
  - 184 5.1.1. Лексикографический порядок
  - 187 5.1.2. Векторы инверсий
  - 189 5.1.3. Вложенные циклы
  - 191 5.1.4. Транспозиция смежных моментов
  - 194 5.1.5. Случайные перестановки
- 195 5.2. Подмножества множеств
  - 196 5.2.1. Коды Грея
  - 202 5.2.2. k-подмножества (сочетания)
- 213 5.3. Композиции и разбиения целых чисел
  - 213 5.3.1. Композиции
  - 214 5.3.2. Разбиения
- 218 5.4. Комментарии и ссылки
- 222 5.5. Упражнения
226 Глава 6. Быстрый поиск
- 226 6.1. Поиск и другие операции над таблицами
- 230 6.2. Последовательный поиск
- 235 6.3. Логарифмический поиск в статических таблицах
  - 236 6.3.1. Бинарный поиск
  - 240 6.3.2. Оптимальные деревья бинарного поиска
  - 248 6.3.3. Почти оптимальные деревья бинарного поиска
  - 253 6.3.4. Цифровой поиск
- 257 6.4. Логарифмический поиск в динамических таблицах
  - 258 6.4.1. Случайные деревья бинарного поиска
  - 261 6.4.2. Бинарные деревья, сбалансированные по высоте
  - 269 6.4.3. Бинарные деревья, сбалансированные по весу
  - 277 6.4.4. Сбалансированные сильно ветвящиеся деревья
- 282 6.5. Методы вычисления адреса
  - 283 6.5.1. Хеширование и его варианты
  - 288 6.5.2. Хеш-функции
  - 291 6.5.3. Разрешение коллизий
  - 293 6.5.4. Влияние коэффициента загрузки
- 295 6.6. Комментарии и ссылки
- 300 6.7. Упражнения
307 Глава 7. Сортировка
- 308 7.1. Внутренняя сортировка
  - 312 7.1.1. Вставка
  - 314 7.1.2. Обменная сортировка
  - 321 7.1.3. Выбор
  - 326 7.1.4. Распределяющая сортировка
- 329 7.2. Внешняя сортировка
- 334 7.3. Частичная сортировка
  - 335 7.3.1. Выбор
  - 338 7.3.2. Слияние
- 341 7.4. Комментарии и ссылки
- 344 7.5. Упражнения
351 Глава 8. Алгоритмы на графах
- 352 8.1. Представления
- 356 8.2. Связность и расстояние
  - 357 8.2.1. Остовные деревья
  - 361 8.2.2. Поиск в глубину
  - 366 8.2.3. Двусвязность
  - 369 8.2.4. Сильная связность
  - 374 8.2.5. Транзитивное замыкание
  - 377 8.2.6. Кратчайшие пути
- 382 8.3. Циклы
  - 382 8.3.1. Фундаментальные множества циклов
  - 384 8.3.2. Порождение всех циклов
- 389 8.4. Клики
- 396 8.5. Изоморфизм
- 402 8.6. Планарность
- 424 8.7. Комментарии и ссылки
- 433 8.8. Упражнения
441 Глава 9. Эквивалентность некоторых комбинаторных задач
- 441 9.1. Классы P и NP
- 445 9.2. NP-трудные и NP-полные задачи
  - 446 9.2.1. Выполнимость
  - 450 9.2.2. Некоторые NP-полные задачи
  - 456 9.2.3. Еще раз о задаче коммивояжера
- 458 9.3. Комментарии и ссылки
- 463 9.4. Упражнения
466 Предметный указатель

Инструкция как скачать книгу Рейнгольд Э., Нивергельт Ю., Део Н.: Комбинаторные алгоритмы. Теория и практика в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.