C. Crespelle
Algorithmique 2
Graphes, texte et objets géométriques
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
- La décomposition des graphes (Le Parcours de graphes, Le Tri topologique, Les Composants Fortement Connexes)
- Le plus court chemin (Dijkstra, Bellman-Ford, Floyd, Dag,..)
- L’arbre couvrant minimal (Prim, Kruscal)
- le problème du flot maximal…
- La Programmation Linéaire
- 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
- Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithms /2008.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009
- Tim Roughgarden Algorithms Illuminated Part 1 The Basics pdf en ligne