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

Authors: Kharrat, Ons
Advisor: Quimper, Claude-GuyTesson, Pascal
Abstract: 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.
Document Type: Mémoire de maîtrise
Issue Date: 2012
Open Access Date: 18 April 2018
Permalink: http://hdl.handle.net/20.500.11794/23332
Grantor: Université Laval
Collection:Thèses et mémoires

Files in this item:
SizeFormat 
28877.pdf24.18 MBAdobe PDFView/Open
All documents in CorpusUL are protected by Copyright Act of Canada.