Changes between Version 34 and Version 35 of CaoCourseTme8

Timestamp:

May 20, 2009, 1:21:22 PM (16 years ago)

Author:

alain

Comment:

--

CaoCourseTme8

@@ -283 +283 @@
        ''graph_t'' et ''move_manager_t''. Vous disposez pour vous aidez d'une fonction ''dump_move_manager()''
        qui affiche le contenu de la structure.
-
- '''2. Ecriture de l'algorithme !MinCut glouton'''::
+       
+ '''2. Exécution et évaluation'''::
        Complétez le programme main() en ajoutant la fonction ''mincut(graph_t *gr, move_manager_t *mm)''.
-       Cette fonction contient la boucle réalisant les transferts de cellules tant que la fonction de coût 
-       n'augmente pas. On utilisera la fonction ''global_cost()'' pour calculer et afficher le coût de
-       la partition avant et après optimisation.
-
- '''3. Exécution et évaluation'''::
-       Exécutez cet algorithme sur différents graphes que vous définirez
-       vous-mêmes. La partition résultante est-elle toujours la partition
-       optimale? Pourquoi? Donnez un contre-exemple.
-
- '''4. Ecriture des fonctions d'accès''':: 
+       On utilisera la fonction ''global_cost(graph_t *g)'' pour calculer et afficher le coût de la partition avant et après optimisation.
+       Exécutez cet algorithme sur différents graphes que vous définirez vous-mêmes. 
+       La partition résultante est-elle toujours la partition optimale? Pourquoi? Donnez un contre-exemple.
+
+'''3. Ecriture de la fonction mincut() '''::
+       Ecrire en langage C la fonction mincut() qui réalise l'algorithme !MinCut glouton. 
+       Cette fonction contient la boucle réalisant les transferts de cellules tant que le transfert fait décroitre
+       la fonction de coût. A chaque tour dans cette boucle, une cellule du sous-ensemble L passe dans R,
+       et une cellule du sous-ensemble R passe dans L. Les deux cellules i et j qui on bougé doivent être retirées
+       de la structure de donnée move_manager'', et les gains de toutes les cellules adjacentes à i et j doivent
+       être mis à jour.
+
+'''4. Ecriture des autres fonctions d'accès''':: 
        Ecrire les différentes fonctions d'accès aux structures de données définies
        dans la partie D, et validez ces fonctions en les intégrant peu à peu dans