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; estudar problemas em aberto em complexidade computacional.

Programa

Computação com recursos limitados no espaço e no tempo. Relações estruturais entre classes de complexidade. Reduções com recursos limitados, de muitos para um (tempo polinomial, espaço logarítmico) e Turing. Conjuntos NP-completos, PSPACE-completos e NL-completos. A hierarquia (de tempo) polinomial. Classes de complexidade não uniforme e circuitos booleanos. Conjuntos P-completos. Máquinas de Turing probabilísticas. Classes PP, BPP, R e ZPP. Conjuntos PP-completos. Relativizações negativas e positivas. Isomorfismo e NP-completude: cilindros e conjuntos esparsos completos. Máquinas de Turing interativas. Jogos Artur contra Merlin e sistemas de prova.

Metodologia de avaliação

Dois testes e/ou exame.

Disciplinas Execução

2017/2018 - 1ºSemestre

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