Conteúdo
Plano de Ensino: Computabilidade e Complexidade
Ementa da Disciplina
Conjuntos enumeráveis, provas por diagonalização, teoria das funções recursivas. Definições de computabilidade. Problemas decidíveis e problema da parada. Conceito de redutibilidade. Classes de complexidade de tempo e espaço.
Metodologia de Ensino
A disciplina adotará a metodologia Project-Based Learning (PBL), onde os alunos aprenderão ativamente através do desenvolvimento de projetos práticos e significativos. As aulas síncronas combinarão exposições teóricas com atividades práticas e discussões. Os encontros assíncronos serão utilizados para reforço do aprendizado, revisão e aprofundamento de tópicos, sem a introdução de novos conteúdos. Serão desenvolvidos dois trabalhos complementares (teóricos/práticos) ao longo do semestre, que não consumirão tempo dos encontros síncronos.
Objetivos de Aprendizagem
Ao final da disciplina, o aluno será capaz de:
- (a) Compreender os limites teóricos da computação e a natureza dos problemas computacionais.
- (b) Desenvolver raciocínio lógico-matemático para analisar a decidibilidade e a redutibilidade de problemas.
- (c) Aplicar conceitos de classes de complexidade para classificar a dificuldade de problemas.
- (d) Conceber argumentos formais para provar a incomputabilidade ou complexidade de problemas.
Encontros Detalhados
A seguir, apresento o detalhamento dos 24 encontros:
| Encontro | Tema | Objetivo (breve descrição) | Formato | Metodologia Inovadora | Recursos Utilizados | Local |
|---|---|---|---|---|---|---|
| 1 (Síncrono) | Introdução à Computabilidade e Complexidade | Apresentar a disciplina e a importância dos limites da computação. | Teórica | Discussão em Grupo | Slides, Whiteboard, Artigos históricos | Sala de Aula |
| 2 (Síncrono) | Conjuntos Enumeráveis e Não Enumeráveis | Compreender o conceito de enumeração e a infinitude de diferentes tamanhos. | Teórica | Estudo de Casos | Slides, Exemplos de Conjuntos | Sala de Aula |
| 3 (Síncrono) | Provas por Diagonalização | Aplicar a técnica de diagonalização para provar a não enumerabilidade. | Teórica/Prática | Resolução Colaborativa | Slides, Exercícios, Diagramas | Sala de Aula |
| 4 (Assíncrono) | Reforço: Conjuntos e Diagonalização | Revisar e aprofundar a compreensão de conjuntos enumeráveis e diagonalização. | Prática | Autoestudo Guiado | Videoaulas, Listas de Exercícios, Fórum online | Ambiente Virtual |
| 5 (Síncrono) | Funções Computáveis e Máquinas de Turing | Definir funções computáveis e introduzir o modelo de Máquina de Turing. | Teórica | Simulação Teórica | Slides, Esquemáticos de MT, Animações | Sala de Aula |
| 6 (Síncrono) | Tese de Church-Turing e Modelos Equivalentes | Entender a Tese de Church-Turing e a equivalência entre modelos de computação. | Teórica | Debate Guiado | Slides, Artigos sobre a Tese | Sala de Aula |
| 7 (Síncrono) | Linguagens Recursivas e Recursivamente Enumeráveis | Distinguir linguagens computáveis e parcialmente computáveis em Máquinas de Turing. | Teórica/Prática | Análise de Gramáticas | Slides, Exemplos de Linguagens, Provas | Sala de Aula |
| 8 (Assíncrono) | Reforço: Máquinas de Turing e Linguagens | Praticar com Máquinas de Turing e a classificação de linguagens. | Prática | Resolução de Problemas | Exercícios Resolvidos, Material Complementar | Ambiente Virtual |
| 9 (Síncrono) | O Problema da Parada (Halting Problem) | Compreender e provar a indecidibilidade do Problema da Parada. | Teórica | Estudo Dirigido | Slides, Prova Formal do Problema | Sala de Aula |
| 10 (Síncrono) | Problemas Decidíveis e Indecidíveis | Classificar problemas computacionais como decidíveis ou indecidíveis. | Teórica/Prática | Análise de Algoritmos | Slides, Exemplos de Problemas | Sala de Aula |
| 11 (Síncrono) | Revisão para G1 | Reforçar os conteúdos abordados até o momento para a prova. | Prática | Resolução de Questões | Exercícios de Fixação | Sala de Aula |
| 12 (Assíncrono) | Reforço: Preparação para G1 | Praticar com mais exercícios e revisar os tópicos mais importantes para a prova. | Prática | Simulados Online | Questões Objetivas, Material de Revisão | Ambiente Virtual |
| 13 (Síncrono) | Prova G1 | Avaliar o conhecimento adquirido nos primeiros encontros. | Avaliação | Prova Individual | Instrumento de Avaliação | Sala de Aula |
| 14 (Síncrono) | Redutibilidade e Completude | Entender o conceito de redutibilidade e problemas completos. | Teórica | Discussão Interativa | Slides, Exemplos de Reduções | Sala de Aula |
| 15 (Síncrono) | Introdução à Complexidade Computacional | Apresentar a complexidade de tempo e espaço, e sua importância prática. | Teórica | Brainstorming | Slides, Casos de Estudo de Algoritmos | Sala de Aula |
| 16 (Assíncrono) | Reforço: Redutibilidade e Complexidade | Revisar e aprofundar a compreensão sobre redutibilidade e complexidade. | Prática | Análise de Problemas | Datasets, Ferramentas de Análise de Algoritmos | Ambiente Virtual |
| 17 (Síncrono) | Classes de Complexidade de Tempo: P e NP | Definir e distinguir as classes de complexidade P e NP. | Teórica | Estudo de Casos | Slides, Exemplos de Problemas em P e NP | Sala de Aula |
| 18 (Síncrono) | Problemas NP-Completos | Identificar e analisar problemas NP-Completos e sua relevância. | Teórica/Prática | Análise de Algoritmos | Slides, Exemplos de NP-Completos | Sala de Aula |
| 19 (Síncrono) | Teorema de Cook-Levin | Compreender a prova da NP-completude do problema SAT. | Teórica | Análise de Demonstrações | Slides, Demonstração do Teorema | Sala de Aula |
| 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. | Prática | Desenvolvimento Guiado | Tutoriais, Artigos Científicos, Exemplos | Ambiente Virtual |
| 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). | Teórica/Prática | Estudo de Artigos | Artigos Científicos, Estudos de Caso, Fórum | Ambiente Virtual |
| 22 (Síncrono) | Revisão G2 | Consolidar todo o conteúdo da disciplina para a prova final. | Prática | Simulação de Prova | Exercícios de Fixação, Questões Dissertativas | Sala de Aula |
| 23 (Síncrono) | Prova G2 | Avaliar o conhecimento global adquirido na disciplina (todo o conteúdo). | Avaliação | Prova Individual | Instrumento de Avaliação | Sala de Aula |
| 24 (Síncrono) | Exame Final | Oportunidade para alunos que perderam a prova ou para exame final (todo o conteúdo). | Avaliação | Prova Individual | Instrumento de Avaliação | Sala de Aula |
Trabalhos Complementares (Não Utilizam Encontros)
- Trabalho Complementar 1: Análise de Computabilidade e Decidibilidade
- Objetivo: Escolher um problema computacional e formalmente provar sua decidibilidade ou indecidibilidade, utilizando os conceitos de Máquinas de Turing e redutibilidade.
- Entrega: Relatório técnico detalhado com a definição do problema, a prova formal e discussões sobre implicações.
- Período: Após o Encontro 10 e antes do Encontro 13.
- Trabalho Complementar 2: Análise de Complexidade de Problemas
- Objetivo: Selecionar um problema e investigar sua classificação dentro das classes de complexidade (P, NP, NP-Completo, etc.), apresentando argumentos e, se aplicável, reduzindo-o a um problema conhecido.
- Entrega: Relatório técnico com a análise da complexidade, justificativas teóricas e, se possível, uma breve implementação de um algoritmo para o problema.
- Período: Após o Encontro 18 e antes do Encontro 23.