Saltar para o conteúdo

DC-UFRPE/Bacharelado em Ciência da Computação/Teoria da Computação

Fonte: Wikiversidade

Programa da Disciplina

[editar | editar código-fonte]
Nome: TEORIA DA COMPUTAÇÃO
Código: 06223
Departamento: Departamento de Computação (DC)
Área: Computação
Carga-horária total: 60 horas
Créditos: 4
Pré-requisitos: 14203 - MATEMÁTICA DISCRETA I 14203 - MATEMÁTICA DISCRETA II

Propriedades e operações com linguagens. Expressões regulares e gramáticas. Modelos de reconhecedores: autômatos finitos, autômatos a pilha, autômatos linearmente limitados, máquinas de Turing. Teorema de Kleene, equivalência entre autômatos à pilha e gramáticas. Hierarquia de Chomsky: linguagens regulares, livre de contexto, sensíveis ao contexto e recursivas. Propriedades de linguagens e funções recursivas. Tese de Church. Problemas indecidíveis: problema da parada, problema da correspondência de Post, redução entre problemas. Classes de problemas: P, NP, NPCompleto.

Metodologia de Aula

[editar | editar código-fonte]
  • Notas de aula divulgadas pelo professor Pablo Sampaio.
  • Aulas Presenciais.
  • Atividades semanais no Google Classroom.
  • Capacitar o aluno na elaboração de algoritmos através do desenvolvimento do raciocínio lógico aplicado à solução de problemas computacionais, tornando-o capaz de resolver problemas simples de forma teórica e aplicá-los na prática em uma linguagem de programação.
  • Apresentar os comandos de entrada e saída e suas utilizações.
  • Apresentar os conceitos de variáveis e constantes e suas utilizações.
  • Apresentar os operadores aritméticos e seu comportamento.
  • Apresentar os operadores relacionais e lógicos e seu comportamento.
  • Desenvolver a habilidade de construção de expressões e sua utilização.
  • Apresentar o conceito de modularização.
  • Desenvolver a habilidade de modularizar problemas em unidade menores.
  1. Breve histórico.
  2. Linguagens e cadeias.
  3. Linguagens regulares.
    1. Autômatos finitos determinísticos;
      1. Definição formal;
      2. Exemplos;
      3. Linguagem de um autômato finito determinístico;
      4. Desenvolvendo autômatos finitos determinísticos;
    2. Autômatos finitos não determinísticos;
      1. Definição formal;
      2. Exemplos;
      3. Linguagem de um autômato finito não determinístico;
      4. Desenvolvendo autômatos finitos não determinísticos;
    3. Equivalência entre autômatos finitos determinísticos e não determinísticos;
    4. Expressões regulares;
      1. Definição;
      2. Exemplos;
      3. Equivalência com autômatos finitos;
    5. Lema do bombeamento para linguagens regulares;
  4. Linguagens livres de contexto.
    1. Gramáticas livres de contexto;
      1. Definição formal;
      2. Exemplos;
      3. Derivação;
      4. Ambiguidade;
      5. Forma normal de Chomsky;
    2. Autômatos de pilha;
      1. Definição formal;
      2. Exemplos;
      3. Equivalência com gramáticas livres de contexto;
    3. Lema do bombeamento para linguagens livres de contexto;
  5. Máquinas de Turing.
    1. Definição formal e exemplos;
    2. Variantes da máquina de Turing (multifita e não determinística);
    3. Desenvolvendo máquinas de Turing;
  6. Indecidibilidade.
    1. Método de diagonalização;
    2. O problema da parada;
    3. Uma linguagem Turing-irreconhecível;
    4. Redução de problemas;
    5. Exemplos de problemas indecidíveis;
    6. Problema de correspondência de Post;
  7. Complexidade de tempo.
    1. Notação assintótica;
    2. A classe P;
    3. A classe NP;
    4. NP-completude;
      1. Reduções em tempo polinomial;
      2. Definição;
      3. Teorema de Cook Levin;
      4. Outros problemas NP-Completos;

Playlist sugerida para estudo.


Mais informação sobre conteúdos pode ser encontrado na antiga página de Teoria da Computação.

Bibliografia Básica

[editar | editar código-fonte]
  • SIPSER, Michael. Introdução à teoria da computação. 2. ed. São Paulo: Thomson, 2007.
  • HOPCROFT, John E.; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introdução à teoria de autômatos, linguagens e computação. Rio de Janeiro: Campus, c2003.
  • LEWIS, Harry R.; PAPADIMITRIOU, Christos H. Elementos de teoria da computação. 2. ed. Porto Alegre: Bookman, 2000.

Bibliografia Complementar

[editar | editar código-fonte]
  • MENEZES, Paulo Blauth. Linguagens formais e autômatos. 5. ed. Porto Alegre: Bookman, 2008.
  • DIVERIO, T. A.; MENEZES, P. B. Teoria da Computação: Máquinas Universais e Computabilidade. 3a edição. Bookman, 2011.
  • GERSTING, J. L. Fundamentos Matemáticos para a Ciência da Computação. Quinta Edição. Rio de Janeiro: LTC, 2004.
  • RAMOS, Marcus Vinícius Midena; JOSÉ NETO, João; VEGA, Ítalo Santiago. Linguagens formais: teoria, modelagem e implementação. Porto Alegre: Bookman, 2009.
  • PAPADIMITRIOU, Christos M. Computational complexity. New York: Addison Wesley Longman, 1994.