Abstract FR:

L'objet de cette these est d'etudier l'impact des methodes de quotientement sur plusieurs problemes issus du parallelisme et modelises sous forme de graphes. La premiere partie de la these, essentiellement theorique, est consacree a l'etude de deux parametres des graphes, qui sont la largeur de bande et la largeur de coupe. On obtient de nouveaux encadrements de ceux-ci pour plusieurs reseaux d'interconnexion, pour certains au moyen de techniques d'evaluation asymptotique. La deuxieme partie traite du probleme du placement statique sur machine parallele. Nous y presentons un algorithme de placement base sur le bipartitionnement recursif conjoint du graphe de communication des processus et du graphe modelisant l'architecture de la machine parallele, qui permet de placer efficacement tout graphe de processus value sur tout type d'architecture