Programmation Dynamique Dans Les Mod les de Calcul Parall le Bsp/Cgm

Nous assistons cette dcennie une tendance (migration) du hardware parallle vers les systme multiprocesseurs gros-grain. Cependant, la majorit du logiciel parallle traditionnel est conue pour des systme grain-fin et pour des machines mmoire partage. L'un des principaux dfis actuels des chercheurs en conception d'algorithmes parallles est de rduire cette incompatibilit dite cart logiciel-matriel. Un grande intrt est ainsi port la conception d'algorithmes parallles efficaces pour les multi-processeurs gros-grain. C'est dans ce cadre que s'inscrit cette thse. Nous utilisons le modle de calcul parallle BSP/CGM(Bulk synchronous parallel Coarse Grained Multicomputers) pour concevoir des solutions pour des problmes faisant appel la technique de programmation dynamique. Nous nous intressons un chantillon typique de la programmation dynamique du type polyadique non-serial. Il s'agit d'une importante classe de problmes largement utiliss dans les applications haute performance (tel que : le problme d'ordonnancement de produit de chane de matrices, le problme de l'arbre binaire de recherche optimale, le problme de triangulation de polygones convexe).