A. Malapert
Recherche Opérationnelle
MIASHS 3 ECTS 30h L3 OPT A. Malapert
Nous allons étudier des notions, problèmes, et algorithmes fondamentaux de la théorie des graphes. La programmation dynamique, une méthode algorithmique pour résoudre des problèmes d’optimisation, sera introduite grâce aux graphes, avant d’être appliquée à d’autres problèmes classiques.
Calendrier
Contenu
Les diapositives du cours de théorie des graphes sont disponibles : 1 diapositive par page ; 4 diapositives par page ; 8 diapositives par page.
Les diapositives du cours de programmation dynamique sont disponibles : suite de Fibonacci ; problème du sac-à-dos ; Merch Time !.
Le plan des cours est le suivant :
- Généralités et définitions sur les graphes.
- Graphes eulériens et hamiltoniens.
- Connexité, arbres, et cheminement.
- Recherche de connexité et applications
- Problèmes de plus courts chemins
- Contrôle continu
- Généralités et définitions sur la programmation dynamique.
- Applications algorithmiques de la programmation dynamique.
Ressources
BU
- Graphes et algorithmes, Michel Gondran et Michel Minoux.
- Précis de recherche opérationnelle, Robert Faure, Bernard Lemaire et Christophe Picouleau.
- Algorithmes de graphes, Philippe Lacomme, Christian Prins et Marc Sevaux.
Électroniques
- Cours en ligne, Didier Muller.
- Cours en ligne, Christophe Rapine.
- Cahier d’exercices, Eric Sopena.
- http://graphes.fr/
- Cours en ligne (en)
Modalités de contrôle des connaissances
Le contrôle des connaissances comprendra 2 épreuves écrites :
- Contrôle Continu (2h)
- Contrôle Terminal (3h)
La seconde session est aussi une épreuve écrite (2h).