Return to search

Le problème de décision CSP : homomorphismes et espace logarithmique

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.

Identiferoai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/24161
Date19 April 2018
CreatorsLamontagne, Éric
ContributorsTesson, Pascal
Source SetsUniversité Laval
LanguageFrench
Detected LanguageFrench
Typemémoire de maîtrise, COAR1_1::Texte::Thèse::Mémoire de maîtrise
Format106 p., application/pdf
Rightshttp://purl.org/coar/access_right/c_abf2

Page generated in 0.0019 seconds