Fundamentos da Teoria da Computação
Primeiro semestre/2004

• Plano de Curso: PDF, PostScript. (Para leitura de PostScript, pegue o software apropriado.)
• As seguintes páginas podem auxiliar no aprendizado de certos conceitos:
  • Language Emulator
  • JFLAP.
  • Deus ex Machina
  • Turing's World
  • Webworks Laboratory
  • Ganimal
  • The Java Computability Toolkit
• Apostila: PS.
• Transparências das seções 1.1 a 1.9: PDF gzipado; PS gzipado.
• Veja uma demonstração poética da indecidibilidade do problema da parada (em PS).
• Exercícios:
  • Primeira lista. Entrega: 22/04/2004.
  • Segunda lista. Entrega: 20/05/2004.
  • Terceira lista. Entrega: 01/07/2004.
  • Quarta lista. Entrega: 15/07/2004.
• Trabalhos Extra:
  • Trabalho 1 valendo 3 pontos extra. Entrega: 03/06/2004.
  • Trabalho 2 valendo 4 pontos extra. Entrega: 09/07/2004. Adiada para 12/07.
• Provas:
  • Primeira prova:
    • Data: 22/04/2004.
    • Assunto: até Autômatos Finitos Determinísticos (seções 1.10, 1.11, 1.12, 2.1 e 2.2).
    • Veja a solução da prova.
  • Segunda prova:
    • Data: 20/05/2004. Adiada para 25/05.
    • Assunto: Máquinas de estado-finito (capítulo 2).
  • Terceira prova:
    • Data: 29/06/2004. Adiada para 01/07.
    • Assunto: Autômatos com pilha (capítulo 3).
  • Quarta prova:
    • Data: 13/07/2004. Adiada para 15/07.
    • Assunto: Máquinas de Turing (capítulo 4).
• Veja suas notas.