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

Des devoirs maison seront donnés régulièrement et compteront pour 50% de la note finale.

Plan du cours

Cours du 27 septembre : La méthode probabiliste

  1. Introduction : égalité de deux polynômes, file d'attente
  2. Argument de comptage : numbre ded Ramsey
  3. Méthode du premier moment : MAXSAT et ensemblees indépendants
  4. Methode du second momnent et flots de données

Cours du 4 octobre : méthode du second moment

  1. Schéma de Flajolet-Martin
  2. Graphes Erdös-Rényi, fonction-seuil pour les cliques de taille 4

Cours du 11 octobre : le lemme local de Lovàsz

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

Cours du 18 octobre : 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 25 octobre : 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 8 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 15 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 22 novembre : Classification des états , existence et unicité de la mesure invariante

  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

Cours du 29 novembre : théorème ergodique et simulation

  1. Existence et unicité de la distribution stationnaire pour les chaînes irréductibles et récurrentes positives
  2. Théorème ergodique, théorème de Kolmogorov
  3. Génération de variables aléatoires discrètes, méthode de Monte-carlo pour approximation de pi

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

  1. Génération aléatoire, méthode de l'alias
  2. Echantillonneur de Gibbs et simulation MCMC
  3. Temps de mélange, couplage de chaînes de Markov

Cours du 13 décembre : simulation parfaite des chaînes de Markov

  1. Algorithme de Propp et Wilson
  2. Chaînes monotones, technique des enveloppes (application aux ensembles indépendants)

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