Structures et Algorithmes Aléatoires

Annonces

Horaires

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 :
  1. Probabilités discrètes et applications
  2. Modèles markoviens

Notes de cours

Feuilles de TDs

Devoirs maison

Chaque devoir maison comptera pour 10% de la note finale.

Plan du cours

Cours du 2 octobre : événements et probabilités

  1. Introduction : égalité de deux polynômes, file d'attente
  2. Événements, axiomes des probabilités
  3. Indépendance, probabilité conditionnelle, lois de Bayes
  4. Méthode probabiliste :argument de comptage

Cours du 9 octobre : espérance et méthode du premier moment

  1. Variables aléatoires et lois de probabilité. Exemples : Lois Bernoulli, binomiales, géométriques
  2. Espérance. Linéarité de l'espérance, collectionneur de coupons
  3. Méthode du premier moment : MAXSAT et ensemblees indépendants

Cours du 16 octobre : variance et méthode du second moment

  1. Variance, inégalité de Tchebychev, application au collectionneur de coupons
  2. 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 30 octobre : le lemme local de Lovàsz

  1. Énoncé, application à k-SAT
  2. Preuve constructive

Cours du 6 novembre : fonctions génératrices et applications

  1. Fonctions génératrices : définition, lien avec les moments, caractérisation d'une loi, égalité de Wald
  2. Processes de branchement de Galson-Watson, probabilité d'extinction
  3. Bornes de Chernoff, application au tri rapide.

Cours du 13 novembre : urnes et balles

  1. Modèle d'urnes et de balles, charge maximale d'une urne
  2. Limite de la loi binomiale : distribution de Poisson; approximation poissonnienne : borne inférieure de la charge maximalde d'une urne
  3. Puissance de deux choix, amélioration de la charge maximale

Cours du 20 novembre : émergence de la composante géante

  1. Énoncé, application à la propagation de virus
  2. Preuve : régime sous-critique, régime sur-critique

Cours du 27 novembre : Chaînes de Markov

  1. Définition, propriété de Markov, indépendance du passé et du futur conditionnellement au présent
  2. Représentations : matricielles, fonctionelles et graphiques (période, classes de communication, irréductibilité)
  3. Mesure invariante, distribution stationnaire, réversibilité.

Cours du 4 décembre : Classification des états , existence de mesures invariantes et probabilités stationnaires

  1. Temps d'arrêt, propriété de Markov forte
  2. Classification des états : états transitoires, récurrents nuls et récurrents positifs, critère de la matrice du potentiel
  3. Existence et unicité à un facteur multiplicatif près de la mesure invariante pour les chaînes irréductibles et récurrentes
  4. Existence et unicité de la distribution stationnaire pour les chaînes irréductibles et récurrentes positives

Cours du 11 décembre : théorème ergodique et simulation

  1. Théorème ergodique, théorème de Kolmogorov
  2. Génération de variables aléatoires discrètes, méthode de l'alias

Cours du 18 décembre : simulation de chaînes de Markov

  1. Echantillonneur de Gibbs et simulation MCMC
  2. Temps de mélange, couplage de chaînes de Markov

Cours du 8 janvier : simulation parfaite des chaînes de Markov

  1. Algorithme de Propp et Wilson
  2. Chaînes monotones, modèle d'Ising

Cours du 15 janvier : critères de Foster

  1. Condition suffisante pour la récurrence positive
  2. Condition siffisante pour la non-récurrence positive
  3. Le protocole Aloha

Références

  1. Markov chains: Gibbs fields, Monte Carlo simulation and queues, P. Brémaud, Springer, New York, 2nd printing, 2001.
  2. Probability and Computing. Randomized Algorithms and Probabilistic Analysis. M. Mitzenmacher and E. Upfal.
  3. The Probabilistic Method. N. Alon and J.H. Spencer.
  4. Finite Markov Chains and Algorithmic Applications. Olle Häggström.

Examens des années précédentes

Pages des années précédentes