Page officielle du cours
Horaires
- Cours et TD : mercredi de 14h à 18h15 en salle C505 (ENS Paris-Saclay)
- Examen : 15 janvier 14h-17h
Plan du cours
Cours du 20 novembre : introduction aux algorithmes randomisés et méthode probabiliste
- Algorithmes randomisés: Monte-Carlo, Las Vegas et principe de Yao
- Méthode probabliste: argument de comptage et méthode du premier moment
Cours du 27 novembre : Flots de données massives
- Exemples introductifs
- Count-min sktech
- Couplage maximum en ligne dans les graphes bipartis
Cours du 4 décembre : Génération aléatoire
- Méthode du rejet, méthode de l'alias
- Simulation Monte Carlo des chaînes de Markov et échantillonneur de
Gibbs
Cours du 11 décembre : Graphes Aléatoires
- Introduction aux graphes aléatoires
- Graphes Erdös-Rényi, fonctions de seuil
- Rappels sur les fonctions génératrices des moments, bornes de
Chernoff
Cuors du 18 décembre : Émergence de la composante géante
- Processus de Galton-Watson
- Émergence de la composante géante
Notes de cours
N'hésitez pas à me faire remarquer toute imprécision ou erreur.
Notes jusqu'au 18 décembre.
Feuilles d'exercices
- TD1 : méthode probabiliste (20 novembre)
- TD2 : flots de données massives (27
novembre)
- TD3 : génération aléatoire (4 décembre)
- TD4 : graphes aléatoires (11 décembre)
Références
- Probability and Computing. Randomized Algorithms and Probabilistic
Analysis. M. Mitzenmacher and E. Upfal.
- The Probabilistic Method. N. Alon and J.H. Spencer.