| Encontro | Data | Quiz | Aula | Trabalho | Leitura |
|---|---|---|---|---|---|
| 1 | 04/08/2025 | Introdução à Computabilidade e Complexidade Apresentar a disciplina e a importância dos limites da computação. |
|||
| 2 | 11/08/2025 | Conjuntos Enumeráveis e Não Enumeráveis Compreender o conceito de enumeração e a infinitude de diferentes tamanhos. |
|||
| 3 | 18/08/2025 | Provas por Diagonalização Aplicar a técnica de diagonalização para provar a não enumerabilidade |
|||
| 4 | (Assíncrono) | Reforço: Conjuntos e Diagonalização Revisar e aprofundar a compreensão de conjuntos enumeráveis e diagonalização. |
|||
| 5 | 25/08/2025 | Funções Computáveis e Máquinas de Turing Definir funções computáveis e introduzir o modelo de Máquina de Turing. |
|||
| 6 | 01/09/2025 | Tese de Church-Turing e Modelos Equivalentes Entender a Tese de Church-Turing e a equivalência entre modelos de computação. |
|||
| 7 | 08/09/2025 | Linguagens Recursivas e Recursivamente Enumeráveis Distinguir linguagens computáveis e parcialmente computáveis em Máquinas de Turing. |
|||
| 8 | (Assíncrono) | Reforço: Máquinas de Turing e Linguagens Praticar com Máquinas de Turing e a classificação de linguagens. |
|||
| 9 | 15/09/2025 | O Problema da Parada (Halting Problem) Compreender e provar a indecidibilidade do Problema da Parada. |
|||
| 10 | 22/09/2025 | Problemas Decidíveis e Indecidíveis Classificar problemas computacionais como decidíveis ou indecidíveis. |
|||
| 11 | 29/09/2025 | Revisão para G1 Reforçar os conteúdos abordados até o momento para a prova. |
|||
| 12 | (Assíncrono) | Reforço: Preparação para G1 Praticar com mais exercícios e revisar os tópicos mais importantes para a prova. |
|||
| 13 | 06/10/2025 | Prova G1 Avaliar o conhecimento adquirido nos primeiros encontros. |
|||
| 14 | 13/10/2025 | Redutibilidade e Completude Entender o conceito de redutibilidade e problemas completos. |
|||
| 15 | 20/10/2025 | Introdução à Complexidade Computacional Apresentar a complexidade de tempo e espaço, e sua importância prática. |
|||
| 16 | (Assíncrono) | Reforço: Redutibilidade e Complexidade Revisar e aprofundar a compreensão sobre redutibilidade e complexidade. |
|||
| 17 | 27/10/2025 | Classes de Complexidade de Tempo: P e NP Definir e distinguir as classes de complexidade P e NP. |
|||
| 18 | 03/11/2025 | Problemas NP-Completos Identificar e analisar problemas NP-Completos e sua relevância. |
|||
| 19 | 10/11/2025 | Teorema de Cook-Levin Compreender a prova da NP-completude do problema SAT. |
|||
| 20 | (Assíncrono) | Reforço: P, NP e NP-Completude Praticar a classificação de problemas em P, NP e a identificação de NP-Completos. |
|||
| 21 | (Assíncrono) | Reforço: Classes de Complexidade Avançadas Explorar classes de complexidade além de P e NP (ex: PSPACE, EXPTIME). Classes de Complexidade de Espaço (PSPACE, NPSPACE). |
|||
| 22 | 17/11/2025 | Revisão G2 Consolidar todo o conteúdo da disciplina para a prova final. |
|||
| 23 | 24/11/2025 | Prova G2 Avaliar o conhecimento global adquirido na disciplina (todo o conteúdo). |
|||
| 24 | 01/12/2025 | Exame Final Exame final (todo o conteúdo). |