Кузюрин Н.Н. Фомин С.А. Эффективные алгоритмы и сложность вычислений

Подождите немного. Документ загружается.

Предметный указатель 341

coNSPACE, 226

NTIME, 225, 226, 263

coNTIME, 226

P, 11, 12, 14, 15, 43, 123, 218–

222, 226, 230–232, 235,

238, 260, 266, 278, 279,

282, 322–324

Packing, 115–117, 122

Алгоритм, 117, 119, 121,

315

Задача, 115–117, 122

PCP, 8, 14, 74, 218, 260–267,

269, 270, 272, 273, 279,

300

Система, 262, 265

Perfect Matching, 93

PP, 240, 253–257

PRAS

Алгоритм, 150

PSPACE, 218, 220, 226, 256,

322

PTAS, 276–279, 282, 284

Knapsack, 108, 109

Quicksort

Алгоритм, 47–50, 242, 310

Randomized

Turing Machine, 241, 244,

255, 264

RP, 218, 240, 243–248, 254, 257–

259

coRP, 240, 243–247, 257, 258,

263, 298, 326

Satisﬁability, 123, 232–235

Задача, 123, 232–235

Semideﬁnite

Matrix, 177

Semideﬁnite programming, 178,

179

Set

Independent, 160

Maximal Independent, 160,

193

Set Cover, 71, 74

Задача, 71, 74

Shortest Path

Задача, 25, 27, 32, 59, 219

Shortest Path Problem, 25, 27,

32, 59, 219

Sorting

Задача, 45

Space

Complexity, 217

Time complexity, 217

Traveling Salesman Problem,

24, 25, 34–36, 38, 43,

59, 88, 89, 94, 222–224,

226, 227, 230, 309

TSP

Алгоритм

Переборный, 24–26, 64

Метрическая

Алгоритм, 91, 93

Задача, 24, 25, 34–36, 38,

43, 59, 88, 89, 94, 222–

224, 226, 227, 230, 309

Turing

342 Предметный указатель

machine, 199, 225, 241

Randomized Machine, 241,

244, 255, 264

Vector programming, 179, 181

Vertex Cover, 75, 83, 311

Vertex Covering, 76, 78, 79, 81,

236, 237

Задача, 76, 78, 79, 81, 236,

237

ZPP, 218, 257–259, 326

coZPP, 298, 326

Список иллюстраций

1.1. Работа алгоритма 6 «TSP-перебор» . . . . . . . . 26

1.2. Работа алгоритма 7 «Дейкстры» . . . . . . . . . 29

1.3. Иллюстрация работы алгоритма 8 «Флойда–Уор-

шолла» . . . . . . . . . . . . . . . . . . . . . . . . 33

1.4. Иллюстрация работы алгоритма 9 «MST Прима» 37

1.5. Работа «Quicksort» с разными методами выбора

оси . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

1.6. Карта-памятка раздела 1.1 . . . . . . . . . . . . . 52

1.7. RAM — машина с произвольным доступом . . . 56

1.8. Моделирование циклов для RAM . . . . . . . . . 57

2.1. «Плохой» граф для жадного алгоритма вершин-

ного покрытия . . . . . . . . . . . . . . . . . . . . 76

2.2. Неоптимальность жадного алгоритма для вер-

шинного покрытия . . . . . . . . . . . . . . . . . 80

2.3. «Ленивый» и «жадный» алгоритмы вершинного

покрытия на «плохих» графах . . . . . . . . . . . 81

2.4. «Ленивый» и «жадный» алгоритмы вершинного

покрытия на случайных графах . . . . . . . . . . 82

2.5. Карта-памятка разделов 2.1.2и 2.1.1 . . . . . . . 84

2.6. Наборы S

в «жадном» алгоритме для «рюк-

зака» . . . . . . . . . . . . . . . . . . . . . . . . . 87

2.7. Карта-памятка раздела 2.1.4 . . . . . . . . . . . . 95

2.8. Карта-памятка раздела 2.2.2 . . . . . . . . . . . . 110

3.1. Работа алгоритма 28 «Упаковка-ДинПрог» . . . 119

344 Список иллюстраций

3.2. Алгоритм 28 «Упаковка-ДинПрог» на случайных

данных . . . . . . . . . . . . . . . . . . . . . . . . 121

3.3. Карта-памятка раздела 3.2.0 . . . . . . . . . . . . 122

3.4. «Обнуляющие» наборы для трехскобочной КНФ 125

3.5. Карта-памятка раздела 3.3.0 . . . . . . . . . . . . 130

3.6. Граф зависимостей утверждений в разделе 3.5 . 142

3.7. Алгоритм 25 «Рюкзак Немхаузера–Ульмана» на

случайных данных . . . . . . . . . . . . . . . . . 144

4.1. Множества U, G, H в задаче 18 «DNF#» . . . . 155

4.2. Карта-памятка раздела 4.2.0 . . . . . . . . . . . . 156

4.3. PRAM — Parallel Random Access Machine . . . . 158

4.4. График функции 1 − (1 − x/k)

при различных k 176

4.5. График функции

2θ

π(1−cos θ)

. . . . . . . . . . . . . 183

4.6. Вектора в вероятностном округлении «MAX-CUT»183

