MSE3112A : Optimisation dans les graphes (3 ECTS)

Code apogée

MSE3112A

Semestre calendaire

S1

Nombre d'ECTS

3

Intitulé du cours

Optimisation combinatoire - Optimisation dans les graphes

Mots clés

Problèmes combinatoire dans les graphes, complexité, algorithmes combinatoires, et introduction à la programmation entière.

Université

Victor Segalen Bordeaux 2

Composante

UFR Sciences et Modélisation

Département

Mention

Ingénierie Mathématique, Statistique et Economique

Specialité

Ingénierie de la gestion quantitative des opérations et aide à la décision

Mutualisation

ce module est aussi offert en spécialité 4 du même master et aux étudiants du master d'informatique.

Objectifs pédagogique

Donner les outils standard de modélisation (outils de la programmation mathématique et de la théorie des graphes) et de résolution algorithmique de l'optimisation discrète : méthodes exactes et approchées.

Prérequis

licence scientifique

Programme détaillé

• Modélisation dans les graphes : définition d'un graphe (quelconque, bipartis) représentation et choix de structure de donnée, parcours de graphes, connexité, chemin, cycle, arbre et forêt, graphe complémentaire.
• Problèmes combinatoires dans les graphes (coloration, plus court chemin, arbre de recouvrement, affectation, couplage) et algorithmes de résolution.

Summary

Références bibliographiques

1. Berge, Claude. Graphes. 3ème édition. - Gauthier-Villars, 1983.
2. Cook, W.J., W.H. Cunningham, W.R. PulleyBlank and A. Schrijver, Combinatorial Optimization, Willey, 1998.
3. Papadimitriou, Combinatorial Optimization.
4. Wolsey, L. A., Integer Programming, John Wiley, 1998 (ISBN 0-471-28366-5).

Contact

A. Raspaud

Equipe pédagogique

P. Pesneau, A. Raspaud, F. Vanderbeck

Volume horaire

10 heures de cours, 14 heures TD

Modalités de contrôle des connaissances

Ecrit terminal 1h30 (=2/3 de la note), Contôle continu (Projet, ...) (=1/3 de la note).