Disciplina Curricular
Computabilidade e Complexidade CC
Mestrado Bolonha em Engenharia Informática e de Computadores - Alameda - MEIC-A 2015
Contextos
Grupo: MEIC-A 2015 > 2º Ciclo > Agrupamentos > Algoritmos e Programaçã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.