Probability and Computing

Randomized Algorithms and Probabilistic Analysis

Michael Mitzenmacher, Eli Upfal

352 pages, parution le 04/04/2005

Ajouter à une liste

Indisponible

Résumé

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.

L'auteur - Michael Mitzenmacher

Michael Mitzenmacher is John L. Loeb Associate Professor in Computer Science at Harvard University.

L'auteur - Eli Upfal

Eli Upfal is Professor and Chair of Computer Science at Brown University.

Sommaire

Preface
Events and probability
Discrete random variables and expectation
Moments and deviations
Chernoff bounds
Balls, bins and random graphs
The probabilistic method
Markov chains and random walks
Continuous distributions and the Poisson process
Entropy, randomness, and information
The Monte Carlo method
Coupling of Markov chains
Martingales
Pairwise independence and universal hash functions
Balanced allocations
References
Further Reading
Index

Voir tout

Replier

Caractéristiques techniques

	PAPIER
Éditeur(s)	Cambridge University Press
Auteur(s)	Michael Mitzenmacher, Eli Upfal
Parution	04/04/2005
Nb. de pages	352
Format	18 x 26
Couverture	Relié
Poids	813g
Intérieur	Noir et Blanc
EAN13	9780521835404
ISBN13	978-0-521-83540-4