Disciplina

Á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

G. L. Nemhauser and L. A

1999

Wiley


Combinatorial Optimization, 2nd Edition

C. H. Papadimitriou and K. Steiglitz

1998

Dover