Disciplina Curricular
Introdução à Computabilidade e Complexidade ICC
Licenciatura Bolonha em Matemática Aplicada e Computação - LMAC 2006
Contextos
Grupo: LMAC 2006 > 1º Ciclo > Tronco Comum
Período:
Peso
7.5 (para cálculo da média)
Objectivos
Entender os limites do que é computável na teoria e na prática. Dominar os conceitos, técnicas e resultados fundamentais da teoria da computabilidade. Conhecer diversos modelos de computação e entender a sua equivalência. Conhecer as noções básicas da teoria da complexidade.
Programa
Parte I: Computação em Mathematica Funções computáveis, conjuntos decidíveis, conjuntos listáveis, problemas decidíveis e problemas semidecidíveis. Critérios de listabilidade. Teorema da projecção. Teorema de Post. Gödelizações. Resultados de robustez. Funções universais. Existência de conjuntos listáveis indecidíveis. Enumeração das funções computáveis. Propriedade s-m-n. Conjuntos universais. Enumeração dos conjuntos listáveis. Teoremas de Rice, Rice-Shapiro e da recursão. Existência de vírus. Teorema de Myhill-Shepherdson. Redutibilidade-m. Conjuntos completos-m, conjuntos produtivos e conjuntos criativos. Teorema de Myhill. Redutibilidade-T. Oráculos. Computabilidade relativa. Teorema de Friedberg-Muchnik. Hierarquia aritmética. Parte II: Modelos de computação abstractos Aplicações recursivas primitivas. Aplicações recursivas. Aplicação de Ackermann. Funções recursivas. Teorema da normalização de Kleene. Ábacos. Máquinas de Turing. Máquinas modulares. Funções e conjuntos Diofantinos. Postulado de Church-Turing. Parte III: Elementos de teoria da complexidade Medidas e classes de complexidade. Classes P, NP e PSPACE. Completude-NP. Teorema de Cook-Levin.
Metodologia de avaliação
Fichas (4 valores) + Exame final (16 valores).