Disciplina Curricular

Algoritmos Avançados AAva

Mestrado Bolonha em Engenharia Informática e de Computadores - Taguspark - MEIC-T 2021

Contextos

Grupo: MEIC-T 2021 > 2º Ciclo > Área Principal > Agrupamentos > Bioinformática e Biologia Computacional

Período:

Grupo: MEIC-T 2021 > 2º Ciclo > Área Principal > Agrupamentos > Algoritmos e Aplicações

Período:

Grupo: MEIC-T 2021 > 2º Ciclo > Área Principal > Agrupamentos > Tecnologias da Informação e Linguagem

Período:

Peso

6.0 (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, 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.

Disciplinas Execução