Méthodes et algorithmes probabilistes

M1 Informatique, Université de Montpellier, 2016-2020

Quelques notes de cours

Les notes suivantes contiennent probablement des typos et des erreurs plus graves… À utiliser à vos risques et périls (et n’hésitez pas à me signaler les problèmes !).

• Boîte à outils : définitions et résultats de base en probabilités discrètes (également une version compacte sans preuve, exemple, etc.)

• Introduction : sélection et tri rapides, coupe minimale
• Techniques algébriques (notes manuscrites) : algorithmes de Freivalds, Schwartz-Zippel, recherche de motifs
• WalkSat : algorithme pour résoudre 3-SAT via une marche aléatoire
• Structures de données probabilistes : Tarbres (traduction de treaps), listes à raccourcis (skip lists) et tables de hachage

Sujets de TD/TP

• 2019-2020 +-
  • TD 1 : introduction ou rappel de probabilités
  • TD 2 : amplification de succès
  • TD 3 : QuickSelect et RandMinCut
  • TD 4 : LazySelect et QuickSort
  • TD 5 : méthode de Monte-Carlo
  • TD 6 : fonctions de hachage
  • TD 7 : fonctions de hachage
  • TD 8 : marches aléatoires
  • TD 9 : approximation probabiliste (Max-SAT)
  • TD 10 : tests de primalité
  • TD 11 : textes et motifs
  • TD 12 : algorithmes de flux
• 2018-2019 +-
  • TD 1 : QuickSelect, RandMinCut
  • TD 2 : QuickSort en place, RandMinCut
  • TD 3 : Tarbres et listes à raccourci
  • TD 4 : Fonctions de hachage
  • TD 5 : Marches aléatoires (2-SAT et connectivité dans les graphes)
  • TD 6 : Approximation de Max-Sat
  • TD 7 : Tests de primalité
  • TD 8 : Algorithme de Rabin-Karp
  • TD 9 : Vérification probabiliste (Freivalds, Schwartz-Zippel)
  • TD 10 : Annale (marche aléatoire pour la 3-coloration)
• 2017-2018 +-
  • TD 1 : Coupe minimum et tri rapides, probabilistes
  • TD 2 : Marches aléatoires
  • TD 3 : Filtres de Bloom
  • TD 4 : Approximation de Max-Sat
  • DM : Approximations de Max-Sat
• 2016-2017 +-
  • TP 3 : Quicksort et MinCut
  • TP 4 : Recherche de motif dans un texte. Fichiers à télécharger : TP4.tar.bz2
  • TD 5 : Élements absents, fréquents, rares
  • TD 6 : Isomorphisme d'arbres, tailles des listes à raccourcis, filtres de Bloom

Bibliographie

1. R. Motwani , P. Raghavan. Randomized algorithms. Cambridge University Press, 1995.
   Malgré sa relative ancienneté, reste LA référence sur les algorithmes probabilistes.
2. M. Mitzenmacher, E. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press, 2nd ed., 2017.
   Beaucoup de choses dans cet ouvrage, qui va bien plus loin que le cours.
3. J. Kleinberg, É. Tardos. Algorithm Design. Pearson Education, 2006.
   Le chapitre 13 est une courte et excellente introduction au sujet. [Dispo à la BU Sciences]
4. S. Dasgupta, C.H. Papadimitriou, U. Vazirani. Algorithms. McGraw-Hill Higher Education, 2006.
   Pas de chapitre spécifique aux algos probabilistes, mais mon livre préféré d’algorithmique, avec de nombreux algorithmes probabilistes.
5. C. Moore and S. Mertens. The Nature of Computation. Oxford University Press, 2011.
   Le chapitre 10 « Randomized algorithms » donne un bon survol du sujet, avec un point de vue conceptuel plus que technique.
6. J. Erickson. Director’s Cut. Plusieurs chapitres de notes de cours sur les algorithmes randomisés, en anglais.
   Notes de cours superbement écrites ! Ne pas hésiter à aller parcourir son excellent livre sur l’algorithmique.

Dernière modification : 21 décembre 2022