EMENTA

DISCIPLINA: Teoria da Computação

CÓDIGO: PGC103

CARGA HORÁRIA: 90h

CRÉDITOS: 5

OBJETIVOS GERAIS DA DISCIPLINA: O curso tem como objetivo responder às seguintes questões fundamentais: Quais são as capacidades e limitações dos computadores? O que faz com que alguns problemas sejam computacionalmente intratáveis?  Ao final do curso, o aluno estará habilitado a utilizar técnicas para demonstrar que certos problemas são impossíveis de serem resolvidos por um computador e que certos problemas, mesmo sendo possivel de ser resolvidos por uma máquina, demandam tempo e/ou espaço em memória impraticáveis.

EMENTA DO PROGRAMA:

Máquinas de Turing – Problemas Decidíveis – Problema da Parada – Redutibilidade –  Problemas Indecidíveis – Problemas Recursivamente Enumeráveis - Complexidade em Tempo – Problemas NP-completos – Complexidade em Espaço – Problemas PSPACE-completos.

DESCRIÇÃO DO PROGRAMA: 

1. Revisão de Teoria das Linguagens: Autômatos e Gramáticas Livres do Contexto Propriedades booleanas das linguagens regulares, lema do bombeamento para    linguagens regulares, gramáticas livres do contexto na forma normal de Chomsky, lema do bombeamento para linguagens livres do contexto.

2. Máquinas de Turing – Definição, Variantes (multi-fitas, não-deterministas, enumeradores)

3. Tese de Church – 10º Problema de Hilbert

4. Decidibilidade

4.1 Linguagens Recursivas (decidíveis), 

4.2 Recursivamente Enumeráveis (Turing-reconhecíveis), 

4.3 Prova da Indecidibilidade do Problema da Parada

4.4 Problemas decidíveis da teoria das linguagens formais

4.5 Problemas indecidíveis da teoria das linguagens formais

4.6 Redutibilidade 

4.7 Método do histórico das configurações

4.8 Problema de Correspondência de Post

5. Tópicos Avançados 

5.1 Teorema de Rice

5.2 Teorema da Recursão

6. Complexidade em Tempo

6.1 Classe P – Classe NP

6.2 O problema P = NP

6.3 Problemas NP-Completos : definição e exemplos

6.4 Técnicas para demonstrar NP-completude

6.5 Teorema de Cook – (demonstrar a NP-Completude do problema SAT)

6.6 Como lidar com problemas NP-completos

7. Complexidade em Espaço

7.1 Classe PSPACE 

7.2 Problemas PSPACE-completos

7.3 Teorema de Savitch

BIBLIOGRAFIA:

01. SIPSER, Michael  : Introduction to the Theory of Computation. Brooks/Cole Pub Co, 2a Edição 2005 (Livro Texto)

02. 3. LEWIS, H., PAPADIMITRIOU, C.: Elements of the Theory of Computation.  Prentice Hall. 2a Edição. 1997.

03. GAREY, M. R.; JOHNSON, D. S. Computers and intractability: a guide to NP-completeness. New York: H. Freeman, 1979. 

04. HAREL, David : Algorithmics – The Spirit of Computing. Addison-Wesley, 2a Edição, 1993.

05. KOZEN, D.: Theory of Computation. Springer, 2006.

06. SIPSER, Michael  : Introduction to the Theory of Computation. Brooks/Cole Pub Co, 2a Edição 2005 (Livro Texto)

07. 3. LEWIS, H., PAPADIMITRIOU, C.: Elements of the Theory of Computation.  Prentice Hall. 2a Edição. 1997.

08. GAREY, M. R.; JOHNSON, D. S. Computers and intractability: a guide to NP-completeness. New York: H. Freeman, 1979. 

09. HAREL, David : Algorithmics – The Spirit of Computing. Addison-Wesley, 2a Edição, 1993.

10. KOZEN, D.: Theory of Computation. Springer, 2006.