Abstract FR:

L'objet de cette thèse est de présenter de nouvelles approches de résolution de certains problèmes combinatoires de la classe NP-Complet. Ces approches sont représentées par des algorithmes efficaces basés sur des métaphores physiques ou sur des modèles qui se caractérisent par des solutions non combinatoires. Dans la première partie nous définirons les problèmes combinatoires traites, et les modèles mathématiques que nous avons défini pour les étudier. Nous avons aussi, pour chacun des problèmes étudiés, défini les algorithmes classiques de résolution optimale et approchée, ainsi que les méthodes et les heuristiques proposées. Dans la seconde partie, nous avons illustré par une étude expérimentale et comparative, les performances ainsi que les lacunes des différents algorithmes présentés