Disciplina

Área

Área Científica de Metodologia e Tecnologia da Programação > Algoritmos

Activa nos planos curriculares

MEIC-T 2021 > Meic-T 2021 > 2º Ciclo > 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

Exame e componente prática. O exame contribui com 50% para a nota final (FM) e o aluno tem de obter pelo menos 7.5 valores num dos exames. A componente prática contribui 50% para a nota final (FM). FM = 0.5 * max(E1, E2) + 0.5 * P Aprovado se max(E1, E2) >= 7.5 e FM >= 9.5.

Tipo

Não Estruturante

Regime

Semestral

Carga Horária

1º Semestre

2.0 h/semana

1.5 h/semana

119.0 h/semestre

Objectivos

Os algoritmos e as estruturas de dados estão na base de qualquer aplicação ou sistema informático, tendo vindo a ganhar cada vez maior relevância com novos desafios no que respeita ao volume de dados a processar, aos requisitos de eficiência e de processamento em tempo real, e à complexidade dos problemas com que nos deparamos hoje em dia. O objectivo desta unidade curricular é portanto a formação avançada em técnicas de desenvolvimento e análise de algoritmos com particular foco em estruturas de dados avançadas para indexação, algoritmos randomizados, algoritmos de aproximação, algoritmos para processamento online e em tempo real, e estruturas de dados e algoritmos para processamento de grandes volumes de dados. Esta unidade curricular seguirá uma abordagem baseda na resolução de problemas em que as técnicas de desenho e análise das estruturas de dados e algoritmos serão motivadas e exploradas de forma intuitiva e construtiva, incluindo as técnicas de implementação relevantes.

Programa

Desenho e análise de estruturas de dados avançadas, como B-trees, splay-trees e árvores cartesianas. Filas com prioridade baseadas em amontoados binomiais, de Fibonacci, e relaxados. Análise amortizada. Estruturas de dados sucintas/compactas. Algoritmos e estruturas de dados para processamento eficiente de strings, como árvores e arrays de sufixos. Algoritmos e estruturas de dados para processamento eficiente de árvores e grafos. Optimização combinatória. Técnicas probabilísticas e de teoria de jogos aplicadas à análise e desenho de algoritmos e estruturas de dados. Algoritmos de aproximação. Algoritmos com escolhas aleatórias. Algoritmos online e sobre streams. Algoritmos e estruturas de dados para processamento de grandes volumes de dados. Técnicas de implementação, utilização prática, e avaliação experimental.

Metodologia de avaliação

Exame e componente prática. O exame contribui com 50% para a nota final (FM) e o aluno tem de obter pelo menos 7.5 valores num dos exames. A componente prática contribui 50% para a nota final (FM). FM = 0.5 * max(E1, E2) + 0.5 * P Aprovado se max(E1, E2) >= 7.5 e FM >= 9.5.

Bibliografia

Principal

Genome-Scale Algorithm Design

Veli Mäkinen, Fabio Cunial, Djamal Belazzougui, and Alexandru I. Tomescu

2015

Cambridge University


Introduction to Algorithms

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

2009

MIT Press


Randomized Algorithms

Rajeev Motwani and Prabhakar Raghavan

2000

Cambridge University Press


Probability and Computing: Randomized Algorithms and Probabilistic Analysis

Michael Mitzenmacher and Eli Upfal

2005

Cambridge University Press


Combinatorial Optimization: Polyhedra and Efficiency

Alexander Schrijver

2004

Springer


Combinatorial Optimization: Theory and Algorithms

Bernhard Korte and Jens Vygen

2008

Springer


Mining of Massive Datasets

Jure Leskovec, Anand Rajaraman, and Jeff Ullman

2019

Cambridge University Press


Art of Computer Programming

Donald E. Knut

1998

Addison-Wesley