Jordi Planes Filiación: Consejo Superior de Investigaciones Científicas. Institut d'Investigació en Intel·ligència Artificial (Bellaterra, España) Biografía: No disponible |
Año de publicación: 2008 Idioma: Inglés Materias: Ciencia y Tecnología Colección: Monografies de l'Institut d'Investigació en Intel-ligencia Artificial eBook gratuito |
Resumen:
The Propositional Satisfiability Problem (SAT) is the problem of determining whether a truth assignment satisfies a CNF formula. Nowadays, many hard combinatorial problems such as practical verification problems in hardware and software can be solved efficiently by encoding them into SAT. In this thesis, we focus on the Maximum Satisfiability Problem (MAX-SAT), an optimization version of SAT which consists of finding a truth assignment that satisfies the maximum number of clauses in a CNF formula. We also consider a variant of MAX-SAT, called weighted MAX-SAT, in which every clause is associated with a weight and the problem consists of finding a truth assignment in which the sum of weights of violated clauses is minimum. While SAT is NPcomplete and well-suited for encoding and solving decision problems, MAX-SAT and weighted MAX-SAT are NP-hard and well-suited for encoding and solving optimization problems. This thesis is concerned with the design, implementation and evaluation of exact MAX-SAT solvers based on the branch and bound scheme, with special emphasis on defining good quality lower bounds, powerful inference techniques, clever variable selection heuristics and suitable data structures.
Descripción física del libro: XX, 144 p. : gráf. ; 24 cm
ISBN: 978-84-00-08709-8
Publicación: Bellaterra (España) : Consejo Superior de Investigaciones Científicas, 2008
Referencia CSIC: 11666
Otros datos: Tesis. Universidad de Lleida (España), 2007
Adquirir la edición digital enEste eBook está disponible en descarga gratuita |
Descargas gratuitas |
Este título está en nuestro catálogo electrónico desde el jueves 31 julio, 2014.