Disciplina Curricular

Computabilidade e Complexidade CC

Mestrado Bolonha em Matemática e Aplicações - MMA 2006

Contextos

Grupo: MMA 2006 > 2º Ciclo > Perfis > Matematica da Computação > Lógica e Computação

Período:

Peso

7.5 (para cálculo da média)

Objectivos

Caracterizar classes computacionais, identificar conjuntos completos, distinguir complexidade uniforme de não uniforme e executar reduções.

Programa

Computação com recursos limitados no espaço e no tempo. Classes de complexidade notáveis. Problemas notáveis em complexidade estrutural. Conjuntos NP-completos e PSPACE-completos. Teorias de redução em tempo polinomial: redução de muitos para um e redução segundo Turing. Classes de complexidade não uniforme: teorias de conselhos polinomiais e de conselhos logarítmicos. Circuitos booleanos. Máquinas de Turing probabilísticas. Classes probabilísticas centrais: PP, BPP e ZPP. A hierarquia (de tempo) polinomial: definição, caracterização e consequências. Relação da hierarquia polinomial com classes probabilísticas. Relativização de relações estruturais entre classes centrais de complexidade. Relativizações negativas. Relativizações positivas.

Metodologia de avaliação

Dois testes e/ou exame.

Disciplinas Execução

2016/2017 - 1ºSemestre

2015/2016 - 1º Semestre

2014/2015 - 1º Semestre

2013/2014 - 1 Semestre

2012/2013 - 2 Semestre

2011/2012 - 2 Semestre

2010/2011 - 2 Semestre

2009/2010 - 2 Semestre

2008/2009 - 2 Semestre

2007/2008 - 2 Semestre

2007/2008 - 1 Semestre