Computabilidade e Complexidade (2025/2)

Carga horária: 80 horas

Descrição:

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.

Objetivos de Aprendizagem:

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.

Pré-requisitos:

Alunos com familiaridade sobre estrutura de dados e algoritmos.