Teoria da Computação

Descrição da disciplina na página da UDESC

Carga horária (teórica): 30
Carga horária (prática): 30

Objetivo

Ao final do curso, o aluno deverá ser capaz de:

  • descrever os principais modelos de computação
  • enumerar as limitações das Máquinas de Turing
  • listar os principais aspectos relacionados à computabilidade

Ementa

Funções recursivas; Máquinas de Turing; Tese de Church; Gödel e a incompletude; (Lambda) Cálculo; Domínios; Continuidade. Relações entre os modelos de computabilidade.

Programa

1. Histórico, Motivação, Contextualização
1.1 Introdução
1.2 Apresentação do plano de curso e avaliação
1.3 A disciplina no currículo e integração com outras disciplinas
1.4 A disciplina na formação do profissional
1.5 Histórico da Evolução Computação
1.6 Histórico sobre a palavra algoritmo
1.7 Os problemas de David Hilbert
1.8 O Teorema da Incompletude de Goedel.

2. Máquinas de Turing
2.1 Máquina de Turing padrão
2.2 Máquinas de Turing como aceitadores de linguagens
2.3 Máquinas de Turing multi-cabeças
2.4 Máquinas de Turing com fitas infinitas
2.5 Máquinas de Turing multi-fitas
2.6 Máquinas de Turing não-determinísticas
2.7 Máquinas de Turing como enumeradores de linguagens
2.8 Estruturas equivalentes à Máquina de Turing (Máquina de Post, etc.)
2.9 Outras máquinas equivalentes.

3. Decidibilidade
3.1 Problemas de decisão: linguagens regulares e livres de contexto
3.2 Tese de Church-Turing
3.3 Problema da Parada da Máquina de Turing
3.4 Método da Diagonalização
3.5 Problema de Post-Correspondência
3.6 Noções de Lambda Cálculo e sua relação com o coneito de computação.

4. Redutibilidade
4.1 Problemas indecidíveis
4.2 Reduções via históricos da computação
4.3 Mapeamentos da redutibilidade
4.4 Máquina Universal.

5. Teoria da Complexidade
5.1 Complexidade de tempo
5.2 Aceleração linear
5.3 Ordens de complexidade
5.4 Complexidade não-determinística
5.5 Complexidade de espaço.

6. Tratabilidade (intratabilidade)
6.1 Problema tratáveis e intratáveis
6.2 Problemas polinomiais determinísticos (Classe P)
6.3 Problemas polinomiais não-determinísticos (Classe NP)
6.4 Problemas NP-Hard e NP-Completos
6.5 Exemplos de problemas NP.

Bibliografia

SIPSER, Michael. Introdução à Teoria da Computação. São Paulo: Thomson Learning, 2007.

HOPCROFT, John E.; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introdução à Teoria de Autômatos, Linguagens e Computação. Campus, 2002.

LEWIS, Harry R.; PAPADIMITRIOU, Christos H. Elementos de Teoria da Computação. 2.ed. Porto Alegre, Bookman, 2000.

DIVERIO, T. A.; MENEZES, P. F. B. Teoria da Computação: máquinas universais e computabilidade. Porto Alegre: Sagra-Luzzatto, 1999. 205p. ISBN 85.241.0593-3 (Série Livros Didáticos do Instituto de Informática da UFRGS, n.5).

CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Algoritmos – Teoria e Prática, Rio de Janeiro: Campus, 2002.

CARNIELLI, Walter; EPSTEIN, Richard L. Computabilidade, funções computáveis, lógica e os fundamentos da matemática, São Paulo: UNESP, 2006.

Metodologia de ensino

Aulas expositivas

Recursos utilizados

Quadro negro
Retroprojetor

Trabalhos dos alunos

Máquinas de Post e Funções Recursivas
Máquinas de Post

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License