Normal view MARC view ISBD view

Réseaux de contraintes : algorithmes de propagation et de décomposition / par Assef Chmeiss ; sous la direction de Philippe Jégou

Auteur principal : Chmeiss, Assef, AuteurAuteur secondaire : Jégou, Philippe, Directeur de thèseAuteur secondaire collectivité : Université de Provence, Etablissement de soutenanceType de document : ThèseLangue : français.Pays : France.Éditeur : [S.l.] : [s.n.], 1996Description : 1 vol. (100 p.) : fig. ; 30 cmBibliographie : Bibliogr. p. 97-100.Sujet MSC : 68T20, Computer science - Artificial intelligence, Problem solving in the context of artificial intelligence
68Q25, Theory of computing, Analysis of algorithms and problem complexity
68R10, Discrete mathematics in relation to computer science, Graph theory
05C85, Combinatorics - Graph theory, Graph algorithms
97-02, Research exposition (monographs, survey articles) pertaining to mathematics education
Note de thèse: Thèse de doctorat, informatique, 1996, Aix-Marseille 1
Tags from this library: No tags from this library for this title. Log in to add tags.
Current location Call number Status Date due Barcode
CMI
Salle S
Thèses CHM (Browse shelf) Available 00753-01

Bibliogr. p. 97-100

Thèse de doctorat informatique 1996 Aix-Marseille 1

Nous nous intéressons aux problèmes de satisfaction de contraintes (CSP) binaires à domaines finis. Nous travaillons sur la micro-structure de CSP qui est définie par le graphe des relations de comptabilité entre paires de variable-valeur: ces paires constituent les sommets tandis que les arêtes sont définies par les paires compatibles. Dans la première partie de cette thèse, nous montrons comment cette micro-structure peut être simplifiée par des algorithmes de consistance partielle. Nous proposons ainsi trois algorithmes de propagation de contraintes par consistance de chemin. La complexité en temps du premier est optimale mais sa complexité en espace le rend peu utilisable (seulement pour des problèmes de petite taille). En relaxant la complexité en temps, nous établissons un algorithme efficace en pratique avec une complexité spatiale meilleure. Le troisième algorithme n'est, en effet, qu'une optimisation de la complexité en espace du deuxième. Dans la seconde partie nous nous intéressons à la résolution de CSP par décomposition de la micro-structure. Deux méthodes qui reposent sur les propriétés combinatoires et algorithmiques des graphes triangulés sont mises en oeuvre et expérimentées. D'autre part, nous proposons une méthode incomplète de résolution s'appuyant sur la recherche de graphes partiels triangulés. Enfin, dans la dernière partie, nous proposons une généralisation des graphes triangulés qui offre une classe des graphes possédant le même type de propriétés que celles des graphes triangulés

There are no comments for this item.

Log in to your account to post a comment.