Satisfação booleana: algoritmos, aplicações, implementações

• Autor(es): Skliarova, Iouliia ; Ferrari, António B.
• Data: 2002
• Origem: Electrónica e Telecomunicações
• Assunto(s): SAT; Satisfação booleana; Algoritmos
• Tipo de Documento: Artigo científico
• Idioma: Português

Descrição

This paper presents the detailed description of the Boolean satisfiability (SAT) problem and considers the complete discrete algorithms that are commonly employed in its solution. It is demonstrated that SAT has numerous practical applications. Thus the design and implementation of efficient algorithms is of great importance today. Finally, various realizations of SAT solvers based on reconfigurable hardware are analyzed and compared.

Neste artigo considera-se em detalhe o problema de satisfação booleana (SAT) e descrevem-se os algoritmos discretos completos que são normalmente utilizados para a sua solução. É mostrado que SAT tem inúmeras aplicações práticas. Portanto, o desenvolvimento e a implementação de algoritmos eficientes assumem actualmente grande importância. Finalmente, são analisadas várias realizações de algoritmos baseadas em hardware reconfigurável e é comparado o seu desempenho.