Exemplos de Projetos
Lista de Projetos Propostos da UC de 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.
-
Valorização, Interface: poderá usar JPL (Java->SWI/YAP) ou YAP4Py (YAP para Python) para construir uma interface.
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
- evite recursão à esquerda, ie, regras da forma
-
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 |
|
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 |
|
é transformado em
.
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.
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