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

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

Список литературы 331

[Kha79] L.G. Khachiyan. A Polynomial Algorithm in Linear

Programming // Soviet Mathematics Doklady. 1979.

Vol. 20. pp. 191–194.

[KLM89] R.M. Karp, M. Luby, N. Madras. Monte-Carlo ap-

proximation algorithms for enumeration problems //

J. Algorithms. 1989. Vol. 10, no. 3. pp. 429–448.

[KMSV99] On Syntactic versus Computational Views of

Approximability // SIAM J. Comput. 1999.

Vol. 28, no. 1. pp. 164–191.

[KZ97] H. Karloﬀ, U. Zwick. A 7/8-approximation al-

gorithm for MAX 3SAT? // Proceedings of the

38th Annual IEEE Symposium on Foundations of

Computer Science, Miami Beach, FL, USA. IEEE

Press, 1997.

http://citeseer.ist.psu.edu/karloff97approximation.html

[Lov99] L. Lov´asz. Complexity of algorithms. 1999.

http://research.microsoft.com/users/lovasz/notes.htm

[Lub85] M. Luby. A simple parallel algorithm for the maximal

independent set problem // STOC ’85: Proceedings of

the seventeenth annual ACM symposium on Theory of

computing. New York, NY, USA: ACM Press, 1985.

pp. 1–10.

[MR95] R. Motwani, P. Raghavan. Randomized algorithms.

Cambridge Univ. Press, 1995.

[Pos36] E.L. Post. Finite Combinatory Processes-Formulation

1 // J. Symb. Log. 1936. Vol. 1, no. 3. pp. 103–105.

[Pri57] R.C. Prim. Shortest Connection Networks and Some

Generalizations // Bell System Technical Journal.

1957. Vol. 36. pp. 1389–1401.

332 Список литературы

[PY91] C.H. Papadimitriou, M. Yannakakis. Optimization,

approximation, and complexity classes // Journal of

Computing and System Sciences. 1991. Vol. 43.

pp. 425–440.

[Rab83] M.O. Rabin. Randomized Byzantine Generals //

Proceedings of the 24th Annual Symposium on

Foundations of Computer Science. 1983. pp. 403–409.

[Rag88] P. Raghavan. Probabilistic constructions of determin-

istic algorithms: approximating packing integer pro-

grams // Journal of Computer and System Scince.

1988. Vol. 37, no. 4. pp. 130–143.

[Sla96] P. Slav´ık. A Tight Analysis of the Greedy Algorithm

for Set Cover // ACM Symposium on Theory of

Computing. 1996. pp. 435–441.

http://citeseer.ist.psu.edu/slavik95tight.html

[Sma00] S. Smale. Mathematical Problems for the Next

Century // Mathematics: Frontiers and Perspectives,

IMU, AMS, 2000 / edited by V. Arnold, M. Atiyah,

P. Lax, B. Mazur. American Mathematical Society,

Providence, 2000.

http://citeseer.ist.psu.edu/smale98mathematical.html

[Tur36] A.M. Turing. On Computable Numbers, with

an Application to the Entscheidungsproblem //

Proceedings of the London Mathematical Society.

1936. Vol. 2, no. 42. pp. 230–265.

http://www.cs.helsinki.fi/u/gionis/cc05/OnComputableNumbers.

pdf

[Wik07] List of NP-complete problems. 2007.

http://en.wikipedia.org/wiki/List_of_NP-complete_problems

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

ε-оптимальный

Алгоритм, 105

Алгоритм

ε-оптимальный, 105

Дейкстры, 27–31, 36, 64,

219

Динамическое програм-

мирование

Knapsack, 99, 101, 103,

313

Packing, 117, 119, 121,

315

Флойда–Уоршолла, 32, 33

Коммивояжер

Метрический, 91, 93

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

Минимальное остовное де-

рево, 36, 37, 64, 70, 309

НОД, 21, 22

Немхаузера–Ульмана, 101,

103, 136, 143, 144, 313

Переполнение памяти умно-

жением, 58, 64, 65, 222

Полиномиальный в сред-

нем, 114, 115, 117

Приближенный, 69, 104,

267, 276

Рюкзак, 99, 101, 103, 313

Сортировка

Быстрая, 47–50, 242, 310

