Ce mémoire porte sur le problème de décision CSP (de l'anglais Constraint Satisfaction Problem, c'est-à-dire problème de satisfaction de contraintes), soit le problème pour lequel nous devons assigner des valeurs à des variables de telle sorte que toutes les conditions portant sur ces variables soient remplies. De surcroît, ce mémoire porte sur les problèmes de détection d'homomorphisme entre structures relationelles qui sont équivalents à CSP. Pour être plus précis, nous nous intéressons à l'algorithme de cohérence d'arc pour les instances de CSP, soit ArcjConsistency. Celui-ci suffit à solutionner un certain sous-ensemble de CSP. Or nous étudions quelques-unes de ses variantes qui sont des algorithmes plus coûteux, mais plus puissants, c'est-à-dire que le sous-ensemble de CSP qu'ils solutionnent est plus grand. La nouveauté de ce mémoire est de décrire et d'étudier une variante de ArcjConsistency, soit NLjCohérence, qui est un algorithme moins puissant mais plus efficace. L'objectif pour nous est de trouver des caractéristiques intéressantes au sujet de ce nouvel algorithme, qui se veut être une version « espace logarithmique » de ArcjConsistency. De plus, nous travaillons sur un sous-ensemble de CSP dit implicatif. Nous démontrons que NL_Cohérence solutionne les instances de ce sous-ensemble en espace logarithmique non-déterministe.
| Identifer | oai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/24161 |
| Date | 19 April 2018 |
| Creators | Lamontagne, Éric |
| Contributors | Tesson, Pascal |
| Source Sets | Université Laval |
| Language | French |
| Detected Language | French |
| Type | mémoire de maîtrise, COAR1_1::Texte::Thèse::Mémoire de maîtrise |
| Format | 106 p., application/pdf |
| Rights | http://purl.org/coar/access_right/c_abf2 |
Page generated in 0.0019 seconds