Disciplina
Algoritmos Avançados
Área
Área Científica de Metodologia e Tecnologias da Programação > Algoritmos
Activa nos planos curriculares
MEIC-T 2021 > MEIC-T 2021 > 2º Ciclo > Área Principal > Agrupamentos > Bioinformática e Biologia Computacional > Algoritmos Avançados
MECD2019 > MECD2019 > 2º Ciclo > Opções > Algoritmos Avançados
MEIC-T 2015 > MEIC-T 2015 > 2º Ciclo > Agrupamentos > Bioinformática e Biologia Computacional > Algoritmos Avançados
MEIC-A 2021 > MEIC-A 2021 > 2º Ciclo > Area Principal > Agrupamentos > Tecnologias da Informação e Linguagem > Algoritmos Avançados
MEIC-A 2015 > MEIC-A 2015 > 2º Ciclo > Agrupamentos > Bioinformática e Biologia Computacional > Algoritmos Avançados
MEIC-A 2006 > MEIC-A 2006 > 2º Ciclo > Área de Especialização Complementar > Ciência da Computação > Algoritmos Avançados
DEASegInf2007 > DEASegInf2007 > 3º Ciclo > Engenharia Informática > Metodologia e Tecnologia da Programação > Algoritmos Avançados
MMA 2006 > MMA 2006 > 2º Ciclo > Perfis > Matematica da Computação > Metodologia e Tecnologia da Programação > Algoritmos Avançados
Nível
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.
Tipo
Não Estruturante
Regime
Semestral
Carga Horária
1º Semestre
2.0 h/semana
1.5 h/semana
119.0 h/semestre
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.
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.
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.
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.
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.
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.
Bibliografia
Principal
Veli Mäkinen, Fabio Cunial, Djamal Belazzougui, and Alexandru I. Tomescu
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
Rajeev Motwani and Prabhakar Raghavan
Probability and Computing: Randomized Algorithms and Probabilistic Analysis
Michael Mitzenmacher and Eli Upfal
Combinatorial Optimization: Polyhedra and Efficiency
Combinatorial Optimization: Theory and Algorithms
Jure Leskovec, Anand Rajaraman, and Jeff Ullman