C. Crespelle

Algorithmique 2

Graphes, texte et objets géométriques

Courte description

L3-INFO 6 ECTS 24h CM + 36h TD S6 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