(LUẬN văn THẠC sĩ) partitionnement de graphe

➤ Gửi thông báo lỗi ⚠️ Báo cáo tài liệu vi phạm

Loại tài liệu: PDF

Số trang: 43 Trang

Tài liệu: ✅ ĐÃ ĐƯỢC PHÊ DUYỆT

TẢI VỀ

Nội dung chi tiết: (LUẬN văn THẠC sĩ) partitionnement de graphe

(LUẬN văn THẠC sĩ) partitionnement de graphe

IFI__________________Institut de la Francophonie pour rinformatiqueUniversite catholique de LouvainPartitionnement de GraphePromoteur:Yves DevilleMémo

(LUẬN văn THẠC sĩ) partitionnement de graphe oire présenté en vue de I'obtention du grade de master informatiqueparDuong Khanh ChuongHanoiNovembre, 2009RemerciementsJe tiens d'abord á remercier t

out particulièrement mon promoteur, Monsieur Deville, pour I'encadrement, I’aide et les idées qu’il m’a donné pendant toute la durée du stage.Je voudr (LUẬN văn THẠC sĩ) partitionnement de graphe

ais remercier tous les membres de réquĩpe BeCool (Belgian Constraint Group) pour leur accueil chaleureux, leur soutlen et leurs conseils sans lesquels

(LUẬN văn THẠC sĩ) partitionnement de graphe

ce travail n'aurait pu aboutir.J’adresse mes sincères remerciements á tous les professeurs de I’lFI pour m'avoir enseigné et m'inspirer pendant mes e

IFI__________________Institut de la Francophonie pour rinformatiqueUniversite catholique de LouvainPartitionnement de GraphePromoteur:Yves DevilleMémo

(LUẬN văn THẠC sĩ) partitionnement de graphe ésuméLe problems du portitionnement de graphs a pour but de découper un graphe en differentes parties (partitions) qui satisfont certains contraintes

(telle que 1'équilibre des parties) et qui optimisent une certaines fonction objectif (telle que le coùt de coup). II possède de nombreuses applicatio (LUẬN văn THẠC sĩ) partitionnement de graphe

ns comme la conception de circuits intégrés électroniques, la repartition de charge pour les machines paralleled OU la segmentation d'images. Cependan

(LUẬN văn THẠC sĩ) partitionnement de graphe

t, le partitionnement de graphe est un problème complexe (NP-complet), dont la solution ne peut pas être trouvée au moyen d'une methode de resolution

IFI__________________Institut de la Francophonie pour rinformatiqueUniversite catholique de LouvainPartitionnement de GraphePromoteur:Yves DevilleMémo

(LUẬN văn THẠC sĩ) partitionnement de graphe onnement dassiques comme la methode de glouton, le multi-niveaux OU les algorithmes de type Kernighan-Lin et des methodes de recherche locate comme la

recherche taboue et le recuit simulé.Enfin, nous avons implémenté les methodes presentees dans ce memoire dans COMET, et nous avons compare leur perf (LUẬN văn THẠC sĩ) partitionnement de graphe

ormance et leur efficacite avec le logiciel METIS.Mots clés : partition, recherche locale, multi-niveaux, contraction, afftnagePage 3AbstractThe graph

(LUẬN văn THẠC sĩ) partitionnement de graphe

partitioning problem consists of dividing a graph into parts (partition) which satisfy some constraints (such as the balance of parts) to optimize an

IFI__________________Institut de la Francophonie pour rinformatiqueUniversite catholique de LouvainPartitionnement de GraphePromoteur:Yves DevilleMémo

(LUẬN văn THẠC sĩ) partitionnement de graphe chines or image segmentation. However, graph partitioning is known to be NP-complete, so there is no exact solution and the local search is one of app

ropriate approach. In our work, we have studied and analyzed classic partitioning methods such as the greedy, the multi-level or algorithms of Kernigh (LUẬN văn THẠC sĩ) partitionnement de graphe

an-Lin and methods of local search such as Tabu search and simulated annealing.Finally, we have implemented those methods In COMET, and then we compar

(LUẬN văn THẠC sĩ) partitionnement de graphe

ed their performance and efficiency with the software METIS.Key words: partition, local search, multi-level, coarsening.Page 4Table des matières1.Part

IFI__________________Institut de la Francophonie pour rinformatiqueUniversite catholique de LouvainPartitionnement de GraphePromoteur:Yves DevilleMémo

(LUẬN văn THẠC sĩ) partitionnement de graphe .................91.2.Contraint.......................................................................101.3.Fonction d'objectives.....................

......................................111.4. Applications...................................................................112.Etatde I'art.......... (LUẬN văn THẠC sĩ) partitionnement de graphe

..............................................................13

IFI__________________Institut de la Francophonie pour rinformatiqueUniversite catholique de LouvainPartitionnement de GraphePromoteur:Yves DevilleMémo