L3 Informatique, Probabilités, printemps 2019

Enseignants

  • Responsable du cours : Guillaume AUBRUN.
  • Responsables du TD : Alice PELLET--MARY et Tien-Nam LE

    Références

    Avancement du cours

  • 1. Cours du 31 janvier. Warm-up : deux exemples d'algorithmes probabilistes 1) vérifier la multiplication de matrices et 2) trouver la coupe minimale dans un graphe (on reviendra sur ce dernier). Chapitre 1 (formalisme) : espaces de probabilités, tribus, événements. Propriétés élémentaires. Définition de l'indépendance d'événements. Théorème admis : il existe une infinité de bits aléatoires, lien avec la mesure de Lebesgue. Exemple de partie non mesurable. Définition d'une variable aléatoire.

  • 2. Cours du 7 février. Exemples des v.a. discrètes et des v.a. admettant une densité, espérance d'une variable aléatoire, indépendance (linéarité, espérance d'un produit de va indépendantes). Lemme des groupement par paquets. Théorème d'existence d'une suite de va indépendantes de loi prescrite. Exemples : calcul de la complexité moyenne de randomized Quicksort ; retour sur l'algorithme probabiliste pour trouver la coupe minimale.

  • 3. Cours du 14 février. Loi géométrique, absence de mémoire. Problème du collectionneur de vignettes. Chapitre 2 (déviations) : inégalité de Markov. Moments, norme L^p, variance, covariance. Inégalité de Tchebychev, convergence en probabilité, loi faible des grands nombres.

  • 4. Cours du 28 février. Fonction génératrice des moments. Inégalité de Chernoff (version Bernoulli(1/2), version Bernoulli générale). Loi de Poisson, loi gaussienne introduites comme lois limites.

  • 5. Cours du 7 mars. Application des bornes de Chernoff : estimation de paramètres, partage équilibré. Inégalité de Hoeffding. Chapitre 3 (quelques modèles probabilistes). Exemple d'un modèle probabiliste : processus de branchement

  • 6. Cours du 14 mars. Graphe aléatoire d'Erdos-Rényi : valeur critique pour la connexité. Processus de Poisson : définition par les temps de saut exponentiels. Indépendance et loi des accroissements. Paradoxe de l'autobus

  • 7. Cours du 21 mars. Chapitre 4 (Convergence des variables aléatoires) : convergence en probabilité, presque sûrement, en loi(=en distribution). Lemme de Borel-Cantelli, loi forte des grands nombres (preuve sous hypothèse L^4). Théorème de Lévy (admis).

  • 8. Cours du 28 mars. Théorème central limite (preuve comme conséquence du théorème de Lévy). Vecteurs aléatoires gaussiens. Lemme de Johnson-Lindenstrauss : preuve (incluant un lemme de concentration pour la loi du chi-2). Chapitre 5 (La méthode probabiliste). Exemple 1 : bornes inférieures pour les nombres de Ramsey. Exemple 2 : satisfiabilité de formules k-SAT

  • 9. Cours du 5 avril. Exemple 3 : borne inférieure pour le problème de partage équilibré. Exemple 4 : lemme local de Lovasz (énoncé + preuve), application aux formules k-SAT, k>>1. Algorithmes probabilistes : exemple de l'algorithme de factorisation de Miller-Rabin

  • 10. Cours du 12 avril. Chapitre 6 (Chaînes de Markov). Définition d'une chaîne de Markov, représentation graphique. Exemple : algorithme probabiliste pour tester si une formule 2-SAT peut être satisfiable. Classification des états : notions de chaîne irréductible, d'état transient vs récurrent, récurrent positif vs récurrent nul.

    Feuilles de TD

    Vous les trouverez, ainsi que des corrigés, sur la page web de Alice PELLET--MARY

    Devoir maison

    Voici le sujet et le corrigé du devoir maison.

    Annales

    La page de l'an dernier avec sujets d'examen et corrections.