Главная    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
Предметный указатель
#P      177 307 309 315 316 331
$\sigma$-field      439
Abstract optimization problem      275 277
Adaptive adversary      373
Adleman's Theorem      39
Adleman, L.      41 410 426
Aggarwal, A.      362
Aho, A.V.      25 187 189 302
Ahuja, R.K.      303
Ajtai, M.      156 361
Albers, S.      389
Aldous, D.J.      64 155 332
Aleliunas, R.      96 155
Alford, W.R.      426
All-pairs shortest paths      278—288 302
Alon, N.      97 122 123 156 160 302 361
Alt, H.      24
Althofer, I.      41
Amortization      200
Amplification of randomness      see “Probability amplification”
Anderson, R.J.      362
Angluin, D.      66 426
Ankney, N.C.      426
APD      279—288 302
APD algorithm      282—284 287 288
Approximation. hardness results      188
APSP algorithm      288
Aragon, C.R.      229 230
Arithmetization      177
Arora, S.      122 188 192
Arrangement of line segments      255
Arrangement of lines      259 274
Arthur — Merlin games      187
Aspnes, J.      97
ASYNCH-CCP algorithm      358 367
Autopartition      13 14 102 253 255 273
Azar, Y.      63
Azuma's inequality      92 97
Azuma, K.      97
Babai, L.      24 187 188 361
Bach, E.      426
Backwards analysis      235 274
Backwards analysis, convex hull algorithm      238
Backwards analysis, half-space intersection      243
Backwards analysis, trapezoidal decomposition      250
Bar-Noy, A.      389
Barany, I.      332
Basis, linear programming      263
BasisLP algorithm      270 272 274 277
Bayes' rale      440
Beaver, D.      188
Beck, J.      123
Belady, L.A.      387
Bellare, M.      122
Ben-David, S.      387
Ben-Or, M.      188 426
Bent, S.W.      63
Berger, B.      123 361 362
Berkowitz, S.I.      362
Berlekamp, E.R.      23 426
Bernoulli distribution      445
Bernoulli trial      67
Bernstein, S.N.      63 96
Bertrand's postulate      220
Bertsimas, D.      96
Bien, E.      123 155
Biggs, N.      155
Billingsley, P.      97 438
Binary partition      252 273
Binary partition, 3 dimensions      254—256
Binary partition, planar      11—14 102
Binary tree, endogenous      198
Binary tree, full      198
Binomial coefficients      434
Binomial distribution      59 67 445
Birthday problem      45
Blum, A.      388
Blum, M.      63 156 186 188 189 193 232
Bollobas, B.      97
Boole — Bonferroni inequalities      44 440
Boolean circuit family      38
Boolean decision diagram      187
Boppana, R.B.      24 41 187
Borodin, A.      96 155 362 387
Boruvka's algorithm      297—298 303
Bovet, D.P.      25
BoxSort algorithm      339—341 361 363
Boyer, R.S.      187
bpp      22 151 309 337 423
BPWM algorithm      286—288 302 304
Brebner, G.J.      96
Broder, A.Z.      63 123 155 332
Buffon, G.      24
Byzantine agreement problem      358—361 363
ByzGen algorithm      360 361 363 367
Carmichael number      419 420 423 426—428
Carmichael, R.D.      426
Carter, J.L.      229 232 233
Cauchy — Schwarz inequality      436
Chandra, A.K.      155 186 189
Characteristic equation      437
Characteristic vector      160
Chazelle, B.      123 273 274
Chebyshev bound      47 63
Chebyshev — Cantelli bound      64
Chebyshev, P.L.      63
Chernoff bound      67—79
Chernoff bound, global wiring      79
Chernoff bound, oblivious routing      77
Chernoff bound, occupancy problem      73
Chernoff bound, sum of geometric variables      98
Chernoff, H.      63 96
Chew, L.P.      274
Chinese remainder theorem      396 408 422 423
Chistiakov, V.P.      63 97
Chistov, A.L.      362
Choice coordination problem      355—358 363
Chor, B.      63 363
Chrobak, M.      387 388
Chromatic number      93 97
Chung, F.R.K.      160
Chvatal, V.      274
Clarkson, K.L.      273 274
Clique number      91
CNF      18
co-BPP      27
co-IP      192
Co-NP      20 143 173 177 417
co-PP      27
co-PSPACE      20
co-RP      21 191 423 426
Cohen, A.      123 156
Cole, R.      361
Commute time      see “Random walk commute
Competitive analysis      368
Competitive analysis, Marker algorithm      376
Competitive analysis, Reciprocal algorithm      382
Competitiveness      370
Complexity classes      18—23
Compositeness      417
Concave function      107 124
Conditional probability      121 440
Conductance      see “Markov chain”
Connected component      139
Contract algorithm      290—292 294 303 305
Contraction      290 297
Convex function      98
Convex hull      236 239
Convex hull, 3 dimensions      241
Convex hull, planar      236—239
Cook, S.A.      155 361
Coppersmith, D.      187 193 302 388
Cormen, T.      302
Coupon collector's problem      57—63
Coupon collector's problem, sharp threshold      61—63
Courant — Fisher equalities      147 159
Cover time      see “Random walk cover
Crescenzi, P.      25
Cryptography      187
Csanky, L.      362
Cvetkovic, D.M.      155
Dagum, P.      332
Dantzig, G.B.      275
Data structures      197—233
Data structures, DELETE operation      197
Data structures, FIND operation      197
Data structures, INS operation      197
Data structures, JOIN operation      197
Data structures, MAKESET operation      197
Data structures, PASTE operation      197
Data structures, SPLIT operation      197
Davenport, H.      426
de Leeuw, K.      23
Delaunay triangulation      245—247
Delaunay triangulation, of a convex polygon      248
DeMillo, R.A.      187
Derandomization      39 63 120 121 274 302 303 346 364
Determinant      see “Matrix”
Diameter, graph      281
Diameter, point set      256—258
Diameter, polytope      275
Dictionary problem, dynamic      214 218
Dictionary problem, static      213
Dietzfelbinger, M.      229
Dijkstra, E.W.      302 303
Dinwoodie, I.H.      156
Discrete log problem      402
Disjunctive normal form      see “DNF”
Distributed algorithms      97
Distributional complexity      34
Dixon, B.      303
DNF      307
DNF counting problem      310—315
Donath, W.      156
Doob, J.L.      97
Doob, M.      155
Doubly stochastic matrix      see “Matrix”
Doyle, P.G.      155 388
Duality      see “Geometric duality”
Dubins, L.E.      97
Dwork, C.      363
Dyer, M.E.      332
Dymond, P.W.      155
Edelsbrunner, H.      273 274
Edge coloring      389
Edmonds matrix      167
Edmonds' Theorem      167
Edmonds, J.      167 187 190
Effective resistance      135
Effective resistance, Short-cut Principle      138
Effective resistance, triangle inequality      138
Eigenvalue      437
Eigenvector      437
Electrical networks      135—137
Electrical networks, Short-cut Principle      138
Elias, P.      302
Erdos, P.      122 123
ERH      405 425 426
Euclid's Algorithm      393 394 414
Euclid's algorithm, extended version      395 427
Euler totient function      397
Euler's criterion      404 413
Euler's theorem      399
EXP      20
expanders      108—112 123 143 145 152
Expanders, application to probability amplification      110—112 151—155
Expanders, existence proof      109—110
Expanders, explicit construction      110
Expanders, Gabber — Galil      145
Expanders, magnifiers      156
Expanders, rapid mixing property      144
Expanders, relation to eigenvalues      144—151
Expanders, super-concentrators      156
Extended Euclidean algorithm      395 427
Extended Riemann hypothesis      see “ERH”
Factoring      399 401 403 409—412 417 426
FastCut algorithm      294 303
Feder, T.      187 302
Feige, U.      188
Feigenbaum, J.      188
Feinstein, A.      302
Feller, W.      63 97 438
Fermat congruence      418
Fermat's theorem      399 418
Fermi, E.      24
Fiat, A.      387 388
Fibonacci number      191 435
Fich, E.E.      41
FIFO      see paging problem FIFO
Find algorithm      15 24 26
Fingerprint      161 168 190 214
Fischer, M.J.      363
Floyd, R.W.      63 302
Ford, L.R.      302
Fortnow, L.      188 192
FPAS      see “Fully polynomial approximation scheme”
FPRAS      see “Fully polynomial randomized approximation scheme”
Fredman, M.L.      229 233 303
Free Boolean graphs      186
Freivalds' technique      162
Freivalds, R.      186
Friedman, J.      123 274
Frieze, A.M.      123 332
Fulkerson, D.R.      302
Fully polynomial approximation scheme      308
Fully polynomial randomized approximation scheme      309
Function, linear      185
Function, nearly linear      185
Furedi, Z.      332
Gabber, O.      123 156
Gabow, H.      303
Gale, D.      63
Galil, Z.      123 156 302 303 362
Game theory      31—34
Game tree evaluation      28—30 102
Gartner, B.      275
Gecsei, J.      387
Gemmell, P.      188
Geometric algorithms      234—277
Geometric distribution      10 57 300 446
Geometric duality      239—241
Gill, J.      23 41 155
Gillman, D.      156
Global wiring      79—83
Goebel, F.      155
Goemans, M.X.      96 122
Goldberg, A.      303 362
Goldberg, M.      361
Golden ratio      435
Goldreich, O.      63 187 188
Goldwassei, M.      275
Goldwasser, S.      187 188 426
Gomory, R.E.      302
Graham, R.L.      229 303 433
Granville, A.      426
Graph algorithms      278—305
Graph isomorphism      173 187
Graph non-isomorphism      173 187
Greedy MIS algorithm      342
Greene, D.H.      433
1 2 3 4
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2018
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте