Méthodes et algorithmes probabilistes

Les étudiants inscrits sont invités à consulter également la page du cours sur Moodle.

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 !).

Sujets de TD/TP

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 : 19 mars 2020