Algorithmique

L3 Informatique parcours Math-Info, U. Grenoble Alpes

Cours

Le plan indiqué est prévisionnel et susceptible de modifications.

Partie 1. Structures de données

1. Types abstraits de données & rappels : tableaux, listes, arbres binaires
2. Structures de données linéaires : piles, files, files à priorité
3. Tableaux dynamique et arbres binaires de recherche
4. Tables de hachage

Partie 2. Techniques algorithmiques

5. Diviser pour régner : principes, exemples du tri fusion et de l’algorithme de Karatsuba
6. Recherche exhaustive : principes, exemples de Sat et du voyageur de commerce
7. Algorithmes probabilistes : Monte Carlo et Las Vegas, exemples de la coupe minimale et du tri rapide
8. Programmation dynamique : principes, exemples de la plus longue sous-suite croissante et de la distance d’édition
9. Algorithmes d’approximation : principes, exemples de couverture par sommets, somme partielle, et équilibrage de charges
10. Deux techniques avancées : recherche exhaustive rapide (3-Sat), diviser-pour-régner en programmation dynamique (distance d’édition)

Quelques lectures intéressantes

• Diviser pour régner : article sur la multiplication d’entiers en temps O(n log n)
• Recherche exhaustive :
  • article sur les algorithmes d’énumération
  • articles sur le problème des huit reines et au delà

Sujets de TD

• 2023-2024 +-
  • TD1 : Types abstraits de données
  • TD2 : Structures de données linéaires
  • TD3 : Tableaux dynamiques et Arbres binaires de recherche
  • TD4 : Tables de hachage
  • TD5 : Diviser pour régner
  • TD6 : Recherche exhaustive
  • TD7 : Algorithmes probabilistes
  • TD8 : Programmation dynamique
  • TD9 : Algorithmes d'approximation
  • TD19 : Recherche exhaustive rapide

Examens

• Contrôle continu
• Devoir à la maison : à rendre le 20 décembre 2023

Bibliographie indicative

• 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 BU.

• R. Sedgewick, K.Wayne. Algorithms. Addison-Wesley, 4th ed., 2011.
  La nouvelle bible de l’algorithmique. Une approche beaucoup plus orientée pratique que le précédent.
  Des versions précédentes, traduites en français, sont disponibles à la BU.

• D. Beauquier, J. Berstel, Ph. Chrétienne. Éléments d’algorithmique. Masson, 1992.
  Un excellent ouvrage d’algorithmique en français.
  Disponible à la BU, et gratuitement sur la page de J. Berstel.

Les deux ouvrages suivants sont mes ouvrages préférés d’algorithmique. Malheureusement, ils ne couvrent pas la partie 1. Structures de données. Ne pas hésiter à les consulter pour la partie 2. Techniques algorithmiques.

• J. Erickson. Algorithms. Self-published, 2019.
  Mon ouvrage préféré d’algorithmique. Consulter également ses autres notes de cours, sur la même page, qui sont toutes excellentes. Disponible gratuitement en ligne.

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

Dernière modification : 27 novembre 2023