Exemplos de Projetos

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

Damas

World Lab

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.

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

World Lab

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.

  • Valorização, Interface: poderá usar JPL (Java->SWI/YAP) ou YAP4Py (YAP para Python) 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 e parser LL, usando DCGs.

    • evite recursão à esquerda, ie, regras da forma
      1
      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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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)].

Binary Decision Diagrams

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. Por exemplo, a função

Para implementar um BDD, pode assuma que recebe uma formula em lógica proposicional. Por exemplo:

1
-x1 * - x2 *-x3 + x1 *x2 +x2 *x3

é transformado em

nesta grafo de decisão.

Repare que a mesma variável podem ter vários nós.

o seu objetivo é verificar a fórmula com um árvore de decisão, onde se x for falso seguimos pela linha fina, e x for falso pela linha mais grossa. Assim, se x1, x2, x3 forem verdadeiros temos: - x1 verdadeiro, logo vamos pela esquerda; - x2 é verdadeiro, o ramo mais grosso é da direita - batemos na folha 1

Para construir a bdd tem primeiro que dar uma ordem às variáveis, Depois pode ir de baixo para cima até completar a árvore.

SAT: Satisfiability Solver

Implemente um provador de fórmulas proposicionais.

  • as fórmulas serão representadas usando CNF, ie, conjunção de disjunções:

ex: (a v b) * ( a + -c + -b)* (a - b +c)

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

    • o algoritmo seleciona uma variável e tenta um valor

    • se falhar usa backtracking.

No ex, tentar a=0, + simplificação: b * (-c-b) * (-c=b) + propagação b=1 -c c=0

  • Valorização: compare com pesquisa local gulosa combinada com troca aleatória de bits (WalkSAT).

Aprendizagem não-relacional

Implemente um algoritmo para dada uma tabela com exemplos atributos e uma coluna especiak, o classe, construir uma árvore de decisão para prever o alvo dado quaisquer valores dos atributos.

Exemplo

No exemplo queremos aprender quano jogar golf. Olhando para cada atributo vemos que de todos os 4, o que reduz mais a entropia é o "Outlook". Há 3 casos: para cada um chamamos o algoritmo até classificar todos os exemplos na mesma classe.

Aprendizagem Multi-Relacional

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