Босс В. Лекции по математике. Т. 10: Перебор и эффективные алгоритмы

М.: Издательство ЛКИ, 2008. - 216 с. Книга посвящена теории сложности алгоритмов в той ее части, где речь идет о противостоянии Р- и NР- задач. В резонанс с проблемой «Р против NP» входит обширная тематика: комбинаторные задачи на графах, неразрешимые проблемы теории алгоритмов, криптография, целочисленное программирование, вероятностные методы, квантовые вычисления, алгоритмы Хачияна и Кармаркара для линейного программирования, а также полиномиальный алгоритм AKS для выяснения простоты числа. Особое внимание уделяется геометрическому взгляду на проблему, который в привычном уже пейзаже обнаруживает свежие ракурсы.
Изложение отличается краткостью и прозрачностью.
Для студентов, преподавателей, инженеров и научных работников. Предисловие к «Лекциям»
Предисловие к десятому тому
Комбинаторные задачи
Экспоненциальный кошмар
Р- и NР-задачи
Центральный вопрос и окружение
Задачи на графах
Целочисленное программирование
Логические задачи
(0, 1)-матрицы
Простые и составные числа
Комбинаторные механизмы
Инструменты и декорации
Вычислимые функции
Перечислимые множества
Неразрешимые проблемы
Машины Тьюринга
Полиномиальные алгоритмы
Вычислительная сложность
Задачи верхнего уровня
Проблема Р ?/ NP
Класс Р
Класс NР
Сводимость и NР-полнота
Универсальная переборная задача
Теорема Кука
Класс NРС
Подход Левина
Полиномиальное раздутие
Будет ли решена проблема Р == NP
Проблема co-NP==NP
Сильная NР-полнота
Кратчайший путь
Максимальный поток и минимальный разрез
Теория матроидов и жадный алгоритм
Вариации МОД
РSРAСЕ-задачи
Схемная сложность
Интерактивные протоколы
Релятивизация и оракулы
Рамсеевские задачи
Линейное программирование
Постановка задачи
Предыстория комбинаторного варианта
Эффекты ограниченной точности
Алгоритм эллипсоидов
Природа алгоритма
Методы внутренней точки
Феномен целочисленных вершин
Арифметика и криптография
О причинах исключительности
Тесты на простоту
Полиномиальный тест AKS
Алгоритмы факторизации
Система RSA
Вариант распознавания
Дискретный логарифм
Системы с нулевым разглашением
Другие задачи
Технические дополнения
Геометрический подход
Общая картина
Выпуклые многогранники
Циклические многогранники
Линейные разделяющие деревья
Алгоритмы прямого типа
Релаксационные многогранники
Аффинная сводимость
Комментарии и дополнения
Вероятностные алгоритмы
Напоминание о смешанных стратегиях
Интерактивные доказательства
РСР-проблематика
Рутинная колея
Простые числа
Прагматика и эвриcтика
Сетевое программирование как обобщение динамического
Ареал жадного алгоритма
Приближенные алгоритмы
Метод ветвей и границ
О задаче ЦЛП
Квантовые вычисления
В чем идея и каковы препятствия
Основные понятия
Вычисление и феномен измерения
Квантовые вентили
Алгоритм ускоренного поиска
Квантовое преобразование Фурье
Алгоритм факторизации Шора
Антипод здравого смысла
ЭПР-парадокс и скрытые параметры
О перетягивании каната
Комментарии и дополнения
Сводка основных определений и результатов
Список NР-полных задач
Алгоритмы и вычислимость
Проблема Р= NP
Вокруг «Р или NP»
Линейное программирование
Арифметика и криптография
Геометрический подход
Вероятностные алгоритмы
Квантовые вычисления
Сокращения и обозначения
Литература
Предметный указатель