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
Dois testes e/ou exame.
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; 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.
Pré-requisitos
Componente Laboratorial
Princípios Éticos
Componente de Programação e Computação
Componente de Competências Transversais
Bibliografia
Principal
Secundária
Computability and complexity Theory