Probabilistics Aspects of Computer Science (Random graphs)
Horaires
- Cours et TD : mardi de 14h à 16h en salle C509-511 (ENS Cachan)
- Examen : mardi 13 janvier 2015
Intervenants
- Anne Bouillard (Cours
graphes aléatoire)
- Serge Haddad et Nicolas Schabanel pour les autres parties
Plan du cours
Cours du 18 novembre : graphes Erdös-Rényi
- Rappels de probabilités : Méthodes du premier et du second moment
- Graphes Erdös-Rényi : définition G(n,p), étude des propositions du
premier ordre quand p fixé
- Quand p varie avec n : fonction de seuil, application à la clique
de taille 4
Cours du 25 novembre : processs de Galton-Watson
- Rappels de probabilités : fonction génératrices, égalité de Wald
- Processus de Galton-Watson : probabilité d'extinction
- Rappels de probabilités : bornes de Chernoff
Cours du 2 décembre : séance de TD
Cours du 9 décembre : émergence de la composante géante
- Enoncé du théorème
- Comparaison entre parcours en largeur et processus de branchement GW
avec loi binomiale
- Preuve du régime sous-critique
- Preuve du régime sur-critique
Cours du 16 décembre : autres types de graphes aléatoires
- Attachement préférentiel
- TD : graphes structurés et effet petit-monde
Cours du 6 janvier : autres types de graphes aléatoires
- Modèle des configurations
- TD : graphes à clés et transitivité
Notes de cours
N'hésitez pas à me faire remarquer toute imprécision ou erreur. Les
exercices de TD sont au fil du cours.
Notes jusqu'au 6 janvier.
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.