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 ou exame, complementado com componentes de avaliação contínua.
Tipo
Não Estruturante
Regime
Semestral
Carga Horária
1º Semestre
119.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 de Turing. Conjuntos NP-completos, PSPACE-completos e NL-completos. Conjuntos P-completos. Alternação. Classes de complexidade para a alternação. A hierarquia polinomial. Classes de complexidade não uniforme e circuitos booleanos. Máquinas de Turing probabilísticas. Classes PP, BPP, R e ZPP. 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
Testes ou exame, complementado com componentes de avaliação contínua.
Pré-requisitos
Apetência pelos fundamentos da computação, frequência de disciplinas na área de Algoritmos e Teoria da Computação.
Componente Laboratorial
Não aplicável.
Princípios Éticos
Todos os membros de um grupo são responsáveis pelo trabalho do grupo. Em qualquer avaliação, todo aluno deve divulgar honestamente qualquer ajuda recebida e fontes usadas. Numa avaliação oral, todo aluno deverá ser capaz de apresentar e responder a perguntas sobre toda a avaliação.
Componente de Programação e Computação
Não aplicável.
Componente de Competências Transversais
A UC permite o desenvolvimento de competências transversais em Pensamento Crítico, Criatividade e Estratégias de Resoluções de Problemas, nas aulas, em trabalho autónomo e nas várias componentes de avaliação. A percentagem de avaliação associada a estas competências deverá ser da ordem dos 15%.
Bibliografia
Principal
Computability and complexity Theory
Computabilidade, Inferência Indutiva e Complexidade,
José Félix Costa e Paula Gouveia
a ser submetido para publicação, 400 pp.