Disciplina
Computabilidade e Complexidade
Área
Área Científica de Lógica e Computação > Lógica e Computação
Activa nos planos curriculares
MEIC-T 2021 > MEIC-T 2021 > 2º Ciclo > Área Principal > Agrupamentos > Algoritmos e Aplicações > Computabilidade e Complexidade
MEIC-T 2018 > MEIC-T 2018 > 2º Ciclo > Agrupamentos > Algoritmos e Aplicações > Computabilidade e Complexidade
MMAC 2021 > MMAC 2021 > 2º Ciclo > Área Principal > Áreas de Especialização > Área de Especialização em Lógica e Computação > Área Científica de Lógica e Computação > Obrigatórias > Computabilidade e Complexidade
MECD2019 > MECD2019 > 2º Ciclo > Opções > Computabilidade e Complexidade
MEIC-T 2015 > MEIC-T 2015 > 2º Ciclo > Agrupamentos > Algoritmos e Programação > Computabilidade e Complexidade
MEIC-A 2021 > MEIC-A 2021 > 2º Ciclo > Area Principal > Agrupamentos > Algoritmos e Aplicações > Computabilidade e Complexidade
MEIC-A 2015 > MEIC-A 2015 > 2º Ciclo > Agrupamentos > Algoritmos e Programação > Computabilidade e Complexidade
MSIDC2014 > MSIDC2014 > 2º Ciclo > Opções > Computabilidade e Complexidade
Segurança de Informação e Direito no Ciberespaço > Segurança de Informação e Direito no Ciberespaço > 3ºciclo > Especialização > Computabilidade e Complexidade
DEAEngCmp2007 > DEAEngCmp2007 > 3º Ciclo > Opcionais > Computabilidade e Complexidade
DEASegInf2007 > DEASegInf2007 > 3º Ciclo > Matemática > Lógica e Computação > Computabilidade e Complexidade
MMA 2006 > MMA 2006 > 2º Ciclo > Perfis > Matematica da Computação > Lógica e Computação > Computabilidade e Complexidade
MEIC-A 2006 > MEIC-A 2006 > 2º Ciclo > Área de Especialização Complementar > Ciência da Computação > Computabilidade e Complexidade
Nível
Teste + Exame Final.
Tipo
Não Estruturante
Regime
Semestral
Carga Horária
1º Semestre
4.0 h/semana
154.0 h/semestre
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.