DCC 129/831 – Fundamentos de Teoria da Computação (2021-02)

Informações gerais

  • Informações sobre o Ensino Remoto Emergencial (ERE):
  • Informações gerais sobre o curso: tópicos, bibliografia, e métodos de avaliação (“syllabus”): [pdf]
  • Calendário de atividades: aulas, entregas de exercícios e realização de provas (última atualização em 2021-10-11): [pdf]
  • FAQ: Algumas dúvidas comuns sobre meus métodos de ensino e avaliação estão respondidas aqui.

Material da disciplina

ConteúdoSlides de aulaListas de exercícios
0.0 - Introdução [pdf][---]
0.1 - Terminologia, Técnicas de Demonstração, Enumerabilidade[pdf][pdf]
0.2 - Linguagens Formais e Problemas de Decisão[pdf][pdf]
1.1 - Autômatos Finitos e Não-determinismo[TBA][TBA]
1.2 - Expressões Regulares[TBA][TBA]
1.3 - Linguagens Não-regulares[TBA][TBA]
2 - Linguagens Livres-do-Contexto[TBA][TBA]
3 - A Tese de Church-Turing e Máquinas de Turing[TBA][TBA]
4 - Decidibilidade[TBA][TBA]
5 - Redutibilidade[TBA][TBA]

Links para vídeos das aulas no Youtube