Disciplina Curricular
Demonstrações, Computabilidade, Complexidade DCC
Mestrado Bolonha em Matemática - 2_MMat 2022/23
Contextos
Grupo: 2_MMat 2022/23 > 2º Ciclo > Parte Escolar > Opcionais > 2º Ano > 689_Opcionais Área CMat / 2º Ano
Período:
Grupo: 2_MMat 2022/23 > 2º Ciclo > Parte Escolar > Opcionais > 1º Ano > 688_Opcionais Área CMat / 1º Ano > 1º Semestre
Período:
Peso
6.0 (para cálculo da média)
Objectivos
O curso oferecerá uma introdução à teoria matemática da computação, com enfoque na compreensão da sua relação com as demonstrações matemáticas. Os objetivos do curso são três: 1. Explicar o que é um computador, por que e como os computadores foram inventados, promovendo no estudante a capacidade de pensar de forma computacional e algorítmica. 2. Introduzir os fundamentos da complexidade computacional: como classificar problemas matemáticos de acordo com a sua dificuldade de resolução? Por exemplo, em jogos e quebracabeças, em que sentido preciso podemos dizer que o xadrez é mais difícil do que o sudoku? Que o sudoku é mais difícil do que um puzzle de deslizamento de peças? Que um tal puzzle é mais difícil do que resolver uma equação linear?... 3. Compreender por que os computadores estão intimamente relacionados com as demonstrações matemáticas. Desenvolver a capacidade de refletir sobre as provas como um objeto de estudo: o que são, quais são as suas limitações e capacidades surpreendentes.
Programa
• A invenção do computador: as máquinas de Turing. • Implementação de vários algoritmos em máquinas de Turing. • Outros modelos de computação: máquinas de acesso aleatório, Baby Python, funções recursivas de GödelHerbrand. Provas de equivalência/simulação. • Máquinas de Turing universais e programas. A tese de Church-Turing. • Problemas insolúveis. O problema da paragem e muitos outros. • Lógica de primeira ordem e o primeiro teorema da incompletude de Gödel (em apenas uma semana!). • Problemas recursivamente enumeráveis e um problema que não é recursivamente enumerável. A hierarquia aritmética. • Complexidade computacional: medição de tempo e espaço, o problema P vs PSPACE. Teoremas da hierarquia. • Máquinas de Turing não determinísticas: o problema P vs NP. • O teorema de Levin-Cook. NP-completude de vários problemas. Decisão vs Pesquisa. A hierarquia polinomial. • De volta ao espaço: o teorema de Savitch. PSPACE-completude. L vs NL. • Algoritmos aleatorizados: P vs BPP e mais. • A complexidade das provas: provas interativas, MA, AM, etc., até IP = PSPACE.
Métodos de ensino e avaliação
Todas as semanas haverá uma leitura obrigatória e trabalhos de casa. No final do semestre, haverá um exame.