Les problèmes de satisfaction de contraintes sont parmi les problèmes fréquents qu'on trouve dans des domaines variés tels que la recherche opérationnelle et l'intelligence artificielle. Dans un problème de satisfaction de contraintes, on cherche à assigner aux variables des valeurs de telle sorte que toutes les contraintes fournies en entrée soient satisfaites. Chaque contrainte est une paire contenant un tuple de variables et une relation définissant les combinaisons de valeurs autorisées pour ce tuple. Ce problème est NP-complet, donc il est important d'identifier des cas particuliers résolubles en temps polynomial. Dans ce travail, on s'intéresse à une approche dite algébrique pour découvrir des classes de problèmes de satisfaction de contraintes traitables efficacement. On se base sur le résultat prouvé par Dalmau "en 2006" qui donne un algorithme polynomial pour une classe assez vaste de problèmes. On analyse et implémente un cas particulier de cet algorithme qui permet de résoudre des instances de 2-SAT. Cette implementation nous aidera à faire des expérimentations et à en apprendre plus sur la nature de l'algorithme de Dalmau et son comportement en pratique.
| Identifer | oai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/23332 |
| Date | 18 April 2018 |
| Creators | Kharrat, Ons |
| Contributors | Tesson, Pascal, Quimper, Claude-Guy |
| 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 | v, 80 p., application/pdf |
| Rights | http://purl.org/coar/access_right/c_abf2 |
Page generated in 0.0022 seconds