Слиянием, 45, 47

Сумма размеров, 97, 312

Упаковка, 117, 119, 121,

315

Вероятностный прибли-

женный, 172

Жадный

Рюкзак, 87, 109

Knapsack, 87, 109

эпсилон-оптимальный, 105

FPRAS, 150

FPTAS, 105

GCD, 21, 22

Knapsack-SAT, 97, 312

MAX-CUT

Вероятностный, 182, 184

MAX-SAT

Дерандомизация, 191,

318

Вероятностный, 174,

175, 182, 190

Mergesort, 45, 47

Minimum Spanning Tree

Прима, 36, 37, 64, 70, 309

333

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

PRAS, 150

PTAS

Рюкзак, 108, 109

Knapsack, 108, 109

Quicksort, 47–50, 242, 310

TSP

Метрическая, 91, 93

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

Цикл

Эйлера, 88

ДНФ

посчет выполняющих на-

боров, 151, 154, 155

Дейкстры

Алгоритм, 27–31, 36, 64,

219

Дискретный логарифм

Задача, 20

Доминирующее подмножество

Рюкзак, 101, 136, 138

Емкостная

Сложность, 217

Эйлера

Цикл, 88

Путь, 88

граф, 88

Эпсилон-оптимальный

Алгоритм, 105

Эвристика, 41

Флойда–Уоршолла

Алгоритм, 32, 33

Функция

Вычислимая, 212

Граф

Эйлера, 88

Инцидентность, 116

К-покрытие

Задача, 74

Карп

Сводимость, 230, 231, 269

Класс

APX, 15, 44, 274, 276–279,

282, 283

APX PB, 283

BPP, 218, 240, 249–254, 259

DSPACE, 216, 220, 225, 226

DTIME, 73, 216, 219, 225,

226

coDTIME, 225

EXPTIME, 218–220, 322

FPRAS, 150, 151, 154, 156

FPTAS, 104

MAX SNP, 279, 282, 283

MAXSNP, 281

NEXP, 263

NP, 7, 8, 11–16, 34, 39, 40,

43, 44, 61, 68, 70, 71,

73, 89, 96–98, 112, 113,

117, 123, 130, 160, 171,

218, 221, 226–236, 238–

240, 245, 246, 256, 260,

261, 263–267, 269–271,

273–275, 278, 279, 282,

298, 300, 323, 324, 326

coNP, 226, 230, 238–240,

246, 257, 323, 324

NPC, 231, 236, 238, 266,

267, 269, 271, 273, 324

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

NPO, 275, 276, 282, 283

NSPACE, 225, 226

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

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

267, 269, 270, 272, 273,

279, 300

PP, 240, 253–257

PSPACE, 218, 220, 226,

256, 322

PTAS, 276–279, 282, 284

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

257–259

coRP, 240, 243–247, 257,

258, 263, 298, 326

ZPP, 218, 257–259, 326

coZPP, 298, 326

Коммивояжер

Алгоритм

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

Метрический

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

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

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

224, 226, 227, 230, 309

Кратчайшие пути

Алгоритм Дейкстры, 27–

31, 36, 64, 219

Алгоритм Флойда–Уор-

шолла, 32, 33

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

Кук

Сводимость, 222, 229

Литерал, 123, 151

Максимальный разрез

Задача, 180, 184, 317, 318

Максимальный разрез(VP)

Задача, 181, 182, 184, 185

Максимальный разрез(ЦП)

Задача, 181, 182, 184

Максимальное

Независимое множество,

160, 193

Машина

Тьюринга, 199, 241

Недетерминированная,

225

Тьюринга Вероятностная,

241, 244, 255, 264

Машина Тьюринга

Симулятор, 200

Матрица

Инцидентности, 116

положительно полуопре-

деленная, 177

Метрическая

Задача коммивояжера, 89,

Минимальное остовное дерево

Алгоритм, 36, 37, 64, 70,

309

Задача, 36, 219

Множество

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

Максимальное независи-

мое, 160, 193

Независимое, 160

Разрешимое, 212

НОД

Алгоритм, 21, 22

Задача, 21

Недетерминированная

Машина Тьюринга, 225

Независимое множество, 160,

193

Остановки

