Книга посвящена теории сложности алгоритмов в той её части, где речь идёт о противостоянии P- и NP- задач. В резонанс с проблемой "P против NP" входит обширная тематика: комбинаторные задачи на графах, неразрешимые проблемы теории алгоритмов, криптография, целочисленное программирование, вероятностные методы, квантовые вычисления, алгоритмы Хачияна и Кармаркара для линейного программирования, а также полиномиальный алгоритм AKS для выяснения простоты числа. Особое внимание уделяется геометрической взгляду на проблему, который в привычном уже пейзаже обнаруживает свежие ракурсы.
Изложение отличается краткостью и прозрачностью.
Для студентов, преподавателей, инженеров и научных работников.
Содержание:
Предисловие к лекциям.
Предисловие к десятому тому.
1. Комбинаторные задачи.
2. Инструменты и декорации.
3. Проблема P и NP.
4. Анатомия переборных задач.
5. Линейное программирование.
6. Арифметика и криптография.
7. Геометрический подход.
8. Вероятностные алгоритмы.
9. Прагматика и эвристика.
10. Квантовые вычисления.
11. Сводка основных определений и результатов.
Сокращения и обозначения.
Литература.
Предметный указатель.
Внимание! У вас нет прав для просмотра скрытого текста.
