Disciplina
Algoritmos Avançados
Área
Área Científica de Metodologia e Tecnologias da Programação > Algoritmos
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
Método de avaliação: exame 60% + projectos 40%.
Tipo
Não Estruturante
Regime
Semestral
Carga Horária
1º Semestre
3.0 h/semana
1.5 h/semana
147.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 e compressão, algoritmos randomizados, algoritmos de aproximação, algoritmos para processamento online e em tempo real, e estruturas de dados e algoritmos distribuídos e com acesso a memória externa. 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.
Programa
Estruturas de dados avançadas. B-trees. Amontoados binomiais, de Fibonacci, e relaxados. Algoritmos de Aproximação para problemas NP-hard. Técnicas probabilísticas, caminhos aleatórios, e teoria de jogos. Algoritmos com escolhas aleatórias. Algoritmos online e para processamento em tempo real. Estruturas de dados e algoritmos distribuídos e com recurso memória externa. Algoritmos para strings, árvores de sufixos. Algoritmos em árvores, LCA. Algoritmos em grafos, corte mínimo, MST em tempo linear, partição de grafos, e contagem de subgrafos. Análise amortizada. Contagem aproximada.
Metodologia de avaliação
Método de avaliação: exame 60% + projectos 40%.
Pré-requisitos
Componente Laboratorial
Princípios Éticos
Componente de Programação e Computação
Componente de Competências Transversais
Bibliografia
Principal
Algorithms on Strings, Trees, and Sequences
Rajeev Motwani and Prabhakar Raghavan
Secundária
H. Papadimitriou and K. Steiglitz
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
Anand Rajaraman, Jeff Ullman, and Jure Leskovec
Probability and Computing: Randomized Algorithms and Probabilistic Analysis
Michael Mitzenmacher and Eli Upfal