Exportar registro bibliográfico

Análise das distribuições do número de operaçõies de resolvedores SAT (2012)

  • Authors:
  • Autor USP: REIS, POLIANA MAGALHÃES - IME
  • Unidade: IME
  • Sigla do Departamento: MAC
  • Assunto: INTELIGÊNCIA ARTIFICIAL
  • Language: Português
  • Abstract: No estudo da complexidade de problemas computacionais destacam-se duas classes conhecidas como P e NP. A questão P=NP é um dos maiores problemas nãp resolvidos em Ciência da Computação teórica e Matemática contemporânea. O problema SAT foi o primeiro reconhecido como NP-completo e consiste em verificar se uma detrminada fórmula da lógica proporcional clássica é ou não satisfazível. As implementações de algoritmos para resolver problemas SAT são conhecidas como resolvedores SAT (STA solvers). Existem diversas aplicações em Ciência da Computação que podem ser realizadas com SAT Solvers e com outros resolvedores de problemas NP-completos que podem ser reduzidos ao SAT como por exemplo problemas de coloração de grafos, problemas de agendamento e problemas de planejamento. Dentre os mais eficientes algoritmos para resolvedores de SAT estão Sato, Grasp, Chaff, MiniSat e Berkmin. O algoritmo Chaff é baseado no algoritmo DPLL o qual existe há mais de 40 anos e é a estratégia mais utilizada para os Sat solvers. Essa dissertação apresenta um estudo aprofundado do comportamento do zChaff (uma implementação muito eficiente do Chaff) para saber o que esperar de suas execuções em geral.
  • Imprenta:
  • Data da defesa: 28.02.2012
  • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      REIS, Poliana Magalhães; FINGER, Marcelo. Análise das distribuições do número de operaçõies de resolvedores SAT. 2012.Universidade de São Paulo, São Paulo, 2012. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21012013-220441 >.
    • APA

      Reis, P. M., & Finger, M. (2012). Análise das distribuições do número de operaçõies de resolvedores SAT. Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21012013-220441
    • NLM

      Reis PM, Finger M. Análise das distribuições do número de operaçõies de resolvedores SAT [Internet]. 2012 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21012013-220441
    • Vancouver

      Reis PM, Finger M. Análise das distribuições do número de operaçõies de resolvedores SAT [Internet]. 2012 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21012013-220441

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

    Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2021