Structures et Algorithmes Aléatoires
Horaires
- Cours : mercredi de 10h45 à 13h15 en salle U/V
- TD : vendredi de 15h45 à 17h45 en salle U/V
- Examen : mercredi 21 janvier de 10h45 à 13h15 en salle U/V, les notes de cours ne sont pas autorisées, mais une feuille de notes au format A4 (recto/verso) sera autorisée.
Intervenants
Si vous avez des questions, n'hésitez pas à leur envoyer un mail : prenom.nom@ens.fr
Résumé 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
Plan du cours
Cours du 24 septembre : événements et probabilités
- Introduction : égalité de deux polynômes, file d'attente
- Événements, axiomes des probabilités
- Indépendance, probabilité conditionnelle, lois de Bayes
Cours du 1er octobre : variables aléatoires
- Variables aléatoires et lois de probabilité. Exemples : Lois Bernoulli, binomiales, géométriques
- Espérance et variance. Linéarité de l'espérance, collectionneur de coupons
- Inégalités de Markov et de Tchebychev
Cours du 8 octobre : fonctions génératrices et applications
- Fonctions génératrices : définition, lien avec les moments, caractérisation d'une loi, égalité de Wald
- Processes de branchement de Galson-Watson, probabilité d'extinction
- Bornes de Chernoff, application au tri rapide.
Cours du 15 octobre : urnes et balles
- Modèle d'urnes et de balles, charge maximale d'une urne
- Limite de la loi binomiale : distribution de Poisson; approximation poissonnienne : borne inférieure de la charge maximalde d'une urne
- Puissance de deux choix, amélioration de la charge maximale
Cours du 22 octobre : la méthode probabiliste
- Argument de comptage : nombre de Ramsey
- Méthode du premier moment : MAXSAT et ensemblees indépendants
- Méthode du second moment : graphes Erdös-Rényi, fonction-seuil pour les cliques de taille 4 ; schéma de Flajolet-Martin
Cours du 24 octobre : le lemme local de Lovàsz
- Énoncé, application à k-SAT
- Preuve constructive
Cours du 12 novembre : émergence de la composante géante
- Énoncé, application à la propagation de virus
- Preuve : régime sous-critique, régime sur-critique
Cours du 19 novembre : Chaînes de Markov
- Définition, propriété de Markov, indépendance du passé et du futur conditionnellement au présent
- Représentations : matricielles, fonctionelles et graphiques (période, classes de communication, irréductibilité)
- Mesure invariante, distribution stationnaire, réversibilité.
Cours du 26 novembre : Classification des états , existence de mesures invariantes et probabilités stationnaires
- Temps d'arrêt, propriété de Markov forte
- Classification des états : états transitoires, récurrents nuls et récurrents positifs, critère de la matrice du potentiel
- Existence et unicité à un facteur multiplicatif près de la mesure invariante pour les chaînes irréductibles et récurrentes
- Existence et unicité de la distribution stationnaire pour les chaînes irréductibles et récurrentes positives
Cours du 3 décembre : théorème ergodique et simulation
- Théorème ergodique, théorème de Kolmogorov
- Génération de variables aléatoires discrètes, méthode de l'alias
Cours du 10 décembre : simulation de chaînes de Markov
- Echantillonneur de Gibbs et simulation MCMC
- Temps de mélange, couplage de chaînes de Markov
Cours du 17 décembre : simulation parfaite des chaînes de Markov
- Algorithme de Propp et Wilson
- Chaînes monotones, chaînes bornantes
Notes de cours
Notes jusqu'au 12 novembre.
Il y a certainement des erreurs, merci de m'en faire part.
Feuilles de TDs
- TD1 du 26 septembre 2014 : événements et
probabilités
- TD2 du 3 octobre 2014 : variables aléatoires,
espérance et variance
- TD3 du 10 octobre 2014 : fonctions génératrices
- TD4 du 17 octobre 2014 : boules et urnes
- TD5 du 5 novembre 2014 : la méthode probabiliste
- TD6 du 7 novembre 2014 : le lemme local de Lovasz
- TD7 du 14 novembre 2014 : graphes petit-monde
- TD8 du 21 novembre 2014 : chaînes de Markov
- TD9 du 28 novembre 2014 : chaînes de Markov
- TD10 du 5 décembre 2014 : chaînes de Markov
- TD11 du 12 décembre 2014 : simulation des chaînes de Markov
Devoirs maison
Chaque devoir maison comptera entre 10% et 15% de la note finale.
- DM1, à rendre le 22 octobre
- DM2, à rendre le 10 décembre. Attention,
le sujet a été corrigé le 4 décembre.
- DM3, à rendre le 14 janvier.
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