C. Crespelle

Algorithmique 2

Graphes, arbres et programmation linéaire

Ce cours vise à développer votre pensée algorithmique en l'appliquant à différents types d'objets tels que les graphes, les objets géométriques ainsi que les séquences de lettres et de nombres.

SLUF501 L3 S5 6 ECTS 24h CM + 36h TD
Syllabus C. Crespelle

Description

But : Modéliser de nombreux problèmes RÉELS et étudier les algorithmes permettant de les résoudre avec une grande efficacité.

Cours

  1. La décomposition des graphes (Le Parcours de graphes, Le Tri topologique, Les Composants Fortement Connexes)
  2. Le plus court chemin (Dijkstra, Bellman-Ford, Floyd, Dag,..)
  3. L’arbre couvrant minimal (Prim, Kruscal)
  4. le problème du flot maximal…
  5. La Programmation Linéaire
  6. Etudes de Cas : Exploration du WEB, Ordonnancement des taches (PERT CPM), Réseaux ferroviaires et distributions…

Modalités de contrôle des connaissances

  • 2 CC à 30%
  • 1 CT à 40%

Ressources

  1. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithms /2008.
  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009
  3. Tim Roughgarden Algorithms Illuminated Part 1 The Basics pdf en ligne