Universidade Federal do Paraná

Disciplina: Inteligência Artificial

Carga horária: 60 horas - 4 créditos

Tema: Introdução aos conceitos da Inteligência Artificial clássica


EMENTA:
Lógica e  programação  em  Lógica. Algoritmos  de  busca  heurística,  solução
(absoluta e relativa)  de problemas  e sua  aplicações: caminho  mínimo e  não
mmínimo, quebra-cabeças,  jogos, planejamento.  Representação do  conhecimento
(nos  paradigmas  de  Lógica  e  Orientação  a  Objetos)  e  suas  aplicações:
conhecimento de senso comum e conhecimento especializado.



OBJETIVO:

Dar uma visão introdutória e aprofundada (formativa) dos conceitos da
Inteligência Artificial clássica (simbólica) que podem ser aplicados na
representação e na automação da solução de problemas variados.

O curso é dividido em 3 (três) partes. Na primeira parte, será feita uma breve
revisão de Lógica Proposicional  assim como de Lógica  de Predicados para  que
seja possível entender os princípios de  Programação em Lógica. O conteúdo  da
primeira parte compreende ainda uma abordagem prática de uso e de análise  das
limitações de provadores como instrumentos de Programação em Lógica.

A segunda  parte é  constituída de  uma abordagem  sobre Algoritmos  de  busca
heurística e suas aplicações. O conceito de divisibilidade de problemas  serve
como fundamento desta parte. Na sequência, o conceito de algoritmo de  busca é
apresentado de forma separada do  conceito de heurística. Aplicações de  busca
heurística são direcionadas para jogos e planejamento.

A Representação de Conhecimento humano é o foco da terceira e última parte  da
disciplina. Ela compreende  o estudo  exaustivo e comparativo  das ténicas  de
descrição interna de elementos complexos. Tais elementos podem ser  associados
a Algoritmos padronizados, os quais  são responsáveis por alterar e  consultar
os conteúdos da descição interna.


PROGRAMA:
1. Visão geral: Introdução à ideia de imitar o comportamento humano utilizando
uma máquina como  meio. O  conceito de "inteligência"  e suas  características
básicas. O Teste de Turing.

2. Revisão de Lógica Proposicional. Breve apresentação de Lógica de Predicados
de Primeira Ordem.

3. Introdução ao conceito de Programação em Lógica. A linguagem Prolog e  suas
variações. Princípios  de  funcionamento  da  máquina  Prolog.  Construção  de
predicados para problemas  clássicos. Abordagem de  eficiência da execução  do
código gerado.

4.  Conceitos  de  solução  automática  de  problemas.  Divisibilidade  de  um
problema. Busca  cega/exaustiva. Explosão  combinatória  do espaço  de  busca.
Aplicação de funções heurísticas. Busca heurística.

5. Algoritmos tradicionais de Busca heurística  em Grafos OU. Gerar e  Testar.
Melhor escolha com arcabouço genérico (A*) e sem arcabouço (IDA*. SMA*).
Análise  Intermediária (alternada/progressivo-regressiva). Subida de Encosta
(Simples, da Trilha maisíngreme). Têmpera Simulada. Satisfação de Restrições
(Profundidade com Meta-heurísticas, Controle Progressivo de Poda).

6. Algoritmos tradicionais de Busca heurística em Grafos E-OU. Fundamentos  da
representação por Grafos E-OU em contraponto  à de Grafos OU. Algoritmo  SSS*.
Algoritmo Poda Alfa-Beta.

7. Aplicação de  conceitos de Busca  heurística para planejamento  automático.
Sequências de ações como solução de problemas. O mundo de blocos virtuais.

8. Conceitos clássicos de Representação de Conhecimento humano.  Representação
interna e  externa  do conhecimento.  A  pre-suposição da  exeistência  de  um
sistema de símbolos. Abordagem  dos diferentes tipos  de representação e  suas
implementações. Representação abstrata e o mundo físico.

9. Técnicas  tradicionais  de Representação  de  Conhecimento.  Representações
orientadas por assertiva: Regras de  Produção, Regras de Horn.  Representações
orientadas a objeto: Frames, Redes Semânticas.


Bibliografia:

   *  Stuart  Russell  e  Peter  Norvig.  Artificial  Intelligence:  A  Modern
Approach. Prentice Hall (2a. ed.), 2004.

   * Ulf Nilsson e Jan Maluszynski. Logic, Programming and Prolog. John  Wiley
&    Sons    Ltd    (2a.    ed.),    1995.    (Atualmente    disponível     em
http://www.ida.liu.se/~ulfni/lpp/ para cópia).

   *  Eurgene  Charniak,  Drew   V.  McDermott.  Introduction  to   Artificial
Intelligence. Addison-Wesley, 1985.

   *   Ivan   Bratko.   Prolog   Programming   for   Artificial   Intelligence
(International Computer Science Series). Addison-Wesley, 1993.

   *  Artificial  Intelligence  Techniques  in  Prolog.  Yoav  Shoham,  Morgan
Kaufmann, 1994.

   * W. F. Clocksin e C.  S. Mellish. Programming in Prolog.  Springer-Verlag,
1987.

   * Artificial  Intelligence.  Patrick  Winston,  Addison-Wesley,  1992,  3rd
Edition.

   *  Sistemas  Inteligentes:  Fundamentos  e  Aplicacoes.  Solange   Oliveira
Rezende, Ed. Manole (SP), 2003 (ISBN: 85-204-1683-7).



Software de Apoio:

- Poplog: http://www.cs.bham.ac.uk/research/poplog/freepoplog.html

- SWI-Prolog: http://www.swi-prolog.org/



Avaliação:

A avaliação consiste de dois trabalhos e duas provas.