Théorie des graphes et Recherche opérationnelle

Informations

Responsable	Géraldine Del Mondo
Enseignant(s)	Géraldine Del Mondo
Langue	Français ou anglais
Crédits	2.5
Volume horaire	CM : 10.5h TD : 10.5h
Site web	http://moodle.insa-rouen.fr/course/view.php?id=124

Objectifs

L'objectif principal est d'acquérir des connaissances de base en théorie des graphes et recherche opérationnelle. Ce cours s'attache à mettre en perspective des problèmes classiques de recherche opérationnelle et des problématiques orientées recherche, notamment par la présentation de projets de recherche en cours sur la thématique des graphes.

A l'issue de cet EC, le but est d'être capable de :

Savoir passer d'un problème réel à un problème modélisé par la théorie des graphes
Savoir utiliser les propriétés liées aux graphes pour résoudre un problème
Savoir évaluer la complexité d'un problème

Capacités enseignées

Référentiel INSA :
- Optimiser un modèle [3P]
- Déterminer des classes de problèmes [2P]
Référentiel CNISF :
- J10C [2I]
- J10G [2I]
- J10Q [1P]

1 - notion, 2 - théorisation, 3 - application, I - intégralement, P - partiellement

Programme

Graphes, Propriétés des graphes, la modélisation par un graphe
Coloration de graphes
Flots et couplages
Parcours de chemins
Graphes spatialisés
Représentation informatique
Base de la théorie de la complexité

Pré-requis

Algorithmique

Bibliographie

Algorithmes de graphes, P. Lacomme, C. Prins, M. Sevaux, Eyrolles, 2003.
Introduction to graph theory, D. B. West, Pearson, 2001
Faure R., Précis de Recherche Opérationnelle, Dunod Décision

Méthode d'évaluation

Examen final : 80%, Projet et/ou autre contrôle continu : 20%