O Algoritmo de Dubois e a transição de fase

-----------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------

Título:O Algoritmo de Dubois e a transição de fase
Palestrante: Eduardo Menezes

Data:   23/04/2009, 14h00
Local:  Sala 241A, IME-USP

A transição de fase no problema da satisfatibilidade booleana (SAT)  é um
fenômeno que afeta a maioria dos algoritmos utilizados hoje em dia e dificulta
muito o problema SAT para um certo intervalo de instâncias.
Neste seminário, será apresentado um algoritmo criado em 1989 por Olivier
Dubois. Esse algoritmo possui uma propriedade interessante: parece não sofrer
alteração no comportamento quando está na região da transição de fase.
Também serão apresentados idéia de otimizações que podem ser aplicadas ao
algoritmo de Dubois na tentativa de torná-lo mais competitivo em comparação com
os algoritmos atuais.
--
 Marcelo Finger
 Departamento de Ciencia da Computacao
 Instituto de Matematica e Estatistica | home page:
 Universidade de Sao Paulo             |   www.ime.usp.br/~mfinger
 Rua do Matao, 1010                    | Tel: +55 11 3091 6310, 3091 6135
 05508-090    Sao Paulo, SP     Brazil | Fax: +55 11 3091 6134, 3814 4135