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).

Disciplinas Execução

2016/2017 - 1ºSemestre

2015/2016 - 1º Semestre

2014/2015 - 1º Semestre

2013/2014 - 1 Semestre

2012/2013 - 1 Semestre

2011/2012 - 1 Semestre

2010/2011 - 1 Semestre

2009/2010 - 1 Semestre

2008/2009 - 1 Semestre

2007/2008 - 2 Semestre

2006/2007 - 2 Semestre