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
Testes (3) ou exame final.
Tipo
Não Estruturante
Regime
Semestral
Carga Horária
1º Semestre
3.0 h/semana
1.5 h/semana
105.0 h/semestre
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.
Metodologia de avaliação
Testes (3) ou exame final.
Pré-requisitos
Componente Laboratorial
Princípios Éticos
Componente de Programação e Computação
Componente de Competências Transversais
Bibliografia
Principal
J. Balcázar, J. Díaz and J. Gabarró
Springer-Verlag, (second revised edition)
Secundária
Circuit Complexity and Neural Networks