Computabilidade e Complexidade (2025/2)
Informações do Curso
| Professor | Curso |
|---|---|
| Márcio Nicolau | Segunda-feira |
| 4 de Agosto - 1 de Dezembro, 2025 | LMI 1 |
| marcio.nicolau@atitus.edu.br | 19:10 - 22:40 |
Descrição do curso
Este curso explora os limites e a natureza fundamental da computação. Você vai mergulhar em conceitos essenciais como conjuntos enumeráveis, provas por diagonalização e a teoria das funções recursivas para entender o que pode e o que não pode ser computado.
O curso te desafiará a desenvolver um raciocínio lógico-matemático afiado para analisar a decidibilidade e a redutibilidade de problemas. Você aprenderá a aplicar os conceitos de classes de complexidade, como P, NP e PSPACE, para classificar a dificuldade inerente de diferentes problemas computacionais.
A disciplina busca que você seja capaz de conceber argumentos formais e rigorosos para provar a incomputabilidade ou a complexidade de um problema. Ao final, você terá uma compreensão sólida sobre as fronteiras teóricas da computação, uma base de conhecimento crucial para qualquer área da ciência da computação.
Pré-requisitos
Alunos com familiaridade sobre estrutura de dados e algoritmos.
Objetivos de Aprendizado
Ao final da disciplina, o aluno será capaz de:
- Compreender os limites teóricos da computação e a natureza dos problemas computacionais.
- Desenvolver raciocínio lógico-matemático para analisar a decidibilidade e a redutibilidade de problemas.
- Aplicar conceitos de classes de complexidade para classificar a dificuldade de problemas.
- Conceber argumentos formais para provar a incomputabilidade ou complexidade de problemas.
Conteúdo Programático
- Conjuntos Enumeráveis e Não Enumeráveis
- Provas por Diagonalização
- Teoria das Funções Recursivas
- Definições de Computabilidade (Máquinas de Turing)
- Problema da Parada (Halting Problem)
- Problemas Decidíveis e Indecidíveis
- Conceito de Redutibilidade e Completude
- Classes de Complexidade de Tempo (P, NP, NP-Completo)
- Classes de Complexidade de Espaço (PSPACE, NPSPACE)
Textos e materiais
Em breve!
Software
Em breve!
Avaliações
Em breve!
Trabalhos
Em breve!
Aulas
Em breve!