Contribution à l'algorithmique parallèle et distribuée : application à l'optimisation combinatoire / Ivan Lavallée ; sous la direction de Guy Vidal Naquet

Thése de doctorat d'état és sciences informatiques informatique 1986 Paris

Cette thèse est divisée en trois parties: la première partie, précédée d’un chapitre 0 qui précise et justifie vocabulaire et notaions, est composée de deux chapitres I et II, qui traitent du problème de la terminaison distribuée, apprentissage et détection, l’idée maîtresse étant celle de “mot circulant” qui généralise le concept de jeton circulant. Le mot circulant permettant un apprentissage de propriétés de l’algorithme distribué étudié. Le chapitre II fournit de plus un algorithme distribué d’identification des circuits élémentaires d’un graphe. La deuxième partie est consacrée à l’étude de trois grands problèmes combinatoires tels que: La recherche des plus courts chemins dans un graphe valué, pour a résolution duquel nous réutilisons des concepts du chapitre II et pour lequel l’algorithme distribué que nous construisons se distingue des autres algorithmes connus par sa totale asynchronicité (Chapitre III). La recherche d’un arbre couvrant (chapitre IV) pour laquelle, en allant à contrario de quelques idées établies sur la question, on donne un algorithme distribuè totalement asynchrone, minimisant le nombre de messages échangés, et ce, malgré des hypothèses moins restrictives (en particulier, nous admettons la possibilité d’arêtes équipondérées) que les autres algorithmes distribués élaborés pour ce faire. L’énumération implicite parallèle (chapitre V) pour laquelle on fait apparaître, en environment parallèle, des phénomènes nouveaux, en particulier à propos des gains de performance en temps, qui tranchent avec, quelques idées largement répandues. Pour ces trois chapitres, nous donnons la particularisation à un environnement parallèle type machine à mémoire partagée (PRAM), et pour les chapitres III et V, nous donnons, en annexe, les programmes, jeux d’essais et résultats de tests sur CRAY. La troisième partie, tirant les enseignements théoriques des deux précédentes, essaie de donner une définition du concept d’algorithme parallèle et distribuée qui soit cohérente avec ce qui se fait en séquentiel, et qui permette une évaluation et une comparaison des algorithmes parallèles ou distribués (chapitre VI). Le chapitre VII est une application du modèle du chapitre VI à quatre problèmes; recherche du maximum, tri, fusion, et le problème de l’arbre couvrant minimum du chapitre IV.