• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.45.2011.tde-02062011-181639
Documento
Autor
Nome completo
Glauber de Bona
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2011
Orientador
Banca examinadora
Finger, Marcelo (Presidente)
Aragão, Marcus Vinicius Soledade Poggi de
Cozman, Fabio Gagliardi
Título em português
Satisfazibilidade probabilística
Palavras-chave em português
lógica probabilística
redução de Turing
redução polinomial
satisfazibilidade (SAT)
satisfazibilidade probabilística (PSAT)
transição de fase
Resumo em português
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 o 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 m de investigar o perl de complexidade do PSAT, observamos o fenômeno de transição de fase e discutimos as condições para sua detecção.
Título em inglês
Probabilistic satisfiability
Palavras-chave em inglês
phase transition
polynomial reduction
probabilistic logic
probabilistic satisfiability (PSAT)
satisfiability (SAT)
Turing reduction
Resumo em inglês
This work studies the Probabilistic Satisfiability problem (PSAT), reviewing its solution through linear programming, and proposing new algorithms to solve it. We construct a polynomial many-to-one reduction from PSAT to SAT, called Canonical Reduction, codifying rational arithmetic operations into bits, as logical variables. We analyze the computational complexity of this reduction and we propose a Limited Precision Canonical Reduction to reduce such complexity. We present a Turing Reduction from PSAT to SAT, based on the Simplex algorithm and the Atomic Normal Form we introduced. We suggest modifications in such reduction looking for computational eficiency. Finally, we implement these reductions in order to investigate the complexity profile of PSAT, the phase transition phenomenom is observed and the conditions for its detection are discussed.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
tese.pdf (1.06 Mbytes)
Data de Publicação
2011-07-20
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2022. Todos os direitos reservados.