Disciplina Curricular

Algoritmos Avançados AAva

Mestrado Bolonha em Matemática e Aplicações - MMA 2006

Contextos

Grupo: MMA 2006 > 2º Ciclo > Perfis > Matematica da Computação > Metodologia e Tecnologia da Programação

Período:

Peso

7.5 (para cálculo da média)

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%.

Disciplinas Execução

2017/2018 - 2ºSemestre

2016/2017 - 2ºSemestre

2015/2016 - 2º Semestre

2014/2015 - 2º Semestre

2013/2014 - 2 Semestre

2012/2013 - 2 Semestre

2011/2012 - 2 Semestre