DC-UFRPE/Licenciatura Plena em 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
Carga-horária semanal: 4 horas (teóricas: 4; práticas: 0; EAD*: 0)
Pre-requisitos: MATEMÁTICA DISCRETA I e MATEMÁTICA DISCRETA II
Co-requisitos: Nenhum
Horários: Segunda-Feira: 20:10 as 21:50 e Quinta-Feira: 18:30 as 20:10

Ementa

Propriedades e operações com linguagens. Expressões regulares e gramáticas. Modelos clássicos 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, NP-Completo.

Prática como componente curricular

Não possui.

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

Método Avaliativo

1VA

• Prova escrita (70% da nota da 1VA) + Listas de Exercícios Semanais (30% da nota da 1VA).

2VA

• Prova escrita (70% da nota da 2VA) + Listas de Exercícios Semanais (30% da nota da 2VA).

3VA

• Prova escrita.

FINAL

• Prova escrita.

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 Programático

• 1. Conceitos básicos
  • 1.1 Representando informações com cadeias
  • 1.2 Alfabeto, cadeias e linguagens
  • 1.3 Linguagens x problemas de decisão
• 2. Linguagens Regulares
  • 2.1 Autômatos Determinísticos (AFDs)
  • 2.2 Autômatos Não-determinísticos (AFNs)
  • 2.3 Equivalência entre AFDs e AFNs
  • 2.4 Expressões regulares (ERs)
  • 2.5 Equivalência entre ERs e AFNs
  • 2.6 Lema do bombeamento
• 3. Linguagens Livres de Contexto
  • 3.1 Gramáticas Livres de Contexto (GLC)
  • 3.2 Autômatos de pilha (AP)
  • 3.3 Equivalência entre GLCs e APs
• 4. Linguagens Sensíveis a Contexto
  • 4.1 Autômatos Linearmente Limitados (ALLs)
• 5. Máquinas de Turing e Decidibilidade
  • 5.1 Definição de Máquinas de Turing (MTs)
  • 5.2 Variantes das MTs equivalentes
  • 5.3 Tese de Church-Turing
  • 5.4 Problemas decidíveis
  • 5.5 Máquinas de Turing universais
  • 5.6 Problema da parada em MTs
  • 5.7 Outros problemas indecidíveis
• 6. Complexidade de Tempo
  • 6.1 Avaliando tempo de execução de MTs
  • 6.2 Classes P e NP 6.2 Problemas NP-Completos
  • 6.3 Problema P =? NP
  • 6.4 Relacionamentos entre as classes

Links úteis:

• JFLAP para simulação de autômatos
• Exemplo de lista de exercícios
• Notas de Aulas do Professor Pablo Sampaio

Vídeos Complementares

• Math's Fundamental Flaw, disponível no Youtube.

Bibliografia

Bibliografia básica:

1. LOPES, Anita; GARCIA, Guto. Introdução à programação: 500 algoritmos resolvidos. Rio de Janeiro: Campus, 2002. 469p.
2. Ziviani, Nivio. Projeto de Algoritmos. Editora Nova Fronteira, 2007.
3. Sebesta, Robert W. Conceitos de Linguagens de Programação. Bookman, 2005.
4. MENEZES, Nilo Ney Coutinho. Introdução à programação com Python: algoritmos e lógica de programação para iniciantes. 2.ed. rev. ampl. São Paulo: Novatec Editora, 2014. 328 p.
5. SIPSER, M. Introdução a Teoria da Computação. 2a Edição Americana. Thomson, 2007.
6. HOPCROFT, J. E.; MOTWANI, R.; e ULLMAN, J. D. Introdução à Teoria de Autômatos, Linguagens e Computação. Tradução da 2a Edição Americana. Editora Campus, 2002.
7. LEWIS, Harry R; PAPADIMITRIOU, Christos H. Elementos de teoria da computação. 2. ed. Porto Alegre: Bookman, 2000

Bibliografia Complementar:

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