Curriculum LDD Informatique-Mathématiques

Cours : Algorithmique (S1)

Objectifs : Le but de ce cours est d’acquérir une maîtrise des concepts de base et de certains concepts avancés de l’algorithmique et des structures de données, ainsi que de maîtriser le calcul de leur complexité et les preuves de correction. Les concepts abordés concernent les paradigmes algorithmiques, les algorithmes sur les structures de données linéaires, arborescentes et sur les graphes.

Plan détaillé :

  1. Correction (terminaison, correction partielle)
  2. Complexité (équations de récurrence, complexité amortie, complexité en moyenne, bornes inférieures de complexité)
  3. Paradigmes (diviser pour régner, programmation dynamique, algorithmes gloutons)
  4. Structures de données (dictionnaires, files de priorité, ensembles disjoints)
  5. Ouverture (géométrie dans le plan)
  6. Tris (tris par comparaison, borne inférieure de complexité, tris sans comparaison, applications)
  7. Compléments sur les tableaux (recherche de k-ième valeur, valeur majoritaire, fusion sur place)
  8. Graphes, chemins, arbres non orientés, cycles, accessibilité
  9. Graphes orientés, parcours, parcours en profondeur, détection de circuits
  10. Tri topologique, composantes fortement connexes, les algorithmes de Sanders-Mehlhorn-Dietzfelbinger-Dementiev, de Tarjan
  11. Algorithme de Roy-Warshall, semi-anneaux, algèbres de Kleene, algorithme de Roy-Warshall généralisé, de McNaughton-Yamada, de Floyd (distances max, distances min)
  12. Algorithmes de plus courts chemins à point de départ fixé: Bellman-Ford, Ford[-Gallo-Pallattino], Dijkstra, cas sans circuit
  13. Flots maximaux, coupes minimales: Ford-Fulkerson, Edmonds-Karp/Dinic
  14. Autres algorithmes de flots maximaux: à échelonnement, à préflots (Karzanov, Goldberg-Tarjan); applications: chemins disjoints, couplages, théorème de Menger

Références :

  • Livre Introduction to Algorithms par Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest, ISBN: 9780262530910, URL: edu/9780262530910/introduction-to-algorithms/
  • les notes de cours pour la seconde partie du cours, lien Graph algorithms