Probl mes de Satisfaction de Contraintes

Dans le cadre des TICSP (Problme de Satisfaction de Contraintes pour l'algbre d'Intervalles de Temps), nous avons propos une amlioration de l'algorithme d'Allen. A partir de la composition d'Allen, nous avons propos une composition entre 4 nuds. Puis, sur la base de cette composition, nous avons dvelopp un algorithme incrmental pour la 4- cohrence ramenant la complexit l'ordre O(n3). En utilisant la gnralisation de la composition entre 4 nuds la composition entre k nuds, nous avons propos un algorithme de k-cohrence avec une complexit temporelle en O(nk-1). Le passage des Problmes de Satisfaction de Contraintes (CSP) aux Problmes de Satisfaction de Contraintes Distribus (DCSP) pose le problme du passage de l'individuel au collectif. Ce passage a fait l'objet de diverses extensions du cadre CSP des DCSP. Dans ce cadre et partir de l'algorithme Intelligent BackTracking Distribu (DIBT), nous avons propos une Gnralisation Optimale en envoi de messages (OGDIBT). DIBT n'tant pas complet. Dans ce mmoire, une tude de la compltude d'OGDIBT est propose et une version complte y est donne.