Probability and Computing: Randomized Algorithms and Probabilistic Analysis

Framsida
Cambridge University Press, 31 jan. 2005 - 352 sidor
Randomization and probabilistic techniques play an important role in modern computer science, with applications ranging from combinatorial optimization and machine learning to communication networks and secure protocols. This textbook is designed to accompany a one- or two-semester course for advanced undergraduates or beginning graduate students in computer science and applied mathematics. It gives an excellent introduction to the probabilistic techniques and paradigms used in the development of probabilistic algorithms and analyses. It assumes only an elementary background in discrete mathematics and gives a rigorous yet accessible treatment of the material, with numerous examples and applications. The first half of the book covers core material, including random sampling, expectations, Markov's inequality, Chevyshev's inequality, Chernoff bounds, balls and bins models, the probabilistic method, and Markov chains. In the second half, the authors delve into more advanced topics such as continuous probability, applications of limited independence, entropy, Markov chain Monte Carlo methods, coupling, martingales, and balanced allocations. With its comprehensive selection of topics, along with many examples and exercises, this book is an indispensable teaching tool.
 

Så tycker andra - Skriv en recension

Vi kunde inte hitta några recensioner.

Innehåll

II
1
V
3
VI
8
VII
12
VIII
14
IX
20
XI
22
XII
23
LXXIX
177
LXXX
182
LXXXI
188
LXXXII
191
LXXXIII
193
LXXXIV
194
LXXXV
196
LXXXVI
197

XIII
25
XIV
26
XV
30
XVI
32
XVII
34
XVIII
38
XIX
44
XX
45
XXI
48
XXII
50
XXIII
52
XXIV
53
XXV
54
XXVI
57
XXVII
61
XXVIII
63
XXIX
67
XXXI
69
XXXII
71
XXXIII
72
XXXIV
73
XXXV
78
XXXVI
83
XXXVII
90
XL
92
XLI
93
XLII
94
XLIII
98
XLIV
99
XLV
104
XLVI
106
XLVII
107
XLVIII
109
XLIX
111
L
112
LI
113
LII
119
LIII
124
LIV
126
LV
128
LVI
129
LVII
130
LVIII
131
LIX
133
LX
134
LXI
135
LXII
136
LXIII
138
LXIV
141
LXV
142
LXVII
143
LXVIII
146
LXIX
148
LXX
153
LXXI
156
LXXII
159
LXXIII
163
LXXIV
166
LXXV
167
LXXVI
173
LXXVII
174
LXXVIII
176
LXXXVII
199
LXXXVIII
201
LXXXIX
204
XC
205
XCI
207
XCII
210
XCIII
212
XCIV
213
XCV
216
XCVII
219
XCVIII
225
XCIX
228
C
230
CI
234
CII
237
CIII
245
CIV
252
CV
255
CVII
257
CVIII
259
CIX
263
CX
265
CXI
267
CXII
270
CXIII
271
CXIV
274
CXV
275
CXVI
276
CXVII
277
CXVIII
278
CXIX
281
CXX
282
CXXI
286
CXXII
289
CXXIII
295
CXXIV
297
CXXV
299
CXXVI
300
CXXVII
303
CXXVIII
305
CXXIX
307
CXXX
308
CXXXI
309
CXXXII
314
CXXXV
315
CXXXVI
316
CXXXVII
317
CXXXVIII
318
CXXXIX
319
CXL
321
CXLI
323
CXLII
324
CXLIII
326
CXLIV
328
CXLV
333
CXLVI
336
CXLVII
341
CXLVIII
344
CL
345
CLI
349
CLII
350
Upphovsrätt

Andra upplagor - Visa alla

Vanliga ord och fraser

Om författaren (2005)

Michael Miztenmacher is a John L. Loeb Associate Professor in Computer Science at Harvard University. Having written nearly 100 articles on a variety of topics in computer science, his research focuses on randomized algorithms and networks. He has received an NSF CAREER Award and an Alfred P. Sloan Research Fellowship. In 2002, he shared the IEEE Information Theory Society Best Paper Award for his work on error-correcting codes.

Eli Upfal is Professor and Chair of Computer Science at Brown University. He has published more than 100 papers in refereed journals and professional conferences, and is the inventor of more than ten patents. His main research interests are randomized computation and probabilistic analysis of algorithms, with applications to optimization algorithms, communication networks, parallel and distributed computing and computational biology.

Bibliografisk information