Disciplina
Algoritmos Avançados
Área
Área Científica de Metodologia e Tecnologias da Programação > Algoritmia
Activa nos planos curriculares
MEIC-T 2021 > MEIC-T 2021 > 2º Ciclo > Área Principal > Agrupamentos > Bioinformática e Biologia Computacional > Algoritmos Avançados
MECD2019 > MECD2019 > 2º Ciclo > Opções > Algoritmos Avançados
MEIC-T 2015 > MEIC-T 2015 > 2º Ciclo > Agrupamentos > Bioinformática e Biologia Computacional > Algoritmos Avançados
MEIC-A 2021 > MEIC-A 2021 > 2º Ciclo > Area Principal > Agrupamentos > Tecnologias da Informação e Linguagem > Algoritmos Avançados
MEIC-A 2015 > MEIC-A 2015 > 2º Ciclo > Agrupamentos > Bioinformática e Biologia Computacional > Algoritmos Avançados
MEIC-A 2006 > MEIC-A 2006 > 2º Ciclo > Área de Especialização Complementar > Ciência da Computação > Algoritmos Avançados
DEASegInf2007 > DEASegInf2007 > 3º Ciclo > Engenharia Informática > Metodologia e Tecnologia da Programação > Algoritmos Avançados
MMA 2006 > MMA 2006 > 2º Ciclo > Perfis > Matematica da Computação > Metodologia e Tecnologia da Programação > Algoritmos Avançados
Nível
Projecto (40%) + Exame (60%)
Tipo
Não Estruturante
Regime
Semestral
Carga Horária
1º Semestre
3.0 h/semana
1.5 h/semana
147.0 h/semestre
Objectivos
Formação avançada em técnicas de desenvolvimento de algoritmos eficientes e aplicações. Algoritmos para a resolução de problemas computacionalmente difíceis (NP-Hard). Identificação de aplicações de problemas computationalmente dificeis. Métodos de procura para problemas NP-Hard. Algoritmos eficientes de aproximação e com escolhas aleatórias. Algoritmos eficientes para processamento online e em tempo real. Algoritmos paralelos e com acesso a memória externa.
Programa
Algoritmos de Aproximação para problemas NP-Hard. Métodos de procura completos para problemas NP-Hard: branch and bound; identificação de planos de corte; procura com retrocesso. Algoritmos gananciosos; programação dinâmica e algoritmos fracamente polinomiais. Métodos de procura local. Aplicações de Problemas NP-Hard. Algoritmos paralelos e com recurso memória externa. Algoritmos Online e em Tempo Real. Algoritmos com escolhas aleatórias. Algoritmos de aproximação para problemas polinomiais, e.g., algoritmos lineares para MSTs e algoritmos rápidos para cortes mínimos.
Metodologia de avaliação
Projecto (40%) + Exame (60%)
Pré-requisitos
Componente Laboratorial
Princípios Éticos
Componente de Programação e Computação
Componente de Competências Transversais
Bibliografia
Principal
Wolsey: Integer and Combinatorial Optimization
Combinatorial Optimization, 2nd Edition
C. H. Papadimitriou and K. Steiglitz