Bienvenido Invitado!

Búsqueda Rápida:  

Búsqueda Avanzada

Idiomas: English Español

Valid XHTML 1.0 Transitional ¡CSS Válido! Icono de conformidad con el Nivel Doble-A, 
	de las Directrices de Accesibilidad para el 
	Contenido Web 1.0 del W3C-WAI

Design and Implementation of Exact MAX-SAT Solvers


Design and Implementation of Exact MAX-SAT Solvers
Design and Implementation of Exact MAX-SAT Solvers

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

Cerrar ventana

Jordi Planes

Acerca de los autores 

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.

Ver Índice Ver Índice (0.06 Mb)

Vista previa Vista previa (0.12 Mb)

Información bibliográfica

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 en

Este eBook está disponible en descarga gratuita

Descargas gratuitas

Descargar eBook Descargar eBook (3.69 Mb)

Este título está en nuestro catálogo electrónico desde el jueves 31 julio, 2014.