Disciplina Curricular
Algoritmos Avançados AAva
Mestrado Bolonha em Engenharia Informática e de Computadores - Alameda - MEIC-A 2006
Contextos
Grupo: MEIC-A 2006 > 2º Ciclo > Área de Especialização Complementar > Ciência da Computação
Período:
Grupo: MEIC-A 2006 > 2º Ciclo > Área de Especialização Principal > Ciência da Computaçã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%.