TEORIA DA COMPUTAÇÃO

Obrigatória: Sim (*)

Carga Horária: 60

Créditos: 4

OBJETIVOS:
Estudar os princípios da Teoria Clássica da Computação, enfatizando as noções de computabilidade, decidibilidade, complexidade de problemas e algoritmos.

EMENTA:
Modelos computacionais. Tese de Church. O problema da parada. Redutibilidade de problemas. A noção de problema e de complexidade de problemas. Complexidade de tempo. Complexidade de espaço. Classes de complexidade de tempo: P, NP, P=NP?. Intratabilidade. Análise da complexidade de Algoritmos. Projeto de Algoritmos Ótimos e Aproximativos.

PROGRAMA:
1. Modelos Computacionais
1.1 Máquina de Turing
1.2 Extensões da Máquina de Turing
1.3 Funções recursivas
2. Indecidibilidade
2.1 Tese de Church-Turing
2.2 O Problema da Parada
2.3 Problemas Indecidíveis sobre Máquinas de Turing
2.4 Propriedades das Linguagens Recursivas
3. Complexidade Computacional
3.1 Classes de Complexidade
3.2 Problemas Intratáveis
3.3 Complexidade de Tempo e Espaço
4. Análise da Complexidade de Algoritmos
4.1 Análise de pior caso
4.2 Análise de caso médio
5. Projeto de Algoritmos
5.1 Algoritmos Ótimos
-Divisão e Conquista
-Programação Dinâmica
-Algoritmos Gulosos
5.2 Algoritmos Aproximativos e Heurísticas

Bibliografia:
ATALLAH, M. J. Handbook of Algorithms and Theory of Computation. New York:CRC Press, 1999.

CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L. Introduction to Algorithms. Cambridge: MIT Press, 1994. Greenlaw, R.; Hoover, H. J. Fundamentals of the Theory of Computation. Morgan Kaufmann, 1998.

HOROWITZ, E.; SAHNI, S. Fundamentals of Computer Algorithms. Computer Science Press, 1978.

GAREY, M. R. ; JONHSON, D. S. Computers and Intractability: a guide to the theory of NP-Completeness. New York: W. H. Freeman and Company, 1997.

LEWIS, H. R.; PAPPADIMITRIOU, C. H. Elements of the Theory of Computation. Englewood, Cliffs: Prentice-Hall, 1981.

LEWIS, H. R.; PAPPADIMITRIOU, C. H. Elementos de Teoria da Computação. Porto Alegre: Bookman, 2000.

MARTIN, J. C. Introduction to Languages and The Theory of Computation. New York:McGraw-Hill, 1997.

SIPSER, M. Introduction to the Theory of Computation. Course Technology. 1st edition, 1996.

TOSCANI, L. V.; Veloso, P. A. S. Complexidade de algoritmos : análise, projeto e métodos. Porto Alegre: Sagra Luzzatto, 2001.

(*) A disciplina pode ser dispensada, por meio de uma prova, mas sem aproveitamento dos créditos.