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

• Disciplina ofertada para:
  • Ciência da Computação (Turma A)
  • Matemática Computacional (Turma M)
  • Engenharia Elétrica (Turma G)
• Plano de Curso: HTML, PostScript. (Para leitura de PostScript, pegue o software apropriado.)
• 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
• A página da profa. Susan H. Rodger contém referências para ferramentas que podem ser utilizadas para o estudo de alguns conceitos.
• Veja uma demonstração poética da indecidibilidade do problema da parada (em PS).
• Listas de exercícios (em PostScript):
  • Primeira Lista. Entrega: Turmas M e G: 8/7; Turma A: 9/7.
  • Segunda Lista. Entrega: Turmas M e G: 5/8; Turma A: 6/8.
  • Terceira Lista. Entrega: Turmas M e G: 2/9; Turma A: 3/9.
  • Quarta Lista. Entrega: Turmas M e G: 23/9; Turma A: 24/9.
• Trabalho Extra valendo 3 pontos.
• Provas:
  • Primeira Prova:
    • Data provável: Turmas M e G: 10/7; Turma A: 11/7.
    • Assunto: até Autômatos Finitos Determinísticos.
    • Veja a solução da prova das turmas M e G.
    • Veja a solução da prova da turma A.
  • Segunda Prova (turmas M e G, turma A):
    • Data provável: Turmas M e G: 07/8; Turma A: 08/8.
    • Assunto: todo o capítulo sobre Máquinas de Estado-Finito.
  • Terceira Prova (turmas M e G, turma A):
    • Data provável: Turmas M e G: 04/9; Turma A: 05/9.
    • Assunto: todo o capítulo sobre Autômatos com Pilha.
  • Quarta Prova (turmas M e G, turma A):
    • Data provável: Turmas M e G: 23/9; Turma A: 24/9.
    • Assunto: todo o capítulo sobre Máquinas de Turing.
• Confira suas notas: Turmas M e G e Turma A.