Projet I3 (PR302) 2005/2006

Comparaison d'algorithmes d'arbre de poids minimum

Suiveur : Jean Cousty

Contexte

Parmi les sciences de l'ingénieur, les problèmes d'optimisation sont récurrents et difficiles à résoudre. Il est souvent impossible de garantir l'optimalité de la solution proposée. La recherche d'arbre couvrant de poids minimum (MST) est un problème d'optimisation intéressant car il existe différentes méthodes permettent d'aboutir avec une bonne complexité à une solution exacte.

Les applications de ce problème sont nombreuses : mise en place de réseaux tépléphoniques ou électriques, design de circuit imprimé ou encore analyse d'image. Néanmoins, étant donnée une application, (c'est à dire un type de graphe caractérisé entre autres par sa taille ou/et sa densité), il est souvent difficile de choisir parmi les différents algorithmes celui qui sera effectivement le plus rapide.

Travail à réaliser

Dans ce projet, nous souhaitons comparer, en fonction du type de graphe considéré, les temps d'execution effectifs de différents algorithmes de calcul de MST.

• Tout d'abord, les algorithmes standards pour le calcul d'arbre de poids minimum (Kruskal, Prim entre autres) seront étudiés et mis en oeuvre efficacement.
• Un algorithme original de calcul d'arbre de poids minimum sera proposé à partir de travaux effectués récemment au sein du laboratoire A2SI.
• Enfin, pour réaliser la comparaison des algorithmes, un outil permettant de générer aléatoirement des graphes en fonction des caractéristiques (taille/densité) souhaitées devra être implémenté.

Moyens logiciels et matériels

Les algorithmes seront implémentés en C.

Pré-requis: IN101, IN202, IN302.