Professor responsável

Monitores

  • Gabriela Freitas (gchf)
  • José Ricardo Figueirôa (jraf)

Horário e sala

  • Quarta-feira 15h-17h (Sala D002)
  • Sexta-feira 13h-15h (Sala D002)

Monitoria

  • Sexta-feira 12h-13h (Sala D002)

Ementa

  • PARTE I - Linguagens formais e autômatos:
    Autômatos finitos determinísticos (AFD) / Autômatos finitos não-determinísticos (AFN) / Linguagens regulares (proprieades e operações) / Expressões regulares (ER) / Equivalência AFD<=>AFN<=>ER / Linguagens não-regulares (Lema do bombeamento) / / Gramáticas Livres de Contexto (GLC) / Linguagens Livres de Contexto (proprieades e operações) / Ambiguidade de normalização de GLCs / Autõmatos com Pilha (AP) / Equivalência GLC<=>AP / Linguagens não-livres de contexto (Lema do bombeamento)
  • PARTE II - Teoria da Computabilidade:
    Máquinas de Turing (MT) / Variações das MT / Não-determinismo / Tese de Church-Turing / Linguagens recursivas e recursivamente enumeráveis / Decidibilidade / O Problema da Parada / Teorema de Rice / Redutibilidade.
  • PARTE III - Teoria da Complexidade:
    Complexidade de Tempo / Classes de complexidade / Redução polinomial / P vs. NP / NP-completude / Teorema de Cook-Levin / Complexidade de Espaço / Teorema de Savitch / PSPACE-completude.

Bibliografia

Básica

  1. Michael Sipser. Introdução à Teoria da Computação, Cengage Learning, 2007.

Suplementar

  1. John E. Hopcroft, Rajeev Motwani & Jeffrey D. Ullman. Introdução à Teoria dos Autômatos, Linguagens e Computação, Ed. Campus, 2002
  2. Harry R. Lewis, Christos Papadimitriou. Elements of the Theory of Computation (2nd Ed.), Prentice-Hall, 1998
  3. Dexter Kozen. Automata and Computability, Springer, 1997
  4. Christos Papadimitriou. Computational Complexity, Addison Wesley, 1994

Avaliação

Três unidades, cada unidade correspondendo a uma parte da ementa. A média do curso (MC) será calculada como

MC = (M1+M2+M3) / 3

A média de cada unidade (M1, M2, M3) será dada por uma prova escrita obrigatória, com nota de 0 a 10, mais atividades extras de monitoria que podem somar até 1 (um) ponto extra à média da unidade.

Segunda chamada

  • Sobre todo o conteúdo da disciplina
  • Mediante solicitação formal junto à Secretaria de graduação

Frequência

  • A frequência a pelo menos 75% das aulas e avaliações parciais é obrigatória, respeitados o turno e o horário previstos para a disciplina. Será realizada chamada.
  • A frequência às atividades de monitoria fora do horário de aula é recomendada mas não é obrigatória.

Exercícios selecionados Sipser 2a.ed.

Capítulo Exercícios Problemas
Cap 1 6,7,11-16,21,29-30 31-32,36,39-41,46-47,53,60-61
Cap 2 2, 4, 6, 7, 9, 13, 15-17 18, 20, 26, 30, 31, 35, 43, 44
Cap 3 3, 5-7 9-13,15-17,22
Cap 4 1-8 9-13, 15-19, 21, 23, 28
Cap 5 1-8 9-15, 17, 20, 22-25, 28-30, 35
Cap 7 4, 7, 8 14, 15, 17, 21, 22, 27, 32, 36, 44, 45
Cap 8 1, 4, 6 8, 11, 13, 16

Inscreva-se já no canal oficial de comunicação entre alunos, professores e monitores da disciplina (apenas para alunos matriculados com e-mail do CIn)

if689-l@cin.ufpe.br