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)
Pré-requisitos
Introdução aos Algoritmos e Estruturas de Dados, e Análise e Síntese de Algoritmos, da LEIC, ou UCs com programas semelhantes. Familiaridade com a linguagem de programação C.
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.