Changes between Version 7 and Version 8 of CaoCourseTme8
- Timestamp:
- Apr 4, 2007, 7:59:02 PM (18 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
CaoCourseTme8
v7 v8 10 10 la méthode Min-Cut, dont le principe a été présenté en cours. 11 11 12 = A .Introduction =12 = A) Introduction = 13 13 14 14 Soit un graphe G(N, H), où N est l'ensemble des noeuds, et H l'ensemble des … … 40 40 * Aij = 0 sinon 41 41 42 = B) Algorithme !MinCut glouton = 43 42 44 On défini comme suit la fonction de coût du problème d'optimisation !MinCut: 43 44 45 {{{ 45 46 FC = Somme Aij * Kij … … 49 50 Kij = 0 sinon 50 51 }}} 51 52 = B. Algorithme !MinCut glouton =53 52 54 53 On part d'une bi-partition équilibrée initiale arbitraire en deux ensembles … … 86 85 diminution de la fonction de coût. 87 86 88 = C .Structures de données =87 = C) Structures de données = 89 88 90 89 On a besoin de deux structures de données séparées pour représenter d'une part … … 93 92 cellules à effectuer, est appelée «gestionnaire de mouvements». 94 93 95 == C .1.représentation du graphe ==94 == C1) représentation du graphe == 96 95 97 96 Les noeuds du graphe sont identifiés par un index compris entre 0 et (NBNODE-1). … … 116 115 }}} 117 116 118 == C2 .représentation du gestionnaire des mouvements ==117 == C2) représentation du gestionnaire des mouvements == 119 118 120 119 On appelle arité d'un noeud du graphe, le nombre d'arêtes attachées à ce … … 176 175 }}} 177 176 178 = D .Fonctions d'accès aux structures de données =177 = D) Fonctions d'accès aux structures de données = 179 178 180 179 On dispose d'un ensemble de fonctions permettant de construire et de manipuler les deux structures de données graph_t et move_manager_t. … … 253 252 et renvoie la valeur calculée. 254 253 255 = E .Travail à réaliser =254 = E) Travail à réaliser = 256 255 257 256 Nous vous proposons un programme à trous. Vous allez pouvoir remplacer … … 282 281 fichier, puis de les introduire. Si vous n'avez pas le temps de construire 283 282 le graphe, étudiez au moins la grammaire de ce petit langage. 283 284 = Compte-Rendu = 285 286 Il ne vous est pas demandé de compte-rendu écrit, 287 mais vous
