Probabilistic and Statistical Methods in Computer Science

Ouvrage (auteur).This book presents a large variety of applications of probability theory and statistics in computer science but we do not cover all domains of application. We focus mostly on: Probabilistic algorithm analysis: starting with the Quicksort algorithm, we switch to A.T.~Jonassen and D.E.Knuth's famous trivial dynamic algorithm whose analysis isn't. Then we lay out the basics of the probabilistic analysis of dynamic data structures. We illustrate with G.~Louchard's method applied to the linear list, then present R.~Maier's powerful large deviation analysis. Binary search trees have been deeply investigated over the last decade. We present a nice result on the width obtained by B.~ Chauvin, M.~ Drmota and J.~Jabbour-Hattab through large deviations. Then we give some hints on R.~ Cerf's probabilistic analysis of a simple genetic algorithm. A concurrency measure based on simple Markov chain features is defined and analyzed. We present also W.T.~Rhee and M.~Talagrand's analysis of bin packing problems. Some simple parallel algorithms (two stacks problem, banker algorithms) are anal yzed with the same tools as dynamic data structures. Computational geometry (and many other algorithmic fields) benefited largely from probability theory through the design and analysis of randomized algorithms. We restrict ourselves to only a few classical geometric constructions (convex hull, Voronoi diagrams and Delaunay triangulations) and follow an expository survey of O. Devillers. Applications of probabilistic tools (Hidden Markov Models, Markov Decision Processes) in speech recognition and robotics. We have decided to work out completely only a few examples. These applications show the important contributions of probabilistic techniques