Recherche Opérationnelle

Données Générales
Programme Académique	Formation ECAM Arts & Métiers			:
Type d'EC	Cours
Cours : 12h00 TD : 4h00 Durée totale : 24h00	Statut : Obligatoire	Période : SEMESTRE ACADEMIQUE	Langue d'enseignement : Français

Acquis d'apprentissage
Ce cours aborde la recherche opérationnelle dans le cadre de la théorie des graphes et de l'étude des algorithmes associés aux problèmes d'optimisation. En abordant les exemples les plus connus, il permet d'appréhender les compétences de modélisation et de résolution. Comprendre les principaux enjeux de la recherche opérationnelle et appliquer aux thématiques de la théorie des graphes. Cinq compétences sont abordées : - Définitions et concepts mathématiques - Modéliser un problème - Appliquer des algorithmes connus - Adapter un algorithme connu - Interpréter un résultat

Acquis d'apprentissage

Ce cours aborde la recherche opérationnelle dans le cadre de la théorie des graphes et de l'étude des algorithmes associés aux problèmes d'optimisation. En abordant les exemples les plus connus, il permet d'appréhender les compétences de modélisation et de résolution.

Comprendre les principaux enjeux de la recherche opérationnelle et appliquer aux thématiques de la théorie des graphes.
Cinq compétences sont abordées :
- Définitions et concepts mathématiques
- Modéliser un problème
- Appliquer des algorithmes connus
- Adapter un algorithme connu
- Interpréter un résultat

Contenu
Chaque séance de cours alterne une partie théorique et une application. Plan du cours - Graphes : définitions - Connexité - Cheminement sans cout - Cheminement avec couts - Chemins hamitoniens et heuristiques - Problèmes de couverture - Coloration de graphes - Affectation - Flot maximum - Problématiques des grands graphes Les séances de TD permettent de travailler en groupe sur des exercices.

Contenu

Chaque séance de cours alterne une partie théorique et une application.
Plan du cours
- Graphes : définitions
- Connexité
- Cheminement sans cout
- Cheminement avec couts
- Chemins hamitoniens et heuristiques
- Problèmes de couverture
- Coloration de graphes
- Affectation
- Flot maximum
- Problématiques des grands graphes

Les séances de TD permettent de travailler en groupe sur des exercices.

Prérequis / corequis
Notions de base de l'algorithmique : conditions, boucles, tableaux, listes, arbres

Bibliographie
- Roseaux, "Exercices et problèmes résolus de recherche opérationnelle", Tome 1, Dunod, Paris 2002, 296p. - M. Gondran, M. Minoux, "Graphes et Algorithmes", Eyrolles, Paris 1995, 588p. - R. Faure, B. Lemaire, C. Picouleau, "Précis de recherche opérationnelle", Dunod, 2000, 520p.

Évaluation(s)
N°	Nature	Coefficient	Objectifs
1	Devoir écrit portant sur l'ensemble du cours. - Connaitre les définitions et concepts mathématiques liés aux graphes - Modéliser un problème - Appliquer des algorithmes connus - Adapter un algorithme connu - - Interpréter un résultat	1	Devoir écrit