Lista de Projetos Propostos para Programação em Lógica

Damas

Implemente um jogador capaz de jogar o jogo de Damas:

• Implemente minimax com alfa-beta pruning para procurar o espaço de procura, Veja o cap 24 do livro "Prolog Programming for Artificial Intelligence"

• A função de avaliação poderá ser desenhada à mõo, mas valerá a pena olhar para a literatura sobre o assunto.

  • Tim Wheeler
  • Anders Baumann
  • Chinook

• Valorização, Interface: poderá usar JPL (Java->SWI/YAP) ou SWIG (JAVA para YAP) para construir uma interface.

Compilador

Implemente um compilador em Prolog:

• Comece por definir uma linguagem de trabalho: sugerimos um subconjunto da linguagem Tiger, usada no livro "Modern Compiler Implementation"

• Implemente um scanner, usando gramáticas

• implemente um parser LL, usando DCGs.

  • evite recursão à esquerda, ie, regras da forma A --> A B

• Desenhe a tabela de símbolos usando para tal uma árvore. Descreva quais os tipos de nós e campos correspondentes:

  • if_then_else( Teste, If, Else)
  • X1 := X2

• Escreva um compilador para linguagem intermédia de tripletos (uma solução é novamente usar gramática)

compila(if_then_else(Teste, If, Else) , LStart, LEnd) -->
    [label(Start)],
    compila(Teste, LStartIf, LStartElse),
    compila(If,LStartIf,LEndIf),
    [label(LEndIf), jump(LEnd)],
    compila(Else, LStartElse, LEnd).

compila((X1 := X2) , LStart, LEnd) -->
    endereço(X1,A1),
    valor(X2,V2),
    [move(A1,V2)].

• Escreva um gerador de código MIPS/ARM assumindo um número infinito de registos.

• Valorização: implemente um gerador de código para registos limitados (ideia: mantenha uma cópia na pilha por variável); verificação de tipos.

BDDs

Uma BDD é uma representação de uma sentença em lógica proposicional que permite verificação em tempo linear sobre o número de variáveis:

• a ordem dos nós numa visita é sempre a mesma

• sub-árvores repetidas são compactadas, resultando num DAG

Para implementar um BDD, assuma uma conjunção de fórmulas da forma `x <-> y op z':

• fixe uma ordem de variáveis;

• inicialmente tem dois nós, 0 e 1;

• dada uma expressão x <-> y op z, pode assumir x < y < z e que x aparece no máximo uma vez como lado esquerdo

  • se x ou y novos, gere um novo nó;
  • se x e y pré-existentes, verifique se pode reusar.
  • construa uma expressão para x a partir de x, y, e op.

• Consegue transformar uma fórmula CNF em BDD? Como?

• Implemente uma estratégia de reordenamento dos nós.

SAT

Implemente um provador de fórmulas proposicionais.

• as fórmulas serão representadas usando CNF.

• use o algoritmo Davis–Putnam–Logemann–Loveland (DPLL)

  • o algoritmo seleciona uma variável e tenta os dois valores de verdade possíveis.
  • se um falhar usa backtracking.

• compare com pesquisa local

• Valorização: implemente aprendizagem, sempre que há um conflito, detecte a fonte do conflito e acrescente à teoria CNF.

ILP

Implemente o algoritmo HYPER, começando a partir do descrito no livro "Prolog Programming for Artificial Intelligence"

• Escolha um conjunto de dados e avalie o seu sistema usando validação cruzada.

• Implemente aprendizagem indutiva de árvores descrito no livro e compare os resultados.

• Valorização: converta os seus dados para Weka (CSV ou arff) e compare com os seus resultados. Imp