Задача, 213, 215, 221, 320

Парето-набор

Рюкзак, 101, 136, 138

Паросочетание, 81

Совершенное, 93

Покрытие множества

Задача, 71, 74

Полиномиальная приближен-

ная схема, 105

Полиномиальная рандомизи-

рованная приближен-

ная схема, 150

Полиномиальный в среднем,

114, 115, 117

Положительно полуопреде-

ленная

матрица, 177

Полуопределенное програм-

мирование, 178, 179

Приближенный

Алгоритм, 69, 104, 267, 276

Пространственная

Сложность, 217

Путь

Эйлера, 88

Разрешимое

Множество, 212

Разрешимость, 212

Разрез, 179

Размер, 180

Рюкзак

Алгоритм

Динамическое програм-

мирование, 99, 101,

103, 313

Жадный, 87, 109

PTAS, 108, 109

Алгоритм Немхаузера–

Ульмана, 101, 103, 136,

143, 144, 313

Доминирующее подмно-

жество, 101, 136, 138

Парето-набор, 101, 136,

138

Рюкзак булев

Задача, 85, 87, 98, 99, 101,

103, 105, 136, 313

Сечение, 179

Размер, 180

Симулятор

Машина Тьюринга, 200

Система

PCP, 262, 265

Сложность

Емкостная, 217

Пространственная, 217

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

Сортировка

Быстрая, 47–50, 242, 310

Слиянием, 45, 47

Задача, 45

Совершенное паросочетание,

Сумма размеров, 96, 97

Алгоритм, 97, 312

Задача, 96, 97

Сводимость

Карп, 230, 231, 269

Кука, 222, 229

Усиливающая, 270

Тьюринга

Машина, 199, 241

Недетерминированная,

225

Симулятор, 200

Машина Вероятностная,

241, 244, 255, 264

Упаковка

Алгоритм

Динамическое програм-

мирование, 117, 119,

121, 315

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

Усиливающая

Сводимость, 270

Векторное программирование,

179, 181

Вероятностный

Приближенный алгоритм,

172

Вершины

Независимые, 160

Вершинное покрытие, 75, 83,

311

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

237

Вычислимая

Функция, 212

Вычислимость, 212

Выполнимость

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

Выполнимость-Максимизация

Задача, 171, 173, 174, 188–

190, 268, 317

Временная сложность, 217

Язык

Разрешимый, 212

Задача

Дискретный логарифм, 20

К-покрытие, 74

Коммивояжер, 24, 25, 34–

36, 38, 43, 59, 88, 89,

94, 222–224, 226, 227,

230, 309

Коммивояжера метриче-

ская, 89, 94

Кратчайшие пути, 25, 27,

32, 59, 219

Максимальный разрез,

180, 184, 317, 318

Максимальный разрез(VP),

181, 182, 184, 185

Максимальный разрез(ЦП),

181, 182, 184

Минимальное остовное де-

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

рево, 36, 219

Наибольший общий дели-

тель, 21

Остановки, 213, 215, 221,

320

Покрытие множества, 71,

Рюкзак булев, 85, 87, 98,

99, 101, 103, 105, 136,

313

Сортировка, 45

Сумма размеров, 96, 97

Упаковка, 115–117, 122

Вершинное покрытие, 76,

78, 79, 81, 236, 237

Выполнимость, 123, 232–

235

Выполнимость-Максими-

зация, 171, 173, 174,

188–190, 268, 317

2-Satisﬁability, 235, 236,

324

2-Выполнимость, 235, 236,

324

2SAT, 235, 236, 324

3-Satisﬁability, 235, 236,

268, 271, 323

3-Выполнимость, 235, 236,

268, 271, 323

3SAT, 235, 236, 268, 271,

323

3Выполнимость-Макси-

мизация, 268, 269, 273

Discrete logarithm, 20

DNF counting, 151, 154,

155

Greatest Common Divisor,

halting problem, 213, 215,

221, 320

K-covering, 74

Knapsack, 85, 87, 98, 99,

101, 103, 105, 136, 313

MAX-3SAT, 268, 269, 273

MAX-CUT, 180, 184, 317,

318

MAX-CUT(ЦП), 181, 182,

184

MAX-CUT(VP), 181, 182,

184, 185

