Optimisation dans les graphes

Code UE : RCP210

  • Cours
  • 3 crédits

Responsable national

Christophe PICOULEAU

Responsable opérationnel

Christophe PICOULEAU

Public et conditions d'accès

Connaissances en recherche opérationnelles et Théorie des graphes niveau licence et M1

Objectifs pédagogiques

Les graphes constituent un outil mathématique fondamental de la Recherche Opérationnelle. Ils permettent la modélisation de systèmes extrêmement variés. Ceci explique l'essor de la discipline depuis son apparition. L'objectif de ce cours est double : d'une part approfondir les connaissances de théorie des graphes et d'algorithmique dans les graphes ; d'autre part présenter des problématiques de recherche apparues récemment comme l'algorithmique on-line. De nombreux problèmes d'optimisation combinatoire seront présentés ainsi que leurs applications industrielles : conception de VLSI, pose de câbles dans des centrales EDF, problèmes de décision en temps réel (routage dynamique, prise en compte d'informations partielles pour la planification, gestion en temps réel de requêtes conflictuelles).

Mots-clés

Contenu

- Structures particulières dans les graphes (stables, cliques, couplages,..)
- Coloration et polynômes chromatiques
- Connectivité, graphes hamiltoniens
- Graphes parfaits
- Etude des problèmes dans les graphes bipartis
- Multiflots entiers, multicoupes et chemins disjoints (applications)
- Introduction à l'algorithmique on-line dans les graphes (applications)

Contact

EPN05 - Informatique
2 rue Conté
75003 Paris
Tel :01 40 27 22 58
Swathi Rajaselvam
Voir les sites

Voir les dates et horaires, les lieux d'enseignement et les modes d'inscription sur les sites internet des centres régionaux qui proposent cette formation

Enseignement non programmé cette année