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

• Plano de Curso: HTML, PostScript. (Para leitura de PostScript, pegue o software apropriado.)
• As seguintes páginas podem auxiliar no aprendizado de certos conceitos:
  • JFLAP.
  • Deus ex Machina
  • Turing's World
  • Webworks Laboratory
  • Ganimal
  • The Java Computability Toolkit
• Apostila (em PostScript): (não mais disponivel)
  • Capítulo 1: Conceitos Preliminares
  • Capítulo 2: Máquinas de Estado-Finito
  • Capítulo 3: Autômatos com Pilha
  • Capítulo 4: Máquinas de Turing
  • Capítulo 5: Decidibilidade
  • Capítulo 6: Soluções de Exercícios Selecionados
• Veja uma demonstração poética da indecidibilidade do problema da parada (em PS).
• Trabalhos práticos (em PostScript):
  • Primeiro trabalho. Data de entrega: 29/05/2003. Adiado para 02/06/2003.
    Veja a solução do monitor!
  • Segundo trabalho. Data de entrega: 02/07/2003.
  • Terceiro trabalho. Data de entrega: 30/07/2003.
  • Quarto trabalho. Data de entrega: 18/07/2003.
• Provas:
  • Primeira prova:
    • Data: 03/06/2003.
    • Assunto: até Autômatos Finitos Determinísticos (seções 1.10, 1.11, 1.12, 2.1 e 2.2).
  • Segunda prova:
    • Data: 03/07/2003.
    • Assunto: Máquinas de Estado-Finito (capítulo 2).
  • Terceira prova:
    • Data: 31/07/2003.
    • Assunto: Autômatos com Pilha (capítulo 3).
  • Quarta prova:
    • Data: 14/08/2003.
    • Assunto: Máquinas de Turing (capítulo 4).
  • Quarta prova/Suplementar:
    • Data: 19/08/2003.
    • Assunto: Máquinas de Turing (capítulo 4).
• Veja suas notas. Notas de exame especial.