Departamento de Informática e Estatística

Programas de Ensino
Visitante (Entrar)

Programa de Ensino 20231

Aprovado pelo Departamento em: 3-11-2022

  1. Identificação: Visualizar em PDF
    • 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
  2. Curso(s):
    • Ciências da Computação (208)
  3. Requisito(s):
    • Ciências da Computação (208)
      • INE5403 - Fundamentos de Matemática Discreta para Computação
      • INE5408 - Estruturas de Dados
  4. 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.
  5. 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:
      1. Conhecer os principais modelos de máquinas, suas relações com classes de linguagens, suas complexidades e propriedades;
      2. Entender a noção de computação e de algoritmo;
      3. Compreender a tese de Church-Turing e suas consequências ao estudo da computabilidade efetiva;
      4. Aprender e praticar técnicas de análise de problemas sob a ótica da decidibilidade.
      5. Aprender e praticar o conceito de classes de complexidade de algoritmos e suas consequências à computabilidade prática.
  6. 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
  7. 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.
  8. 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.