Algorithmique

L3 Informatique, Université de Montpellier, 2021-2022

Cours

0. Rappels de probabilités discrètes
1. Aléatoire et algorithmique
2. Recherche exhaustive et backtrack
3. Analyse amortie, analyse d’algorithmes probabilistes
4. Tables de hachage
5. Algorithmes d’approximation

Sujets de TD

• 2021-2022 +-
  • TD1 : Rappels d'analyse d'algorithmes, probabilités
  • TD2 : Recherche exhaustive et backtrack
  • TD3 : Analyses amortie et probabiliste
  • TD4 : Tables de hachage
  • TD5 : Algorithmes d’approximation

Sujets de TP

• 2021-2022 +-
  • TP1 – Aléatoire en Python : bibliothèque random, élément majoritaire, générateurs pseudo-aléatoires
  • TP2 – Recherche exhaustive et retour sur trace : SAT, Sudoku, cryptarithme, problème des huit reines [cnf.tar.gz, sudokus.tar.gz]
  • TP3 – Voyageur de commerce dans le plan : 2-approximation et algorithme de Christofidès [dessins.py]

Bibliographie

1. J. Erickson. Algorithms. Self-published, 2019.
   Mon ouvrage préféré d’algorithmique. Consulter ces autres notes de cours, passionnantes également ! Quelques unes de mes illustrations sont issues ou inspirées de cet ouvrage.
   Disponible gratuitement en ligne.

2. S. Dasgupta, C.H. Papadimitriou, U. Vazirani. Algorithms. McGraw-Hill Higher Education, 2006.
   Mon autre ouvrage préféré d’algorithmique ! Concis et efficace.
   Disponible à la BIU

3. T. H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. MIT Press, 3rd ed., 2009.
   La bible de l’algorithmique, disponible en traduction française. Même si je n’adore pas le style de cet ouvrage, il faut bien reconnaître qu’il y a toute l’algorithmique classique dedans, et bien plus !
   Disponible à la BIU, en français ou en anglais.

Dernière modification : 24 janvier 2023