Probabilistic and Statistical Methods in Computer Science

Jean-François Mari 1 René Schott 1
1 ORPAILLEUR - Knowledge representation, reasonning
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Type de document :
Ouvrage (y compris édition critique et traduction)
Kluwer Academic Publishers, 236 p, 2001
Liste complète des métadonnées
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:52:57
Dernière modification le : jeudi 11 janvier 2018 - 06:19:52


  • HAL Id : inria-00100932, version 1



Jean-François Mari, René Schott. Probabilistic and Statistical Methods in Computer Science. Kluwer Academic Publishers, 236 p, 2001. 〈inria-00100932〉



Consultations de la notice