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)
Moritz MUHLENTHALER, Zoltan SZIGETI
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
CONTRÔLE CONTINU :
Type d'évaluation (ex : TP, assiduité, participation) : -
SESSION NORMALE :
Type d'examen (écrit, oral, examen sur machine) : écrit
Salle spécifique :
Durée : 2 heures
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) : notes de cours
Documents interdits (ex : livres, tous documents) : livres
Matériel (ex : calculatrices):
- matériel autorisé, préciser :
- matériel interdit, préciser : calculatrices
Commentaires :
SESSION DE RATTRAPAGE :
Type d'examen (écrit, oral, examen sur machine) : oral
Salle spécifique :
Durée : 1/2 heure
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) :
Documents interdits (ex : livres, tous documents) : livres
Matériel (ex : calculatrices):
- matériel autorisé, préciser :
- matériel interdit, préciser : calculatrices
Commentaires
- MCC en présentiel et distantiel
N1=(E1+E2)/2
N2=E3
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 :
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