Disciplina Curricular
Computabilidade e Complexidade CC
Curso de Especialização em Segurança de Informação e Direito no Ciberespaço - Segurança de Informação e Direito no Ciberespaço
Contextos
Grupo: Segurança de Informação e Direito no Ciberespaço > 3ºciclo > Especializaçã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
Modelos de computação. Computabilidade. Computação com recursos limitados no espaço e no tempo. Postulados de Church-Turing e invariância. Classes de complexidade notáveis. Teorias de redução em tempo e espaço limitados. Conjuntos P-completos, NP-completos e PSPACE-completos. Aplicações à Criptografia. Circuitos booleanos. Classes probabilísticas. Diagonalização uniforme. A hierarquia polinomial. Relativização de relações estruturais entre classes de complexidade.
Metodologia de avaliação
Teste + Exame Final.