algorithmes hiérarchiques de résolution des problèmes décisionnels de markov et des modèles de markov cachés

Abstract

Cette thèse porte sur la résolution des problèmes de grandes tailles qui sont modélisés par des Modèles Markoviens tels que les Problèmes Décisionnels de Markov et les Modèles de Markov Cachés. Devant la limitation des algorithmes classiques de résolution de ces problèmes notre objectif est de chercher de nouvelles méthodes atténuant les problèmes générés dans le cas des grandes dimensions en réalisant un bon compromis entre qualité de la solution et accélération de la convergence avec un minimum de complexité. Dans la première partie de ce travail, en utilisant la méthode de décomposition conçue aux Problèmes Décisionnels de Markov, nous proposons dans un premier temps, des algorithmes hiérarchiques pour résoudre quelques problèmes fondamentaux des Modèles de Markov Cachés en basant sur une modification au niveau de la méthode de décomposition. Dans un second temps, nous présentons une nouvelle version de l’algorithme d’Itération de la Valeur basée sur la méthode de décomposition et la méthode itérative d’accélération de convergence Gauss-Seidel. À la fin de cette partie, et pour montrer l’efficacité de nos approches, nous avons réalisé une étude détaillée de la complexité et de temps d’exécution résultants. Vu l’importance du parallélisme dans le traitement des données de grandes tailles, dans la dernière partie nous avons débuté par l’introduction d’un procédé de parallélisation pour les problèmes subis de la décomposition, ce genre d’hybridation nous a permis de construire des algorithmes Hiérarchiques Parallèles. Par la suite, nous avons combiné une autre technique de décomposition qu’on a développée, dite décomposition topologique, avec le paradigme du parallélisme, ce qui nous a permis de concevoir des algorithmes Topologiques Parallèles. Enfin, les expérimentations et les évaluations effectuées montrent que les algorithmes proposés, sont compétitifs avec les algorithmes de résolution classiques en termes de qualité, de complexité et de temps de convergence.