Probabilistic and Statistical Methods in Computer Science

Jean-François Mari; René Schott

inria-00100932, version 1

Probabilistic and Statistical Methods in Computer Science

Jean-François Mari ()^a^, 1, René Schott^b^, 1

Probabilistic and Statistical Methods in Computer Science (2001) 236 p

a – UNIVERSITE NANCY 2
b – UNIVERSITE HENRI POINCARE
1 : ORPAILLEUR (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL) France

Références bibliographiques

inria-00100932, version 1
http://hal.inria.fr/inria-00100932
oai:hal.inria.fr:inria-00100932
Contributeur : Publications Loria <>
Soumis le : Mardi 26 Septembre 2006, 14:52:57
Dernière modification le : Jeudi 28 Septembre 2006, 15:22:47

Voir la fiche concise

Exporter

Bibtex EndNote TEI RefWorks

%% inria-00100932, version 1
%% http://hal.inria.fr/inria-00100932
@book{mari:inria-00100932,
    hal_id = {inria-00100932},
    url = {http://hal.inria.fr/inria-00100932},
    title = {{Probabilistic and Statistical Methods in Computer Science}},
    author = {Mari, Jean-Fran{\c c}ois and Schott, Ren{\'e}},
    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.}},
    keywords = {probability; statistic; hmm; mdp; probabilistic algorithm analysis || probabilit{\'e}; statistique; mod{\`e}le de markov cach{\'e}; processus de d{\'e}cision markovien; analyse probabiliste d'algorithmes},
    language = {Anglais},
    affiliation = {ORPAILLEUR - INRIA Lorraine - LORIA},
    publisher = {Kluwer Academic Publishers},
    pages = {236 p},
    note = {Ouvrage (auteur). A01-R-010 || mari01a A01-R-010 || mari01a },
    year = {2001},
}

%F inria-00100932, version 1
%0 Book
%U http://hal.inria.fr/inria-00100932
%2 INFO:INFO_OH
%T Probabilistic and Statistical Methods in Computer Science
%A Mari, Jean-François
%A Schott, René
%+ ORPAILLEUR - INRIA Lorraine - LORIA
%X 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.
%G Anglais
%8 2001-00-00
%2 
%I Kluwer Academic Publishers
%P 236 p
%K probability; statistic; hmm; mdp; probabilistic algorithm analysis || probabilité; statistique; modèle de markov caché; processus de décision markovien; analyse probabiliste d'algorithmes
%Z Ouvrage (auteur).
%Z A01-R-010 || mari01a