Ver registro no DEDALUS
Exportar registro bibliográfico

Satisfazibilidade probabilística (2011)

  • Authors:
  • USP affiliated authors: BONA, GLAUBER DE - IME
  • USP Schools: IME
  • Sigla do Departamento: MAC
  • Subjects: INTELIGÊNCIA ARTIFICIAL
  • Language: Português
  • Abstract: Este trabalho estuda o problema da satisfazibilidade probabilística (PSAT), revendo a sua solução via programação linear, além de propor novos algoritmos para resolvê-lo através da redução ao SAT. Construímos uma redução polinomial do PSAT para SAT, chamada de Redução Canônica, codificando operações da aritmética racional em bits, como variáveis lógicas. Analisamos a complexidade computacional dessa redução e propomos uma redução canônica de precisão limitada para contornar tal complexidade. Apresentamos uma redução de turing do PSAT ao SAT, baseada no algoritmo simplex e na forma normal atômica que introduzimos. Sugerimos modificações em tal redução em busca de eficiência computacional. Por fim, implementamos essas reduções a fim de investigar o perfil de complexidade do PSAT, observamos o fenômeno de transição de fase e discutimos as condições para sua detecção.
  • Imprenta:
  • Data da defesa: 20.05.2011
  • Acesso online ao documento

    Online access or search this record in

    Exemplares físicos disponíveis nas Bibliotecas da USP
    BibliotecaCód. de barrasNúm. de chamada
    IME31000066623QA860.T D287s e.2
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      DE BONA, Glauber; FINGER, Marcelo. Satisfazibilidade probabilística. 2011.Universidade de São Paulo, São Paulo, 2011. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-02062011-181639 >.
    • APA

      De Bona, G., & Finger, M. (2011). Satisfazibilidade probabilística. Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-02062011-181639
    • NLM

      De Bona G, Finger M. Satisfazibilidade probabilística [Internet]. 2011 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-02062011-181639
    • Vancouver

      De Bona G, Finger M. Satisfazibilidade probabilística [Internet]. 2011 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-02062011-181639