Carregando...

DISCIPLINA Listagem de Ementa/Programa

TEORIA DA COMPUTAÇÃODISCIPLINA 316296

VER OFERTA

ÓrgãoCIC Departamento de Ciência da Computação
Código316296
DenominaçãoTeoria da Computação
NívelMestrado
Vigência1971/2
Pré-requisitosDisciplina sem pré-requisitos
Ementa

- Revisão dos fundamentos teóricos da computação: geração e reconhecimento de linguagens formais e funções computáveis.

- Fundamentos de programação lógica: noções de lógica matemática, unificação, teoria de pontos fixos, programas definidos, tratamento de informação negativa computabilidade de funções recursivas com programas lógicos.

- Fundamentos de teoria de reescrita: lambda cálculo, sistemas abstratos de reescrita, sistemas de reescrita de termos e computabilidade de funções recursivas com sistemas de reescrita.

Programa

1- Revisão dos fundamentos teóricos da computação:

- Geração e reconhecimento de linguagens formais: linguagens regulares e autômatos finitos, linguagens livres de contexto e autômatos a pilha, linguagens recursivas e máquinas de Turing, a tese de Church.
- Funções Computáveis: conjuntos enumeráveis e não-enumeráveis, conjuntos recursivamente enumeráveis, funções recursivas primitivas e funções recursivas parciais.

2- Fundamentos da programação lógica:

- Noções de lógica matemática: sintaxe, semântica, teorias de primeira ordem, skolemização e resolução no cálculo proposicional;
- Unificação;
- Teoria de pontos fixos;
- Programas definidos: SLD-resolução, completude e corretude da SLD-resolução, adequabilidade computacional da SLD-resolução e computação de funções recursivas parciais com SLD-resolução.

3-- Fundamentos de teoria de reescrita:

- Motivação;
- O lambda cáculo: adequabilidade computacional do lambda cálculo.
- Sistemas abstratos de reescrita: terminação e confluência de sistemas de reescrita
- Sistemas de reescrita de termos (TRS): terminação e confluência de TRS, lema dos pares críticos e completação de Knuth-Bendix;
- Estreitamento.

Bibliografia

- M. Ayala-Rincón. Fundamentos da Programação Lógica e Funcional. Notas de aula versão 2006. Disponível em http://ayala.mat.unb.br

- F. Baader and T. Nipkow.Term Rewriting and All That. CUP, 1998.

- W. Carnielli e R. L. Epstein. Computabilidade, Funções Computáveis, Lógica e os Fundamentos da Matemática, Editora Unesp, 2006.

- K. Doets. From Logic to Logic Programming, MIT Press, 1994.

- J. E. Hopcroft, R. Motwani and J. D. Ullman. Introduction to Automata Theory, Languages and Computation.Addison-Wesley, Third Edition, 2006.

- D. Kelley Automata and Formal Languages - An Introduction. Prentice Hall, 1995.

- J. W. Lloyd. Foundations of Logic Programming, Symbolic Computation - Artificial Intelligence. Springer, second edition, 1987.

- M. Sipser Introduction to the Theory of Computation.PWS Publishing Company, 1997.

- TERESE. Term Rewriting Systems. Cambridge Tracts in Theoretical Computer Science, Vol. 55, Cambridge University Press, 2003.