Return to search

Étude d'un algorithme pour 2-SAT via les opérations de majorité-minorité généralisées

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.

Identiferoai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/23332
Date18 April 2018
CreatorsKharrat, Ons
ContributorsTesson, Pascal, Quimper, Claude-Guy
Source SetsUniversité Laval
LanguageFrench
Detected LanguageFrench
Typemémoire de maîtrise, COAR1_1::Texte::Thèse::Mémoire de maîtrise
Formatv, 80 p., application/pdf
Rightshttp://purl.org/coar/access_right/c_abf2

Page generated in 0.0023 seconds