|
|
Авторизация |
|
|
Поиск по указателям |
|
|
|
|
|
|
|
|
|
|
Motwani R., Raghavan P. — Randomized algorithms |
|
|
Предметный указатель |
Paging problem, Random algorithm 383 384 388
Paging problem, weighted 381
Pairwise independence 51 52 220 221 362 364 441 442
Palem, K. 97 100
Pan, V. 302 362
Papadimitriou, C.H. 25 155 156 187 188 191 388
Parabolic transformation 246
Parallel algorithms 335—355
Parallel Matching algorithm 354 355 362 365
Parallel MIS algorithm 343 346 361 364
Parallel random access machine see “PRAM”
PAS see “Polynomial approximation scheme”
Patashnik 6 433
Paterson, M.S. 24 63 273 361 363
Pattern matching 170 190
Pattern matching, two-dimensional 191
Payne, X. 387
Payoff matrix 31
PCP 180 188
Pease, M. 363
Peleg, D. 123
Perfect hash function 215
Perfect matching 66 145 167 190 347—355 365 366
Permanent see “Matrix permutation”
Permanent, sign 165 351
Permanent, value 351
Permutation routing 74 112
Permutation routing, lower bound 75
Phillips, S.J. 303
Pinsker, M. 123
Pippenger, N.J. 63 123 362
Plotkin, S. 362
Plummer, M.D. 362
Podderyugin, V.D. 302
Point location 259—262
Poisson distribution 59 446
Poisson heuristic 59
Poisson trials 68
Polynomial approximation scheme 308
Polynomial product verification 164
Polynomial randomized approximation scheme 309
Polynomial reduction 20
Polynomial time 19
PolyRoot algorithm 416 417 426
Pomerance, C. 426
PP 22
PRAM 74 335 337
PRAS see “Polynomial randomized approximation scheme”
Pratt, V.R. 63 187 426
Prim, R.C. 303
Primality, certificate of 417
Primality, testing 417—425
Primality1 algorithm 421 423 426
Primality2 algorithm 424
Primality3 algorithm 425 426 428
Prime number theorem 168 428
Principle of Deferred Decisions 55 56 163 175 300
Probabilistic method 14 101—126
Probabilistic method, expanders 108
Probabilistic method, kth moment inequality 124
Probabilistic method, oblivious routing 112
Probabilistic method, universal traversal sequences 141
Probabilistic recurrence 15 24
Probabilistically checkable proofs 180
Probability amplification 53 110—112 151—155
Probability measure 439
Probability space 439
Probability vector 131 143
Program checking 162 186 188
Proof verification 180—187
Pruhs, K. 24
PSPACE 20 176 177 188 191
Public-key encryption 410
Pugh, W. 229 232
Pure strategy 33
QBF 191
Quadratic residue 403 405 408
QuadRes algorithm 405 407 413 425 426
Quantified boolean formula 191
Quicksort 337 363
Quicksort, sharp concentration 97
Rabani, Y. 387 388
Rabin cryptosystem 412 427
Rabin, M.O. 23 187 190 191 273 362 363 365 367 412 426—428
Rackoff, C. 155 187
Ragde, P.L. 41
Raghavan, P. 96 97 123 155 387 388 390
Raiffa, H. 40
RAM 16 229 234 335
RAM, log-cost 18 171
RAM, uniform 18
RAM, unit-cost 18 162 393
Ramachandran, V.L. 361
RandAuto algorithm 13 102 126 252 253 255 273
Random graph 66 90 97 109 111 112 115 143 299 332
Random sampling, geometric algorithms 258—262
Random sampling, linear programming 262
Random sampling, point location 259—262
Random Simplex algorithm 275
Random treap 203
Random variable 441
Random walk 127—160 362
Random walk, 2-SAT algorithm 129 136
Random walk, application to probability amplification 151—155
Random walk, commute time 133
Random walk, cover time 133 137—139
Random walk, expanders 143—155 320
Random walk, graph connectivity 139—143 148
Random walk, hitting time 133
Random walk, stationary distribution 132
Random walk, transition matrix 129
Randomized incremental algorithm 234
Randomized incremental algorithm, Delaunay triangulation 247
Randomized incremental algorithm, half-space intersection 241
Randomized incremental algorithm, linear programming 268
Randomized incremental algorithm, trapezoidal decomposition 248
Randomized rounding 81 96 105 106
RandQS algorithm 3—5 24 99
Rank 365
Rank, in ordered set 4
Rank, matrix 187 190
Rao, S. 123 303
Rapid mixing 144 148 320 323 331 332
Rauch, M. 303
Ravid, Y. 387 388
Reciprocal algorithm 382 383 387 388 391
Reed, B.A. 97
Reif, J.H. 361
Reingold, N. 389
Reischuk, R. 361
Relative pointwise distance 148 159 322
Request-answer game 378
Rivest, R.L. 63 302 410 426
RLP 139
RNC 337 342 346 347 349 362—367
Rohnert, H. 229
Romani, F. 302
Rompel, J. 123 188 192 361 362
Row-major form see “Matrix”
RP 21 23 52 110 112 151 337 423
RSA scheme 410—412 426 428
Rub, C. 96
Rubinfeld, R. 188 193
Rudolph, L. 387
Ruzzo, W.L. 155
Ryser, H. 331
s-t min-cut 26 289
Sachs, H. 155
Safra, S. 188 192
Saks, M.E. 41 158 387 388
| SampLP algorithm 264
SAT 19 115 117 128 155 176
SAT, arithmetization 177
SAT, counting 188
SAT, counting version 176
Savage, L.J. 97
Schieber, B. 96
Schmidt, J.P. 96
Schonhage, A. 63
Schoning, U. 188
Schrijver, A. 274
Schwartz — Zippel Theorem 165
Schwartz, J.T. 165 187
Search tree 258
Search tree, balanced 200
Search tree, binary 5 198
Search tree, finger 230
Search tree, rotation 199
Search tree, splay operation 200
Second moment method 53
Seidel, R.G. 229 2.30 274 302
SeideLP algorithm 268 269 274
Selection algorithm 47—51 363
Self-reducibility 316
Selfrdige, J.L. 123
Semidefinite programming 122
Set-balancing problem 73 99 102 120
Set-cover problem 99
Sevastianov, B.A. 63 97
Shallit, J.O. 426
Shamir, A. 188 191 192 410 426
Shamir, E. 97
Shannon, C.E. 23 302
Shapiro, N. 23
Shapley, L.S. 63
Shark, M. 274 275
Sharp threshold 63
Shen, A. 192
Shiloach, Y. 362
Shmoys, D.B. 362
Shor, P.W. 273
Shortest path algorithm 278—288
Shostak, R. 363
Siegel, A. 96
Similar matrices see “Matrix”
Simplex algorithm 263
Sinclair, A. 24 332 334
Sinha, R. 186
Sipser, M. 123 188 192
Skew-symmetric matrix 190
Skip lists 209—213
Sleator, D.D. 228 387 389
Slutz, D.R. 387
Smallest enclosing ball 277
Smolensky, R. 155
Snell, J.L. 155
Snir, M. 40 387 388
Solovay, R. 23 426
Sorting algorithm 3 9 235 337
Spanning trees, counting problem 307
Spencer, J.H. 97 122 123
Spencer, T. 303 361
Speranza, M.G. 24
Spirakis, P. 97 100
Sprugnoli, R. 229
Srinivasan, A. 96
Stable marriage problem 53—57
Stable marriage problem, Amnesiac Algorithm 56
Stable marriage problem, Proposal Algorithm 54 63 66
Stationary distribution see “Markov chain stationary
STCON 142
Stein, C. 303
Stirling's formula 434
Stirzaker, D.R. 97 438
Stochastic domination 56 213 299 300 443
Stochastic matrix see “Matrix”
Stockmeyer, L.J. 331
Strang, G. 433
Strassen, V. 23 426
Strong component 130
Strongly k-universal hash functions 221
Strongly universal hash functions 221
Sudan, M. 96 122 188
Super-concentrators see “Expanders”
Symmetric order 198
SYNCH-CCP algorithm 356
Szegedy, M. 122 188
Szemeredi, E. 156 160 229 233 361
Tail probability 43
Tanner, R.M. 156
Tardos, G. 387
Tarjan, R.E. 63 229 302 303 387 389
Tarsi, M. 41
Teia, B. 389
Tetali, R. 155
Thompson, C.D. 96
Timofeev, E.A. 302
Tiwari, P. 155
Tompa, M. 155
Total variation distance 159
Traiger, I.L. 387
Transition probability matrix 129 148
Transition probability matrix, doubly stochastic 134 148
Transparent proofs 188
Trapezoidal decomposition 248—252
Treap 201—208
Treap, random 203
Treap, weighted 230
Treat, A. 363
Tree isomorphism 188
Triangle inequality 436
Truth assignment 19
Tsantilas, T. 96
Turing machine 16 140
Turing machine, log-space 139 159
Turing machine, probabilistic 17 23 139
Tutte matrix 190 347 348 351 365
Tutte's theorem 190 347 351
Tutte, W.T. 187 190
Two-point sampling 51 53
Two-sided error 22
Ulam, S. 24
Ullman, J.D. 25 187 189 302
Uniform algorithm 38
Universal hash functions 170 213—221
Universal traversal sequence 140
Upfal, E. 24 63 96 123 362 366
USTCON 139
Vaidya, P. 362
Valiant's scheme see “Oblivious routing randomized”
Valiant, L.G. 66 96 331 332 362
Van der Waerden, B.L. 426
Vandermonde matrix 165
Vazirani, U.V. 187 332 362 365—367
Vazirani, V.V 187 190 332 362 365—367
Vector norms 435
Vector space 435
Vector space, basis 437
Vector space, orthogonal subspace 435
Vector space, orthonormal basis 437
Vector space, subspace 435
Vercellis, C. 24
Vinogradov, I.M. 426
Viswanathan, S. 387
Vizing, V.G. 362
Vohra, R. 96
Volume estimation 329—331
von Neumann's Minimax Theorem 33
von Neumann, J. 24 25 33 40
von zur Gathen, J. 362
|
|
|
Реклама |
|
|
|