Probabilités et applications en algorithmique
Cours : Yves Robert (Yves.Robert)
TD : Jean-Baptiste Rouquier (Jean-Baptiste Rouquier)
Présentation
Le cours commence par une introduction aux notions de base du calcul
des probabilités (mesures de probabilités, évênements, variables
aléatoires, espérance...).
On présentera ensuite quelques outils importants pour les
applications à l'algorithmique et à la combinatoire.
En ce qui concerne l'algorithmique, je présenterai et j'analyserai quelques
algorithmes probabilistes (c'est-à-dire
des algorithmes dont le déroulement dépend de choix aléatoires).
Les applications combinatoires sont fondées sur la “méthode
probabiliste”:
il s'agit de donner des preuves probabilistes de l'existence de
certains objets combinatoires.
Le cours se terminera par une introduction aux marches au hasard et
aux chaînes de Markov.
Bibliographie
-
R. MOTWANI and P. RAGHAVAN. Randomized algorithms. Cambridge
University Press, 1995.
- P. BILLINGSLEY. Probability and measure. Wiley, 1995.
- W. FELLER. An introduction to probability theory and its
applications. Wiley, 1968.