Skip to topic | Skip to bottom
Home
Minfo04
Minfo04.OptimisationCombinatoirer1.16 - 30 Mar 2005 - 16:18 - HavetFrederictopic end

Start of topic | Skip to actions

Optimisation Combinatoire

L'objectif de ce cours est de présenter les algorithmes standard en optimisation combinatoire.

Plan du cours:

(Les versions postcript du support de cours ne sont pas finalisées : de nombreuses typos et erreurs sont susceptibles de s'y trouver.)

  • Rappels rappels.ps
    • Parcours dans les graphes
    • Connexité
    • Graphes bipartis et eulériens

  • Algorithmique classique dans les graphes algo.ps
    • Calcul de plus courts chemins : algorithmes de Dijkstra et de Bellmann-Ford
    • Arbre couvrant de poids minimum : algorithmes de Prim et de Kruskal

  • Couplages dans les graphes couplage.ps
    • Couplage dans les graphes bipartis : méthode hongroise
    • Couplage et couverture
    • Couplages dans les graphes généraux

  • Problèmes de flots flot.ps
    • Flot max = coupe min
    • Algorithmes de flots par poussée : algorithme initial de Ford et Fulkerson, algorithme de poussée par les plus courts chemins de Edmonds et Karp, algorithme utilisant un facteur d'échelle.
    • Flot dans les graphes non-orientés
    • Applications : Arête-connexité, couplage dans les graphes bipartis, clôture de bénéfice maximal.

  • Coloration de graphes coloration.ps
    • Introduction et premières relations. Théoreme de Brooks
    • Coloration des graphes planaires
    • Coloration des arètes

  • Programmation linéaire proglin.ps
    • Introduction
    • Méthode du simplexe

Plusieurs livres reprenant une partie des chapitres de ce cours sont disponibles en ligne. Graph Theory with Applications par J.A. Bondy et U.S.R. Murty et Graph Theory par R. Diestel.

Informations pratiques

Le cours du 22 Mars 2005 a été annulé. Il est reporté au Lundi 18 avril 2005 à 13h30 en salle M308.

L'examen aura lieu le Mardi 26 Avril 2005 à 15h15 en salle habituelle (MA).

-- HavetFrederic - 14 Jan 2004


to top

I downAttachment sort Action Size Date Who Comment
rappels.ps manage 451.9 K 12 Feb 2004 - 11:16 HavetFrederic Les rappels
algo.ps manage 327.5 K 12 Feb 2004 - 11:16 HavetFrederic L'algo classique
couplage.ps manage 352.8 K 27 Feb 2004 - 10:34 HavetFrederic Les couplages
flot.ps manage 571.7 K 08 Mar 2004 - 11:05 HavetFrederic Les flots
coloration.ps manage 284.0 K 04 Mar 2004 - 18:17 MorinAlloryKatell La coloration
corexam04.ps manage 169.0 K 29 Apr 2004 - 13:45 HavetFrederic Correction de l'examen 2004
exam04.ps manage 130.9 K 29 Apr 2004 - 13:49 HavetFrederic L'examen 2004
proglin.ps manage 453.1 K 30 Mar 2005 - 16:19 HavetFrederic Programmation lineaire

Minfo.OptimisationCombinatoire moved from Minfo03.OptimisationCombinatoire on 20 Oct 2004 - 14:37 by OlivierDalle
You are here: Minfo04 > OptimisationCombinatoire

to top

Copyright © 1999-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding WIKIDeptinfo? Send feedback