DCC 129 – Fundamentos de Teoria da Computação (2026/1)

Informações gerais

  • Local e hora das aulas:

    • Turma TN: Segundas e quartas, 14:55–16:35, em sala a ser definida.
    • Turma TZ: Segundas e quartas, 17:00–18:40, em sala a ser definida.

  • 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: (atualizado em 2026-Fev-27): [pdf]

  • FAQ: Algumas dúvidas comuns sobre meus métodos de ensino e de avaliação estão respondidas aqui.

Material da disciplina

ConteúdoSlides de aulaListas de exercícios
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[pdf][pdf]
1.2 - Expressões Regulares[pdf][pdf]
1.3 - Linguagens Não-regulares[—][—]
2 - Linguagens Livres-do-Contexto[—][—]
3 - A Tese de Church-Turing e Máquinas de Turing[—][—]
4 - Decidibilidade[—][—]
5 - Redutibilidade[—][—]

Playlist do YouTube, gravada durante a pandemia em 2021/2.