LiveZilla Live Chat Software

Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Algorithmes pour le problème de l'arbre couvrant minimal

La Chance Edmond. (2014). Algorithmes pour le problème de l'arbre couvrant minimal. Mémoire de maîtrise, Université du Québec à Chicoutimi.

[img] PDF
3MB

Résumé

Le problème de l'arbre couvrant minimal est un des plus vieux problèmes en théorie des graphes. La problématique se pose comme suit : étant donné un graphe avec un nombre de sommets et un nombre d'arêtes ayant des poids de valeurs dans l'ensemble des entiers relatifs, l'arbre couvrant minimal consiste à trouver l'ensemble des arêtes permettant de rejoindre tous les sommets sans former de cycle, et ce, avec un coût minimal. Ce problème trouve des applications pratiques variées : il est directement applicable pour l'optimisation et la conception de divers types de réseaux (électrique, internet, etc.). Son application la plus populaire est actuellement dans le domaine du forage de données. La raison étant que certains algorithmes construisent l'arbre minimal en faisant grossir des groupes d'éléments progressivement. Ces groupes, appelés également clusters, représentent ensuite des groupes d'éléments similaires, ce qui permet de faire du forage de donnée efficacement. Il suffit au préalable de transformer les données multidimensionnelles du problème de clustering en graphe. Pour trouver l'arbre couvrant minimal, de nombreux algorithmes ont été proposés dans la littérature et ils sont pour la plupart assez performants. Cependant, avec l'invention récente de meilleures structures de données et de nouvelles techniques, les algorithmes n'ont cessé d'évoluer dans les vingt dernières années. Se pose donc la question : quel est l'algorithme le plus performant d'un point de vue théorique et/ou pratique? Les algorithmes testés dans ce mémoire ont des complexités temporelles assez semblables ; il est donc difficile de prévoir a priori celui qui sera le plus performant. Nous avons pour cela choisi une série d'algorithmes résolvant ce problème, nous avons expliqué en détail leur fonctionnement et nous les avons programmés en utilisant plusieurs structures de données. Ces algorithmes sont ceux de Kruskal, Borûvka et Prim. L'algorithme de Prim a été implémenté avec de nombreuses files de priorité et les algorithmes de Kruskal et Borûvka utilisent les meilleurs algorithmes de gestion des ensembles disjoints. Nous avons ensuite fait des tests empiriques sur des graphes de différentes tailles et densités afin de pouvoir confirmer les avantages de leur complexité temporelle. Les résultats obtenus permettent de tirer de nombreuses conclusions sur les performances de chaque algorithme en fonction de la densité du graphe. L'algorithme de Borûvka sort notamment du lot, car il propose des performances excellentes pour toutes les densités de graphe.

Type de document:Thèse ou mémoire de l'UQAC (Mémoire de maîtrise)
Date:2014
Lieu de publication:Chicoutimi
Programme d'étude:Maîtrise en informatique
Nombre de pages:105
ISBN:Non spécifié
Sujets:Sciences naturelles et génie > Sciences mathématiques > Informatique
Département, module, service et unité de recherche:Départements et modules > Département d'informatique et de mathématique > Programmes d'études de cycles supérieurs en informatique
Directeur(s), Co-directeur(s) et responsable(s):Rebaïne, Djamal
Mots-clés:arbre couvrant minimal, théorie des graphies, algorithmes
Déposé le:07 juill. 2015 11:13
Dernière modification:26 févr. 2016 14:23
Afficher les statistiques de telechargements

Éditer le document (administrateurs uniquement)

Creative Commons LicenseSauf indication contraire, les documents archivés dans Constellation sont rendus disponibles selon les termes de la licence Creative Commons "Paternité, pas d'utilisation commerciale, pas de modification" 2.5 Canada.

Bibliothèque Paul-Émile-Boulet, UQAC
555, boulevard de l'Université
Chicoutimi (Québec)  CANADA G7H 2B1
418 545-5011, poste 5630