4.7. Карта-памятка раздела 4.4.2 . . . . . . . . . . . . 186

5.1. Дерандомизация на основе минимизации оценок

математического ожидания . . . . . . . . . . . . 189

5.2. Карта-памятка раздела 5.1.0 . . . . . . . . . . . . 192

6.1. Машина Тьюринга: удвоение строки . . . . . . . 202

6.2. Машина Тьюринга: унарное сложение . . . . . . 203

6.3. Машина Тьюринга: распознавание четных строк 204

6.4. Пример МТ: «Количество 0 и 1 равно?» . . . . . 205

6.5. Выполнение МТ «Количество 0 и 1 равно?» . . . 206

6.6. Трехленточная универсальная МТ для однолен-

точных МТ . . . . . . . . . . . . . . . . . . . . . . 210

6.7. Карта-памятка раздела 6.1.1 . . . . . . . . . . . . 216

6.8. Отображение выполнимой КНФ на граф . . . . 237

6.9. Классы N P, coN P, P, N PC . . . . . . . . . . . . 238

6.10. Карта-памятка раздела 6.2.3 . . . . . . . . . . . . 240

6.11. Классы сложности RP и coRP . . . . . . . . . . 246

6.12. Классы сложности: BPP и его «соседи» . . . . . 253

6.13. Классы сложности: PP и его «соседи» . . . . . . 256

Список иллюстраций 345

6.14. Вероятностные классы сложности: ZPP, RP,

BPP, ZPP . . . . . . . . . . . . . . . . . . . . . . 259

6.15. Карта-памятка раздела 6.3 . . . . . . . . . . . . . 259

6.16. Карта-памятка раздела 6.3.5 . . . . . . . . . . . . 267

6.17. Карта-памятка раздела 6.3.6 . . . . . . . . . . . . 273

6.18. Пример схемы: сравнение двух строк . . . . . . . 286

6.19. Пример коммуникационного протокола для

«x

= y

» . . . . . . . . . . . . . . . . . . . . . 294

6.20. Иерархия некоторых классов сложности . . . . . 299

Список алгоритмов

1. Тривиальное вычисление y = x

mod m . . . . . 18

2. Разумное вычисление y = x

mod m . . . . . . . 19

3. Вычисление факториала y = n! mod m . . . . . . 20

4. Алгоритм Евклида . . . . . . . . . . . . . . . . . 22

5. Неэффективный алгоритм для «НОД» . . . . . . 22

6. Переборный алгоритм для «TSP» . . . . . . . . . 24

7. Алгоритм Дейкстры . . . . . . . . . . . . . . . . . 28

8. Алгоритм Флойда-Уоршолла . . . . . . . . . . . . 32

9. Алгоритм Прима . . . . . . . . . . . . . . . . . . 38

10. Сортировка слиянием . . . . . . . . . . . . . . . . 46

11. Процедура «partition» в «Quicksort» . . . . . . . 48

12. Быстрая сортировка/«Quicksort» . . . . . . . . . 49

13. Переполнение памяти из-за умножения . . . . . 58

14. Простое вычисление R

· R

на RAM . . . . . . . 58

15. Жадный алгоритм для задачи о покрытии . . . 72

16. Жадный алгоритм для вершинного покрытия . 77

17. «Ленивый» алгоритм для задачи 12 «Min Vertex

Covering» . . . . . . . . . . . . . . . . . . . . . . . 79

18. Жадный алгоритм для задачи 13 «Knapsack» . . 85

19. «Модифицированный жадный» для «Рюкзака» . 86

20. Алгоритм нахождения Эйлерова цикла . . . . . 90

21. Простой алгоритм для решения метрической за-

дачи коммивояжера . . . . . . . . . . . . . . . . . 92

22. Алгоритм Кристофидеса для метрической TSP . 94

23. Сумма размеров . . . . . . . . . . . . . . . . . . . 98

24. «Рюкзак»: динамическое программирование . . 100

Список алгоритмов 347

25. «Рюкзак» Немхаузера–Ульмана . . . . . . . . . . 102

26. «Рюкзак» с отбором «легких» решений . . . . . 106

27. PTAS для рюкзака . . . . . . . . . . . . . . . . . 111

28. «Упаковка»: динамическое программирование . 118

29. Динамическое программирование для «SAT» . . 128

30. Алгоритм MIS-Greedy . . . . . . . . . . . . . . . . 161

31. Алгоритм «Parallel MIS» . . . . . . . . . . . . . . 163

32. Протокол византийского соглашения . . . . . . . 169

33. Приближенный вероятностный алгоритм для за-

дачи 20 (MAX-SAT) на основе линейной релакса-

ции . . . . . . . . . . . . . . . . . . . . . . . . . . 174

34. «SDP-округление MAX-CUT» . . . . . . . . . . . 184

35. Дерандомизация вероятностного алгоритма 33 «ве-

роятностный MAX-SAT» по методу условных

вероятностей . . . . . . . . . . . . . . . . . . . . . 190

36. Симулятор работы машины Тьюринга . . . . . . 201

37. Сведение оптимизационных задач к задачам раз-

решения . . . . . . . . . . . . . . . . . . . . . . . . 224