MAX-SAT, 171, 173, 174,

188–190, 268, 317

Minimum Spanning Tree,

36, 219

Packing, 115–117, 122

Satisﬁability, 123, 232–235

Set Cover, 71, 74

Shortest Path, 25, 27, 32,

59, 219

Sorting, 45

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

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

226, 227, 230, 309

Vertex Covering, 76, 78, 79,

81, 236, 237

2-Satisﬁability

Задача, 235, 236, 324

2-Выполнимость

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

Задача, 235, 236, 324

2SAT, 235, 236, 324

Задача, 235, 236, 324

3-Satisﬁability

Задача, 235, 236, 268, 271,

323

3-Выполнимость

Задача, 235, 236, 268, 271,

323

3SAT, 235, 236, 268, 271, 323

Задача, 235, 236, 268, 271,

323

3Выполнимость-Максимизация

Задача, 268, 269, 273

APX, 15, 44, 274, 276–279, 282,

283

APX PB, 283

BPP, 218, 240, 249–254, 259

Cложность

Временная, 217

coDTIME, 225

Complexity

Space, 217

Time, 217

coNP, 226, 230, 238–240, 246,

257, 323, 324

coNSPACE, 226

coNTIME, 226

Cook

Сводимость, 222, 229

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

263, 298, 326

coZPP, 298, 326

Cut, 179

Size, 180

Discrete logarithm, 20

Задача, 20

DNF counting, 151, 154, 155

Задача, 151, 154, 155

DSPACE, 216, 220, 225, 226

DTIME, 73, 216, 219, 225, 226

coDTIME, 225

EXPTIME, 218–220, 322

FPRAS, 150, 151, 154, 156

Алгоритм, 150

FPTAS, 104

Алгоритм, 105

GCD

Алгоритм, 21, 22

Greatest Common Divisor, 21

Задача, 21

halting problem, 213, 215, 221,

320

Задача, 213, 215, 221, 320

Heuristic, 41

Independent

Set, 160

Independent Set, 160

K-covering, 74

Задача, 74

Knapsack, 85, 87, 98, 99, 101,

103, 105, 136, 313

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

Алгоритм, 99, 101, 103, 313

Жадный, 87, 109

PTAS, 108, 109

Алгоритм Немхаузера–

Ульмана, 101, 103, 136,

143, 144, 313

Задача, 85, 87, 98, 99, 101,

103, 105, 136, 313

PTAS, 108, 109

Knapsack-SAT

Алгоритм, 97, 312

Literal, 123, 151

Machine

Turing, 199, 225, 241

Matching, 81

Perfect, 93

Matrix

Semideﬁnite, 177

MAX SNP, 279, 282, 283

MAX-3SAT, 268, 269, 273

Задача, 268, 269, 273

MAX-CUT, 180, 184, 317, 318

Алгоритм

Вероятностный, 182, 184

Задача, 180, 184, 317, 318

MAX-CUT(ЦП), 181, 182, 184

Задача, 181, 182, 184

MAX-CUT(VP), 181, 182, 184,

185

Задача, 181, 182, 184, 185

MAX-SAT, 171, 173, 174, 188–

190, 268, 317

Алгоритм

Дерандомизация, 191,

318

Вероятностный, 174,

175, 182, 190

Задача, 171, 173, 174, 188–

190, 268, 317

Maximal

Independent Set, 160, 193

Maximal independent set, 160,

193

MAXSNP, 281

Mergesort

Алгоритм, 45, 47

Minimum Spanning Tree, 36,

37, 64, 70, 219, 309

Алгоритм

Прима, 36, 37, 64, 70, 309

Задача, 36, 219

NEXP, 263

NP, 7, 8, 11–16, 34, 39, 40,

43, 44, 61, 68, 70, 71,

73, 89, 96–98, 112, 113,

117, 123, 130, 160, 171,

218, 221, 226–236, 238–

240, 245, 246, 256, 260,

261, 263–267, 269–271,

273–275, 278, 279, 282,

298, 300, 323, 324, 326

coNP, 226, 230, 238–240, 246,

257, 323, 324

NPC, 231, 236, 238, 266, 267,

269, 271, 273, 324

NPO, 275, 276, 282, 283

NSPACE, 225, 226