Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Motwani R., Raghavan P. — Randomized algorithms
Motwani R., Raghavan P. — Randomized algorithms



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Randomized algorithms

Авторы: Motwani R., Raghavan P.

Аннотация:

The last decade has witnessed a tremendous growth in the area of randomized algorithms. During this period, randomized algorithms went from being a tool in computational number theory to finding widespread application in many types of algorithms. Two benefits of randomization have spearheaded this growth: simplicity and speed. For many applications, a randomized algorithm is the simplest algorithm available, or the fastest, or both.
This book presents the basic concepts in the design and analysis of randomized algorithms at a level accessible to advanced undergraduates and to graduate students. We expect it will also prove to be a reference to professionals wishing to implement such algorithms and to researchers seeking to establish new results in the area.


Язык: en

Рубрика: Computer science/Алгоритмы/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1995

Количество страниц: 476

Добавлена в каталог: 08.12.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
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
1 2 3 4
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте