Disciplina Curricular

Algoritmos Avançados AAva

Mestrado Bolonha em Engenharia Informática e de Computadores - Alameda - MEIC-A 2021

Contextos

Grupo: MEIC-A 2021 > 2º Ciclo > Area Principal > Agrupamentos > Tecnologias da Informação e Linguagem

Período:

Grupo: MEIC-A 2021 > 2º Ciclo > Area Principal > Agrupamentos > Bioinformática e Biologia Computacional

Período:

Grupo: MEIC-A 2021 > 2º Ciclo > Area Principal > Agrupamentos > Algoritmos e Aplicações

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.

Componente de Competências Transversais

Não existindo uma componente explícita de Competências Transversais a desenvolver no âmbito desta UC, o trabalho prático, em grupo, levará ao desenvolvimento de Pensamento Crítico e Inovador, Competências Intrapessoais, e Competências Interpessoais.

Componente Laboratorial

Aplicação das técnicas discutidas nas aulas teóricas, e estudadas na sequência das mesmas, na resolução de problemas, nomeadamente propostos nos trabalhos práticos e na implementação dos algoritmos e estruturas de dados inerentes às soluções alcançadas.

Componente de Programação e Computação

No curso onde esta UC é oferecida estão asseguradas as componentes de Computação e Programação de acordo com o MEPP 2122. Esta UC contribui em particular com técnicas de implementação prática de algoritmos e estruturas de dados avançadas.

Princípios Éticos

Todos os membros de um grupo são responsáveis pelo trabalho do grupo. Em qualquer avaliação, todo aluno deve divulgar honestamente qualquer ajuda recebida e fontes usadas. Numa avaliação oral, todo aluno deverá ser capaz de apresentar e responder a perguntas sobre toda a avaliação.

Disciplinas Execução