Structures et Algorithmes Aléatoires
Horaires
- Cours : vendredi de 13h45 à 16h15 en salle U/V
- TD : mercredi de 11h à 13h en salle R
Intervenants
- Pierre Brémaud (Cours - partie 2)
- Anne Bouillard (Cours - partie 1 + TD)
Si vous avez des questions, n'hésitez pas à leur envoyer un mail : prenom.nom@ens.fr
Plan du cours
Ce cours vise à donner aux étudiants les bases de probabilités qui sont utilisées dans divers domaines de l'informatique (algorithmique, algorithmes stochastiques, réseaux de communication,...). Il est divisé en deux parties :
- Probabilités discrètes et applications
- Variables aléatoires, indépendance, conditionnement
- Méthode probabiliste
- Graphes aléatoires
- Modèles markoviens
- Chaînes de Markov, comportement asymptotique
- Simulation Monte Carlo et simulation parfaite
- Champs de Gibbs
Notes de cours
Feuilles de TDs
- TD1 (3 octobre 2012) : Événements, indépendance
- TD2 et TD2 bis (17 octobre 2012) : Variables aléatoires, espérance, variance, flots de données
- TD3 (24 octobre 2012) : Fonctions génératrices
- TD4 (31 octobre 2012) : Méthode probabiliste
- TD5 (14 novembre 2012) : Lemme de Lovàsz
- TD6 (21 novembre 2012) : Distribution de Poisson, urnes et balles
- TD7 (28 novembre 2012) : Routage dans un graphe
- TD8 (5 décembre 2012) : Chaînes de Markov
- TD9 (12 décembre 2012) : Chaînes de Markov
- TD10 (19 décembre 2012) : Chaînes de Markov
Devoir maison
Devoir à rendre pour le 12 décembre.
Références
- Markov chains: Gibbs fields, Monte Carlo simulation and queues,
P. Brémaud, Springer, New York, 2nd printing, 2001.
- Probability and Computing. Randomized Algorithms and Probabilistic
Analysis. M. Mitzenmacher and E. Upfal.
- The Probabilistic Method. N. Alon and J.H. Spencer.
Examens des années précédentes
Pages des années précédentes