Disciplina Curricular
Computabilidade e Complexidade CC
Mestrado Bolonha em Engenharia Informática e de Computadores - Alameda - MEIC-A 2021
Contextos
Grupo: MEIC-A 2021 > 2º Ciclo > Area Principal > Agrupamentos > Algoritmos e Aplicações
Período:
Peso
6.0 (para cálculo da média)
Pré-requisitos
Apetência pelos fundamentos da computação, frequência de disciplinas na área de Algoritmos e Teoria da Computação.
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.
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%.
Componente Laboratorial
Não aplicável.
Componente de Programação e Computação
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.