Volumes horaires
- CM 18.0
- Projet -
- TD 18.0
- Stage -
- TP -
- DS -
Crédits ECTS
Crédits ECTS 3.0
Objectif(s)
Apprendre comment modéliser certains problèmes susceptibles d'être résolus par des méthodes d’Optimisation Combinatoire et de proposer une introduction aux concepts de base de la Recherche Opérationnelle.
Responsable(s)
Zoltan SZIGETI, Moritz MUHLENTHALER
Contenu(s)
1. Graphe - un remarquable outil de modélisation : de nombreux exercices illustrent les notions de base: connexité, stabilité, coloration, couplages, arbres et arborescences, structurations des données.
2. La programmation linéaire : concepts fondamentaux, l'aspect algorithmique (la méthode du simplexe) et l'aspect théorique.
3. Les aspects algébriques et algorithmiques des graphes (co-)cycles, (co-)arbres.
4. Quelques algorithmes sélectionnés comme :
- arbres de recouvrement de poids optimal ;
- chemins optimaux et leurs applications dans des ordonnancements de projets.
5. La notion de complexité des problèmes est introduite. On explique les motivations de l'introduction des algorithmes heuristiques et approximatifs.
- Ce cours est donné en Période(s) Académique(s) 1 et 2 **
Aucun, mais a priori, élève doit pouvoir suivre le raisonnement formel avec un certain niveau d’abstraction (=bon niveau en maths).
Contrôle des connaissances
Evaluation : Examen Ecrit (2h)
Rattrapage : Examen oral (exposé, soutenance, etc..) (30 min)
Session 1 :
- Période 1
- E1 = examen écrit 2h, notes de cours autorisées uniquement - Période 2
- E2 = examen écrit 2h, notes de cours autorisées uniquement - N1 = (E1 + E2)/2
Session 2 :
- ET2 = oral 30 min, aucun support autorisé
- N2 = ET2
Calendrier
Le cours est programmé dans ces filières :
- Cursus ingénieur - Alternance - Alternance 1ere annee
Informations complémentaires
Code de l'enseignement : 3MM1RO
Langue(s) d'enseignement : 
Le cours est rattaché aux structures d'enseignement suivantes :
- Equipe Algorithmique-Mathématiques discrètes
Vous pouvez retrouver ce cours dans la liste de tous les cours.
Bibliographie
W. BIENIA : "Introduction à la recherche opérationnelle et optimisation combinatoire", polycopié 2009
V. CHVATAL : "Linear programming", W.H. Freeman Company, 1983
G. FINKE at al “Recherche Opérationnelle et réseaux” traité IGAT, HERMES, 2002