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

Босс В. Лекции по математике. Т. 10: Перебор и эффективные алгоритмы: Учебное пособие. — М., 2008. — 216 с.
Книга посвящена теории сложности алгоритмов в той ее части, где речь идет о противостоянии Р- и NP-задач. В резонанс с проблемой «Р против NP» входит обширная тематика: комбинаторные задачи на графах, неразрешимые проблемы теории алгоритмов, криптография, целочисленное программирование, вероятностные методы, квантовые вычисления, алгоритмы Хачияна и Кармаркара для линейного программирования, а также полиномиальный алгоритм AKS для выяснения простоты числа. Особое внимание уделяется геометрическому взгляду на проблему, который в привычном уже пейзаже обнаруживает свежие ракурсы.
Изложение отличается краткостью и прозрачностью.
Для студентов, преподавателей, инженеров и научных работников.
Оглавление
Предисловие к «Лекциям»....................................................7
Предисловие к десятому тому................................................9
Глава 1. Комбинаторные задачи......................10
1.1. Экспоненциальный кошмар ..................................10
1.2. Р- и NP-задачи....................................................11
1.3. Центральный вопрос и окружение..........................17
1.4. Задачи на графах..................................................18
1.5. Целочисленное программирование.............25
1.6. Логические задачи........................27
1.7. (0, 1)-матрицы...........................30
1.8. Простые и составные числа..................32
1.9. Комбинаторные механизмы..................33
Глава 2. Инструменты и декорации ...................35
2.1. Вычислимые функции.....................35
2.2. Перечислимые множества...................37
2.3. Неразрешимые проблемы...................39
2.4. Машины Тьюринга .......................40
2.5. Полиномиальные алгоритмы.................45
2.6. Вычислительная сложность..................47
2.7. Задачи верхнего уровня.....................49
Глава 3. Проблема Р = NP ........................52
3.1. Класс Р...............................52
3.2. Класс NP..............................54
3.3. Сводимость и NP-полнота ..................56
3.4. Универсальная переборная задача..............58
3.5. Теорема Кука............................59
3.6. Класс NPC.............................62
3.7. Подход Левина..........................64
3.8. Полиномиальное раздутие...................66
3.9. Будет ли решена проблема Р = NP.............67
Глава 4. Анатомия переборных задач ..................69
4.1. Проблема co-NP=NP......................69
4.2. Сильная NP-полнота......................70
4.3. Кратчайший путь.........................72
4.4. Максимальный поток и минимальный разрез .....75
4.5. Теория матроидов и жадный алгоритм ..........76
4.6. Вариации МОД..........................80
4.7. PSPACE-задачи..........................80
4.8. Схемная сложность.......................83
4.9. Интерактивные протоколы..................83
4.10. Релятивизация и оракулы...................86
4.11. Рамсеевские задачи .......................88
Глава 5. Линейное программирование..................91
5.1. Постановка задачи........................91
5.2. Предыстория комбинаторного варианта.........95
5.3. Эффекты ограниченной точности..............97
5.4. Алгоритм эллипсоидов.....................100
5.5. Природа алгоритма .......................102
5.6. Методы внутренней точки...................103
5.7. Феномен целочисленных вершин..............104
Глава 6. Арифметика и криптография..................107
6.1. О причинах исключительности ...............107
6.2. Тесты на простоту........................108
6.3. Полиномиальный тест AKS..................110
6.4. Алгоритмы факторизации...................112
6.5. Система RSA............................113
6.6. Вариант распознавания.....................116
6.7. Дискретный логарифм.....................117
6.8. Системы с нулевым разглашением.............119
6.9. Другие задачи...........................120
6.10. Технические дополнения....................123
Глава 7. Геометрический подход.....................126
7.1. Общая картина..........................126
7.2. Выпуклые многогранники...................130
7.3. Циклические многогранники.................134
7.4. Линейные разделяющие деревья...............136
7.5. Алгоритмы прямого типа ...................139
7.6. Релаксационные многогранники..............142
7.7. Аффинная сводимость.....................144
7.8. Комментарии и дополнения.................146
Глава 8. Вероятностные алгоритмы...................148
8.1. Напоминание о смешанных стратегиях..........149
8.2. Интерактивные доказательства................150
8.3. РСР-проблематика........................153
8.4. Рутинная колея..........................155
8.5. Простые числа...........................157
Глава 9. Прагматика и эвристика.....................158
9.1. Сетевое программирование как обобщение динамического ..........................158
9.2. Ареал жадного алгоритма...................160
9.3. Приближенные алгоритмы ..................161
9.4. Метод ветвей и границ.....................163
9.5. О задаче ЦЛП...........................164
Глава 10. Квантовые вычисления......................166
10.1. В чем идея и каковы препятствия..............166
10.2. Основные понятия........................168
10.3. Вычисление и феномен измерения.............174
10.4. Квантовые вентили.......................175
10.5. Алгоритм ускоренного поиска................176
10.6. Квантовое преобразование Фурье..............177
10.7. Алгоритм факторизации Шора................179
10.8. Антипод здравого смысла...................180
10.9. ЭПР-парадокс и скрытые параметры ...........183
10.10. О перетягивании каната....................185
10.11. Комментарии и дополнения.................186
Глава 11. Сводка основных определений и результатов .......188
11.1. Список NP-полных задач...................188
11.2. Алгоритмы и вычислимость..................191
11.3. Проблема P = NP........................192
11.4. Вокруг «Р или NP»........................193
11.5. Линейное программирование.................194
11.6. Арифметика и криптография.................195
11.7. Геометрический подход.....................197
11.8. Вероятностные алгоритмы...................200
11.9. Квантовые вычисления.....................201
Сокращения и обозначения..........................203
Литература....................................205
Предметный указатель ............................207

Created using FlowPaper Flipbook Maker ↗