Programa de Ensino 20231
Aprovado pelo Departamento em: 3-11-2022
- Identificação:
- Disciplina: INE5415 - Teoria da Computação
- Carga horária: 72 horas-aula
Teóricas: 72
Práticas: 0
- Período:
1º semestre de 2023 até a presente data
- Curso(s):
- Ciências da Computação (208)
- Requisito(s):
- Ciências da Computação (208)
- INE5403 - Fundamentos de Matemática Discreta para Computação
- INE5408 - Estruturas de Dados
- Ementa:
- Programas, Máquinas e Computações. Máquinas de Turing. Funções Recursivas. Computabilidade. Decidibilidade. Análise e Complexidade de Algoritmos. Classes e complexidade de problemas computacionais.
- Objetivo(s):
- Geral: Fazer com que o aluno aprenda alguns dos principais fundamentos da Teoria da Computação, suas consequências à análise de problemas, e saiba aplicá-los na busca e análise de soluções algorítmicas.
- Específicos:
- Conhecer os principais modelos de máquinas, suas relações com classes de linguagens, suas complexidades e propriedades;
- Entender a noção de computação e de algoritmo;
- Compreender a tese de Church-Turing e suas consequências ao estudo da computabilidade efetiva;
- Aprender e praticar técnicas de análise de problemas sob a ótica da decidibilidade.
- Aprender e praticar o conceito de classes de complexidade de algoritmos e suas consequências à computabilidade prática.
- Conteúdo Programático:
- 1. Apresentação da Disciplina e seu contexto histórico [02 horas-aula]
- 2. Introdução a Linguagens Formais [04 horas-aula]
- 2.1. Problemas e Representação de Instâncias de Problemas;
- 2.2. Alfabeto;
- 2.3. Palavra e Palavra vazia;
- 2.4. Linguagem;
- 2.5. Operações sobre linguagens.
- 3. Autômatos Finitos [16 horas-aula]
- 3.1. Autômatos Finitos Determinísticos como modelos de computação;
- 3.2. Construção de Autômatos Finitos para reconhecer linguagens;
- 3.3. Configuração e Computação em Autômatos Finitos
- 3.4. Autômatos Finitos não Determinísticos
- 3.5. Configuração e Computação em Autômatos Finitos não Determinísticos
- 3.6. Equivalência entre AF e AFND
- 3.7. Linguagens Regulares, Propriedades e Linguagens que não são reconhecidas por AF.
- 4. Autômatos de Pilha [08 horas-aula]
- 4.1. Autômatos de Pilha como Modelos de Computação;
- 4.2. Construção de Autômatos de Pilha para reconhecer linguagens;
- 4.3. Autômatos Pilha Determinísticos e Não Determinísticos; linguagens inerentemente ambíguas;
- 4.4. Configuração e Computação em Autômatos de Pilha
- 4.5. Linguagens Livres de Contexto, Propriedades e Linguagens que não são reconhecidas por AP.
- 5. Máquinas de Turing [14 horas-aula]
- 5.1. Máquinas de Turing como Modelo Definitivo de Computação;
- 5.2. Construção de Máquinas de Turing para reconhecer linguagens e computar funções;
- 5.3. Configuração e Computação em MT
- 5.4. Variantes de Máquinas de Turing: Multifitas, Não Determinísticas e Enumeradores - Configuração e Computação; Equivalências entre os modelos
- 6. Computabilidade e Indecidibilidade [14 horas-aula]
- 6.1. Propriedade de um Algoritmo
- 6.2. Máquina de Turing Universal
- 6.3. Provas de Decidibilidade utilizado máquinas de Turing
- 6.4. Problema da Parada
- 6.5. Reduções e Provas de indecidibilidade
- 6.6. Problema da Correspondência de Post e o Teorema de Rice
- 7. Tratabilidade [14 horas-aula]
- 7.1. Análise de Complexidade e Ordens assintóticas
- 7.2. Complexidade no tempo
- 7.3. Classe P, NP e NP-Completos
- 7.4. Teorema de Cook-Levin
- 7.5. Complexidade no espaço
- 7.6. Teorema de Savitch
- 7.7. Classe PSPACE
- 7.8. Classes L e NL
- 7.9. Noções de intratabilidade
- Bibliografia Básica:
- Michael Sipser, Introdução a Teoria da Computação, 2a. Edição, Cengage Learning, 2012.
- Hopcroft, J. F., ULLMAN, J. D., MOTWANI, R. Introdução à Teoria de Autômatos, Linguagens e Computação, Tradução da segunda edição Americana,Elsevier Editora Ltda, 2003.
- Lewis, H.R., Papadimitriou, C.H., Elementos de Teoria da Computação, 2a. edição, Bookman, 2000.
- Bibliografia Complementar:
- Carnielli, W. e Epstein, R.L., Computabilidade, Funções Computáveis,
- Lógica e os Fundamentos da Matemática, Editora Unesp, 2006
- Tiarajú A. Diverio e Paulo B. Menezes, Teoria da Computação: Máquinas Universais e Computabilidade, 3a. Edição, URGS, 2011.
- Hopcroft, J. E., ULLMAM, J. D. Formal Languagens and Their Relations to Automata. Addison-Wesley, 1969.