Кузюрин Н.Н. Фомин С.А. Сложность комбинаторных алгоритмов. Курс лекций
Подождите немного. Документ загружается.
PP
Класс, 53, 54
PSPACE
Класс, 39, 40, 42, 54
PTAS
Knapsack, 84, 87
Quicksort
Алгоритм, 17, 20, 21, 48
RP
Класс, 39, 49–51, 53, 54
Satisfiability, 45, 46
Задача, 45, 46
Semidefinite programming, 108
Set Covering, 69, 70
Задача, 69, 70
Shortest Path
Задача, 9, 11, 36, 40
Shortest Path Problem, 9, 11, 36, 40
Traveling Salesman Problem, 9, 10, 13, 15, 36, 41–44,
76, 78
TSP
Алгоритм
Переборный, 9, 38
Задача, 9, 10, 13, 15, 36, 41–44, 76, 78
Метрическая
Алгоритм, 76, 77
Vector programming, 108, 109
Vertex Covering, 46, 47
Задача, 46, 47
ZPP
Класс, 39, 54
Алгоритм
Euler cycle, 73
GCD, 7
Greedy MSSC, 70, 72
Knapsack-SAT, 79
MAX-CUT
Вероятностный, 109
MAX-SAT
Вероятностный, 106, 107, 109, 112
Дерандомизация, 112
Mergesort, 17
Minimum Spanning Tree
Прима, 15
PTAS
Knapsack, 84, 87
Рюкзак, 84, 87
Quicksort, 17, 20, 21, 48
TSP
Метрическая, 76, 77
Переборный, 9, 38
Дейкстры, 11, 13, 15, 40
Динамическое программирование
Knapsack, 79, 82, 84
Packing, 89, 91
Жадный
Knapsack, 73, 84
Рюкзак, 73, 84
Жадный MSSC, 70, 72
Коммивояжер
Метрический, 76, 77
Переборный, 9, 38
Минимальное остовное дерево, 15
НОД, 7
Немхаузера-Ульмана, 82
Рюкзак, 79, 82, 84
Сортировка
Быстрая, 17, 20, 21, 48
Слиянием, 17
Сумма размеров, 79
Упаковка, 89, 91
Флойда-Уоршолла, 13
Эйлеров цикл, 73
Векторное программирование, 108, 109
Вершинное покрытие
Задача, 46, 47
Выполнимость
Задача, 45, 46
Выполнимость-Максимизация
Задача, 58, 105, 106, 110–112
Дейкстры
Алгоритм, 11, 13, 15, 40
Жадный MSSC
Алгоритм, 70, 72
Задача
2-Satisfiability, 46
2-Выполнимость, 46
2SAT, 46
3-Satisfiability, 46, 57, 59
3-Выполнимость, 46, 57, 59
3SAT, 46, 57, 59
3Выполнимость-Максимизация, 57–59
halting problem, 36, 40
K-covering, 69
Knapsack, 79, 82
MAX-3SAT, 57–59
MAX-CUT, 108, 109
MAX-CUT(VP), 109, 110
MAX-CUT(ЦЛП), 109
MAX-SAT, 58, 105, 106, 110–112
Min Sum Set Cover, 70, 71
Minimum Spanning Tree, 15, 40
Packing, 89, 91
Satisfiability, 45, 46
Set Covering, 69, 70
Shortest Path, 9, 11, 36, 40
TSP, 9, 10, 13, 15, 36, 41–44, 76, 78
Vertex Covering, 46, 47
Вершинное покрытие, 46, 47
131
Выполнимость, 45, 46
Выполнимость-Максимизация, 58, 105, 106, 110–
112
К-покрытие, 69
Коммивояжер, 9, 10, 13, 15, 36, 41–44, 76, 78
Кратчайшие пути, 9, 11, 36, 40
Максимальный разрез, 108, 109
Максимальный разрез(VP), 109, 110
Максимальный разрез(ЦЛП), 109
Минимальное остовное дерево, 15, 40
Остановки, 36, 40
Покрытие гиперграфа с минимальной суммой, 70,
71
Покрытие множества, 69, 70
Рюкзак булев, 79, 82
Упаковка, 89, 91
К-покрытие
Задача, 69
Класс
BPP, 39, 51–53
coNP, 42, 44, 47, 48, 50, 54
coNSPACE, 42
coNTIME, 42
coRP, 49, 50, 54, 56
DSPACE, 40, 42
DTIME, 39, 42
EXPTIME, 39, 40
NEXP, 56
NP, 8, 13, 15, 17, 39, 40, 42–47, 50, 54–59, 67, 76,
79, 88, 89, 94, 100, 105
NPC, 44, 46, 47, 57–59
NSPACE, 42
NTIME, 42, 56
P, 39–42, 44–47, 57
PCP, 39, 55–59
PP, 53, 54
PSPACE, 39, 40, 42, 54
RP, 39, 49–51, 53, 54
ZPP, 39, 54
Коммивояжер
Алгоритм
Переборный, 9, 38
Задача, 9, 10, 13, 15, 36, 41–44, 76, 78
Метрический
Алгоритм, 76, 77
Кратчайшие пути
Алгоритм Дейкстры, 11, 13, 15, 40
Алгоритм Флойда-Уоршолла, 13
Задача, 9, 11, 36, 40
Максимальный разрез
Задача, 108, 109
Максимальный разрез(VP)
Задача, 109, 110
Максимальный разрез(ЦЛП)
Задача, 109
Машина Тьюринга
Симулятор, 26
Минимальное остовное дерево
Алгоритм, 15
Задача, 15, 40
НОД
Алгоритм, 7
Остановки
Задача, 36, 40
Покрытие гиперграфа с минимальной суммой
Задача, 70, 71
Покрытие множества
Задача, 69, 70
Полуопределенное программирование, 108
Рюкзак
Алгоритм
PTAS, 84, 87
Динамическое программирование, 79, 82, 84
Жадный, 73, 84
Алгоритм Немхаузера-Ульмана, 82
Рюкзак булев
Задача, 79, 82
Симулятор
Машина Тьюринга, 26
Сортировка
Быстрая, 17, 20, 21, 48
Слиянием, 17
Сумма размеров
Алгоритм, 79
Тьюринга
Машина
Симулятор, 26
Упаковка
Алгоритм
Динамическое программирование, 89, 91
Задача, 89, 91
Флойда-Уоршолла
Алгоритм, 13
Эйлеров цикл
Алгоритм, 73
132
Список иллюстраций
1.1 RAM — машина со случайным доступом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.2 Пример МТ: удвоение строки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.3 Пример МТ: унарное сложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.4 Пример МТ: распознавание четных строк . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.5 Пример МТ: Распознавание строки, с одинаковым количеством 0 и 1 . . . . . . . . . . . . . . . . . . . . 31
1.6 Выполнение МТ «Распознавание строки, с одинаковым количеством 0 и 1» . . . . . . . . . . . . . . . . . 32
1.7 Трехленточная универсальная МТ для одноленточных МТ . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.8 Классы NP, coNP, P, NPC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
1.9 Схема сравнения двух битовых строк . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
1.10 Иерархия некоторых классов сложности. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.1 Иллюстрация работы жадного алгоритма для задачи о покрытии . . . . . . . . . . . . . . . . . . . . . . . 68
3.1 Дерандомизация на основе минимизации оценок матожидания. . . . . . . . . . . . . . . . . . . . . . . . . 111
133
Список алгоритмов
1 Тривиальное вычисление y = x
n
mod m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Разумное вычисление y = x
n
mod m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Вычисление факториала y = n! mod m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4 Алгоритм Евклида . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5 Неэффективный алгоритм для нахождения НОД . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6 Переборный алгоритм для задачи 3 «TSP» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
7 Алгоритм Дейкстры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
8 Алгоритм Флойда-Уоршолла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
9 Алгоритм Прима . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
10 Сортировка слиянием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
11 Быстрая сортировка с детерминированным выбором оси . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
12 Быстрая сортировка с вероятностным выбором оси . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
13 Быстрое переполнение памяти в присутствии умножения. . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
14 Простой способ вычисления произведения R
1
· R
2
на RAM. . . . . . . . . . . . . . . . . . . . . . . . . . 25
15 Симулятор работы машины Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
16 Сведение оптимизационных задач к задачам разрешения . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
17 Моделирование перебора недетерминизмом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
18 Жадный алгоритм для задачи 20 «MSSC» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
19 Модифицированный жадный алгоритм для задачи 0-1 РЮКЗАК . . . . . . . . . . . . . . . . . . . . . . . 74
20 Алгоритм нахождения Эйлерова цикла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
21 Простой алгоритм для решения метрической задачи коммивояжера . . . . . . . . . . . . . . . . . . . . . 76
22 Алгоритм Кристофидеса для решения метрической TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
23 Динамическое программирование для задачи 22«Сумма размеров» . . . . . . . . . . . . . . . . . . . . . 80
24 Динамическое программирование для задачи 0-1 РЮКЗАК . . . . . . . . . . . . . . . . . . . . . . . . . 81
25 Алгоритм Немхаузера-Ульмана для задачи о рюкзаке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
26 PTAS для задачи 0-1 РЮКЗАК: Общая схема . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
27 PTAS для задачи 0-1 РЮКЗАК: Алгоритмы сложности
n
3
ε
и
n
2
ε
. . . . . . . . . . . . . . . . . . . . . . . 86
28 Динамическое программирование для задачи «Упаковка» . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
29 Приближенный вероятностный алгоритм для задачи 25 (MAX-SAT) на основе линейной релаксации . . 106
30 «SDP-округление MAX-CUT»: вероятностное округление для задачи 28 «MAX-CUT» . . . . . . . . . 109
31 Дерандомизация вероятностного алгоритма 29 «вероятностный MAX-SAT» по методу условных веро-
ятностей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
32 Полиномиальный алгоритм для проверки простоты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
33 Протокол выработки общего секретного ключа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
34 Схема RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
134
Список таблиц
1.1 Значения функции n! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 RAM — машина со случайным доступом: Список команд. . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
135