Laboratoire dinformatique, Université de Besançon,
Moustafa Nakechbandi juillet 1984
Titre : Algorithmes parallèles dans les problèmes combinatoires
Résumé : Le travail présenté dans cette thèse est relatif à l'utilisation de la machine parallèle dans le domaine combinatoire.
Le Chapitre dintroduction met en évidence la liaison entre algorithmes parallèles et architecture parallèles.
Le chapitre 2 est consacré à l'étude du gain que peut apporter l'introduction du parallélisme pour les algorithmes séquentiels classiques. Ceci aboutit à une contribution originale concernant le passage d'un calcul séquentiel à un calcul parallèle synchrone. Notre modèle est basé sur la décomposition d'un schéma de calcul en actions binairement répétitives ; ce modèle est assez général pour inclure la plupart des algorithmes fondamentaux connus : tris, produit de matrices, résolution de systèmes linéaires, cheminement, composantes fortement connexes.
Les chapitres 3, 4, 5 sont consacré à l'étude des algorithmes nouveaux, conçus pour lexploitation en parallèle. Ces algorithmes touchent des classes très générales de problèmes d'Optimisation combinatoire, à savoir :
- les itérations par voisinage,
- la structure algébrique de cheminement généralisé (proposé par Minoux 1975),
- la programmation linéaire en nombre entier.
En ce qui concerne les itérations par voisinage (chapitre 3), nous proposons une nouvelle méthode d'énumération en parallélisme asynchrone, à partir de laquelle nous étudions plusieurs applications :
- la programmation linéaire (P.L.) afin d'obtenir un algorithme de simplexe asynchrone,
-
la classification automatique afin
d'obtenir un
algorithme de classification par transfert asynchrone,
Dans les deux applications on fournit des résultats expérimentaux par simulation pour la P. L. et par un multiprocesseur, réalisé en laboratoire en reliant 4 microordinateurs Micral 90-50 pour la deuxième application.
En ce qui concerne la structure algébrique de cheminement généralisé (chapitre 4), nous étudions l'application des méthodes d'itération asynchrone pour résoudre une classe très générale de problème de cheminement (problème de plus court chemin avec contraintes temporelles ou avec des arcs libellés par des fonctions de temps). Ces méthodes permettent de constituer des modèles d'interaction des processus de calcul évaluant en parallèle de façon asynchrone. Une analyse de la convergence a été établie. Des essais numériques par simulation sur des graphes pleins ont été effectués. Les résultats expérimentaux de ce chapitre ainsi que ceux du chapitre précédent montrent la faisabilité de l'implémentation de mes algorithmes sur des architectures différentes des multiprocesseurs, et permet, d'autre part, de comparer leur efficacité avec les algorithmes séquentiels.
Au cinquième chapitre, nous proposons un réseau cellulaire (VLSI model) pour résoudre un programme linéaire (P.L.) à deux variables entières. Ce réseau peut être utilisé pour chercher une solution approchée d'un P.L. à deux variables continues. Un programme linéaire quelconque (en variables entières ou continues) sera décomposé en une série de sous P.L. de deux variables. Une fois cette décomposition faite, notre réseau est très efficace pour résoudre cette série de P.L. partiels car la période de notre réseau est faible : elle est de lordre de contraintes du P.L.