Professor responsável

Monitor

  • Lucas Cavalcanti (lhcs)

Horário e sala

  • Quarta-feira 13h-15h (Sala D005)
  • Sexta-feira 13h-15h (Sala D005)

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.

A ser anunciado

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)

if689ec-l@cin.ufpe.br