Optimisation dans un graphe
4 crédits Safia KEDAD SIDHOUM EPN05 - Informatique Unité spécifique de type cours
Publié Du 01-09-2011 au 31-08-2024
Connaître les grands problèmes de graphes, leur résolution et leurs domaines d'applications. Savoir utiliser un logiciel de traitement de graphes.
L'unité US331A apparaît dans 1 cursus.
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 d'approfondir les connaissances de théorie des graphes et d'algorithmique dans les graphes. Les grands problèmes classiques de graphes seront présentés ainsi que les méthodes permettant de les résoudre de façon exacte ou approchée : multi-chemins, flots, simples ou multiples, continus ou entiers, coupes et multi-coupes, partitionnement, .... 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 électriques, placement de capteurs, optimisation de compilateur,... Une partie du cours sera réservée à un projet et à l'apprentissage d'un logiciel de type Rudy.