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

Programa da Disciplina

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

Ementa

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

• Notas de aula divulgadas pelo professor Pablo Sampaio.
• Aulas Presenciais.

• Atividades semanais no Google Classroom.

• Extra: Videoaulas gravadas de semestre anteriores. Disponíveis no Youtube através do link: https://www.youtube.com/watch?v=x8DZUnBozik&list=PLIltuXQwfJd5ape9BY-PJcMzAD_Qf36Qn&index=1

Objetivos

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

Conteúdo

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

• 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

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