Différences

Ci-dessous, les différences entre deux révisions de la page.

--- if-oc [2020/10/16 13:21] – créée vpenelle
+++ if-oc [2020/10/16 14:34] (Version actuelle) – obaudon
@@ Ligne 1: / Ligne 1: @@
-TODO
+====Optimisation Combinatoire====
+Responsables : [[https://dept-info.labri.fr/~baudon/| Olivier Baudon]]
+Ce cours du S8 vaut 6ECTS.
+===Résumé===
+Partie 1 (Olivier Baudon) : [[https://dept-info.labri.fr/~baudon/Master/OptiComb/OptiComb.html| Coloration de graphes]]
+Cette partie concerne les problèmes de la coloration de graphes, c'est à dire :
+- comment colorier les sommets d'un graphe de façon à ce que deux sommets voisins aient toujours des couleurs différentes ;
+- comment colorier les arêtes d'un graphe de façon que deux arêtes partageant un sommet aient toujours des couleurs différentes.
+Après avoir montré les bornes classiques sur le nombre de couleurs nécessaires, nous nous intéressons plus particulièrement à la classes des graphes parfaits, ce qui nous permet d'aborder des classes de graphes classiques, très souvent utilisées comme exemples pour différents paramètres : graphes d'intervalles, graphes de comparabilité, graphes scindés ...
+Partie 2 (à compléter) : Programmation Linéaire
+Cette partie du cours est consacrée à la programmation linéaire et à son utilisation pour résoudre des problèmes de graphes. Nous présentons l'algorithme du simplexe, la notion de dualité, ..., avant de passer à la question de l'utilisation des programmes linéaires pour les graphes, pour lesquels les solutions demandées sont forcément entières.

Master Informatique - Université de Bordeaux

Outils pour utilisateurs

Outils du site

Différences

Outils de la page