Laboratoire dinformatique, Université de Besançon,
Moustafa Nakechbandi, decembre,1979.
Titre : Quelques problèmes numériques et non numériques en calcul parallèle
Résumé : On étudie lexistence du paraplasme dans les problèmes suivants :
1. La programmation linaire,
2. Les procédures arborescentes doptimisation « Branch and Bound »,
3. La programmation dynamique,
4. Problème de cheminement.
Pour le problème (1), on présente une nouvelle méthode du simplexe parallèle qui consiste à faire entrer plusieurs variables dans la base au lieu dune seule dans la méthode classique. Pour le problème (2) on propose une stratégie dexploration de larborescence de recherche adaptée au calcule parallèles. Cette stratégie est une combinaison de deux stratégies classiques : « en profondeur dabord » et « le meilleur dabord ». Pour le problème (3) et (4) on analyse lintroduction parallélisme dans les algorithmes classiques. Il y a pour chaque problème une étude de complexité et une simulation sur monoprocesseur pour (1) et (2).