Biblioteca Digital da Produção Intelectual Discente: Um algoritmo baseado em programação dinâmica e renomeamento para minimização de formas normais
Utilize este link para identificar ou citar este item: https://bdm.unb.br/handle/10483/14818
2016_MatheusCostadeSousaCarvalhoPimenta.pdf 609,66 kB Adobe PDF ver/abrir
dc.contributor.advisor Nalon, Cláudia -
dc.contributor.author Pimenta, Matheus Costa de Sousa Carvalho -
dc.identifier.citation PIMENTA, Matheus Costa de Sousa Carvalho. Um algoritmo baseado em programação dinâmica e renomeamento para minimização de formas normais. 2016. x, 42 f., il. Monografia (Bacharelado em Ciência da Computação)—Universidade de Brasília, Brasília, 2016. pt_BR
dc.description.abstract Satisfatibilidade booleana é um problema de grande interesse prático, além de ser o primeiro problema caracterizado como NP-completo. Desde que ganhou atenção, diversos algoritmos para este problema já foram descobertos e alguns deles são baseados em formas normais. As transformações usuais para formas normais podem acarretar aumento exponencial do tamanho da fórmula, o que não é desejável. No entanto, é sabido que técnicas como renomeamento podem auxiliar a reduzir o tamanho da fórmula transformada. Neste trabalho, apresentamos uma heurística para o problema de encontrar renomeamentos que reduzem o tamanho de fórmulas e um algoritmo baseado em programação dinâmica para calcular o renomeamento dado pela heurística, junto com sua prova de correção, análise de complexidade e resultados experimentais. A avaliação experimental inclui a comparação do algoritmo proposto com um algoritmo guloso que é ótimo para uma classe restrita do problema. Os resultados indicam que a heurística proposta, na prática, é tão eficiente quanto a do algoritmo ótimo para esta classe, apresentando em alguns casos resultados ainda melhores quando não há restrições sobre a entrada do problema. pt_BR
dc.subject.keyword Satisfatibilidade booleana pt_BR
dc.subject.keyword Programação dinâmica pt_BR
dc.subject.keyword Algoritmos de computador pt_BR
dc.title Um algoritmo baseado em programação dinâmica e renomeamento para minimização de formas normais pt_BR
dc.date.accessioned 2016-09-28T18:22:53Z -
dc.date.available 2016-09-28T18:22:53Z -
dc.identifier.uri http://bdm.unb.br/handle/10483/14818 -
dc.description.abstract1 Boolean satisfiability is a problem of great practical interest and the first problem ever to be stated as NP-complete. Many algorithms for this problem are based on normal forms. Also, naive translations to normal forms may lead to exponential growth on the size of a formula, a highly undesirable effect. It is known, however, that techniques such as formula renaming may help reducing the size of such translation. In this work, we present a heuristic to find renamings that may reduce the size of translated formulæ and a dynamic programming algorithm to compute the renaming given by the heuristic, together with its proof of correctness, complexity analysis and experimental results. We also present comparison results with a greedy algorithm which is optimal for a restricted class of the problem. Empirical evaluation shows that, in most cases, the proposed heuristic produces as fewer clauses as the greedy algorithm for this restricted class of the problem and behaves even better for some specific unrestricted inputs. pt_BR