PT | EN

MINISTÉRIO DA EDUCAÇÃO

UNIVERSIDADE FEDERAL DE SANTA CATARINA

CENTRO TECNOLÓGICO

DEPARTAMENTO DE INFORMÁTICA E ESTATÍSTICA

PROGRAMA DE ENSINO

1. Identificação

Disciplina:INE5415 - Teoria da Computação
Nível:Graduação
Carga Horária:72 horas-aula (Teórica: 72)
Vigência:De 2023-1 até a presente data

2. 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.

3. Cursos Relacionados

4. Objetivos

4.1 Objetivo 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.

4.2 Objetivos 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.

5. Conteúdo Programático

  1. 1. Apresentação da Disciplina e seu contexto histórico [02 horas-aula]
  2. 2. Introdução a Linguagens Formais [04 horas-aula]
    1. 2.1. Problemas e Representação de Instâncias de Problemas;
    2. 2.2. Alfabeto;
    3. 2.3. Palavra e Palavra vazia;
    4. 2.4. Linguagem;
    5. 2.5. Operações sobre linguagens.
  3. 3. Autômatos Finitos [16 horas-aula]
    1. 3.1. Autômatos Finitos Determinísticos como modelos de computação;
    2. 3.2. Construção de Autômatos Finitos para reconhecer linguagens;
    3. 3.3. Configuração e Computação em Autômatos Finitos
    4. 3.4. Autômatos Finitos não Determinísticos
    5. 3.5. Configuração e Computação em Autômatos Finitos não Determinísticos
    6. 3.6. Equivalência entre AF e AFND
    7. 3.7. Linguagens Regulares, Propriedades e Linguagens que não são reconhecidas por AF.
  4. 4. Autômatos de Pilha [08 horas-aula]
    1. 4.1. Autômatos de Pilha como Modelos de Computação;
    2. 4.2. Construção de Autômatos de Pilha para reconhecer linguagens;
    3. 4.3. Autômatos Pilha Determinísticos e Não Determinísticos; linguagens inerentemente ambíguas;
    4. 4.4. Configuração e Computação em Autômatos de Pilha
    5. 4.5. Linguagens Livres de Contexto, Propriedades e Linguagens que não são reconhecidas por AP.
  5. 5. Máquinas de Turing [14 horas-aula]
    1. 5.1. Máquinas de Turing como Modelo Definitivo de Computação;
    2. 5.2. Construção de Máquinas de Turing para reconhecer linguagens e computar funções;
    3. 5.3. Configuração e Computação em MT
    4. 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. 6. Computabilidade e Indecidibilidade [14 horas-aula]
    1. 6.1. Propriedade de um Algoritmo
    2. 6.2. Máquina de Turing Universal
    3. 6.3. Provas de Decidibilidade utilizado máquinas de Turing
    4. 6.4. Problema da Parada
    5. 6.5. Reduções e Provas de indecidibilidade
    6. 6.6. Problema da Correspondência de Post e o Teorema de Rice
  7. 7. Tratabilidade [14 horas-aula]
    1. 7.1. Análise de Complexidade e Ordens assintóticas
    2. 7.2. Complexidade no tempo
    3. 7.3. Classe P, NP e NP-Completos
    4. 7.4. Teorema de Cook-Levin
    5. 7.5. Complexidade no espaço
    6. 7.6. Teorema de Savitch
    7. 7.7. Classe PSPACE
    8. 7.8. Classes L e NL
    9. 7.9. Noções de intratabilidade

6. Bibliografia Básica

  1. Michael Sipser, Introdução a Teoria da Computação, 2a. Edição, Cengage Learning, 2012.
  2. 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.
  3. Lewis, H.R., Papadimitriou, C.H., Elementos de Teoria da Computação, 2a. edição, Bookman, 2000.

7. Bibliografia Complementar

  1. Carnielli, W. e Epstein, R.L., Computabilidade, Funções Computáveis,
  2. Lógica e os Fundamentos da Matemática, Editora Unesp, 2006
  3. Tiarajú A. Diverio e Paulo B. Menezes, Teoria da Computação: Máquinas Universais e Computabilidade, 3a. Edição, URGS, 2011.
  4. Hopcroft, J. E., ULLMAM, J. D. Formal Languagens and Their Relations to Automata. Addison-Wesley, 1969.