Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis

ISBN-13: 9781107154889 / Angielski / Twarda / 2017 / 484 str.

Michael Mitzenmacher; Eli Upfal

Opis

This greatly expanded new edition offers a comprehensive introduction to randomization and probabilistic techniques in modern computer science.

Recenzje

'As randomized methods continue to grow in importance, this textbook provides a rigorous yet accessible introduction to fundamental concepts that need to be widely known. The new chapters in this second edition, about sample size and power laws, make it especially valuable for today's applications.' Donald E. Knuth, Stanford University, California

Spis treści

1. Events and probability; 2. Discrete random variables and expectations; 3. Moments and deviations; 4. Chernoff and Hoeffding bounds; 5. Balls, bins, and random graphs; 6. The probabilistic method; 7. Markov chains and random walks; 8. Continuous distributions and the Polsson process; 9. The normal distribution; 10. Entropy, randomness, and information; 11. The Monte Carlo method; 12. Coupling of Markov chains; 13. Martingales; 14. Sample complexity, VC dimension, and Rademacher complexity; 15. Pairwise independence and universal hash functions; 16. Power laws and related distributions; 17. Balanced allocations and cuckoo hashing.

O autorze

Mitzenmacher, Michael Michael Mitzenmacher is a Professor of Computer Science in the School of Engineering and Applied Sciences at Harvard University, Massachusetts. Professor Mitzenmacher has authored or co-authored over 200 conference and journal publications on a variety of topics, including algorithms for the internet, efficient hash-based data structures, erasure and error-correcting codes, power laws, and compression. His work on low-density parity-check codes shared the 2002 IEEE Information Theory Society Best Paper Award and won the 2009 ACM SIGCOMM Test of Time Award. He was elected as the Chair of the ACM Special Interest Group on Algorithms and Computation Theory in 2015. Upfal, Eli Eli Upfal is a Professor of Computer Science at Brown University, where he was also the department chair from 2002 to 2007. Prior to joining Brown in 1998, he was a researcher and project manager at the IBM Almaden Research Center, and a professor at the Weizmann Institute of Science, Israel. His main research interests are randomized algorithms, probabilistic analysis of algorithms, and computational statistics, with applications ranging from combinatorial and stochastic optimization, massive data analysis and sampling complexity to computational biology, and computational finance.