Estruturas de Dados e Algoritmos Avançados
Áreas Científicas |
Classificação |
Área Científica |
OFICIAL |
Programação |
Ocorrência: 2022/2023 - 2S ![Requerida a integração com o Moodle Ícone do Moodle](/feup/pt/imagens/MoodleIcon)
Ciclos de Estudo/Cursos
Sigla |
Nº de Estudantes |
Plano de Estudos |
Anos Curriculares |
Créditos UCN |
Créditos ECTS |
Horas de Contacto |
Horas Totais |
M.EIC |
26 |
Plano de estudos oficial |
1 |
- |
6 |
39 |
162 |
Língua de trabalho
Português - Suitable for English-speaking students
Objetivos
Esta unidade curricular (UC) tem por objetivo complementar e aprofundar conhecimentos previamente assimilados em UCs de 1º ciclo sobre conceção e análise de algoritmos e estruturas de dados, cobrindo um espectro adicional de técnicas de conceção e análise de algoritmos e estruturas de dados mais avançadas, apropriadas a problemas mais complexos.
Resultados de aprendizagem e competências
No final da unidade curricular, os estudantes devem ser capazes de:
- Compreender o mapeamento de problemas complexos do mundo real para soluções algorítmicas (e.g., problemas em grafos, problemas geométricos, programação linear, etc.);
- Selecionar e aplicar estruturas de dados avançadas (e.g., árvores-kd) e técnicas algorítmicas (e.g., randomização, aproximação, paralelização) para resolver problemas do mundo real;
- Conceber algoritmos eficientes para resolver um problema em questão;
- Reconhecer algumas classes de problemas intratáveis e aplicar algoritmos de aproximação para os resolver;
- Selecionar e aplicar técnicas avançadas de análise de algoritmos (e.g., amortizada, probabilística, etc.);
- Avaliar os algoritmos do ponto de vista da eficiência e correção, tanto analítica como experimentalmente.
Modo de trabalho
Presencial
Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)
Não há pré-requisito obrigatório. No entanto, serão úteis conhecimentos consolidados das unidades curriculares de
Algoritmos e Estruturas de Dados e
Desenho de Algoritmos.
Programa
- Estruturas de dados avançadas (e.g., árvores B);
- Análise probabilística e algoritmos probabilísticos (randomized);
- Algoritmos paralelos (aproximação, divisão e conquista, balanceamento, divisão geométrica);
- Estruturas de dados e algoritmos geométricos (voronoi, quad/octree, kd-tree);
- Otimização combinatória e programação linear;
- Algoritmos de aproximação e heurísticas;
- Análise amortizada.
Bibliografia Obrigatória
Thomas H. Cormen;
Introduction to algorithms. ISBN: 978-0-262-53305-8
Bibliografia Complementar
Steven S. Skiena;
The algorithm design manual. ISBN: 0-387-94860-0
M. E. Newman;
Networks. ISBN: 978-0-19-920665-0
Robert Sedgewick;
Algorithms in C++. ISBN: 0-201-35088-2
Robert Sedgewick;
Algorithms in C++. ISBN: 978-0-201-36118-6
Suman Saha, Shailendra Shukla;
Advanced Data Structures: Theory and Applications, Chapman and Hall/CRC, 2019. ISBN: 9781138592605
Peter Brass; Advanced Data Structures, Cambridge University Press, 2008. ISBN: 9780511800191
Martin Grötschel, László Lovász, Alexander Schrijver;
Geometric Algorithms and Combinatorial Optimization, Springer Verlag, 1993
Christos H. Papadimitriou;
Combinatorial optimization. ISBN: 0-13-152462-3
Observações Bibliográficas
Serão também consultados artigos científicos, publicados em conferências e periódicos.
Métodos de ensino e atividades de aprendizagem
A metodologia de ensino combina componentes teóricas e práticas. A componente teórica é usada para a exposição formal da matéria, apresentação de exemplos e sua discussão. Na componente prática, os estudantes resolvem desafios de programação com recurso a algoritmos e estruturas de dados avançados, com acompanhamento tutorial. A UC é agnóstica em relação à linguagem de programação, sendo permitido aos estudantes escolherem em que linguagem codificam os seus programas.
Adicionalmente, os estudantes deverão realizar dois projetos práticos, em grupo.
No 1º projeto prático, cada grupo deverá estudar de forma aprofundada uma estrutura de dados avançada, de interesse prático bem definido, sobre a qual produzirá uma apresentação a ser realizada aos colegas e à turma.
No 2º projeto prático, cada grupo deverá apresentar soluções para problemas do mundo real, tendo por base uma estrutura de dados das que tiverem sido apresentadas no contexto do 1º projeto prático, com a ressalva de não poderem trabalhar sobre a estrutura de dados que o próprio grupo estudou.
O 2º projeto prático será alvo de uma apresentação intermédia, de uma apresentação final, e de um relatório final.
Palavras Chave
Ciências Físicas > Ciência de computadores > Programação
Ciências Físicas > Matemática > Algoritmos
Tipo de avaliação
Avaliação distribuída sem exame final
Componentes de Avaliação
Designação |
Peso (%) |
Trabalho prático ou de projeto |
60,00 |
Trabalho escrito |
20,00 |
Participação presencial |
20,00 |
Total: |
100,00 |
Componentes de Ocupação
Designação |
Tempo (Horas) |
Elaboração de projeto |
76,00 |
Estudo autónomo |
47,00 |
Frequência das aulas |
39,00 |
Total: |
162,00 |
Obtenção de frequência
A obtenção de frequência implica nota >=8,0 em todos os cinco elementos constituintes da avaliação distribuída (AD), individualmente.
Fórmula de cálculo da classificação final
- Projecto prático 1 (P1): 20%;
- Deliverable: uma apresentação (20%)
- Projecto prático 2 (P2): 60%;
- Deliverables: duas apresentações (20%+20%) e um relatório final (20%)
- Avaliação individual (I): 20%.
Nota final: 0.2*P1 + 0.6*P2 + 0.20*I.
Provas e trabalhos especiais
Dois projectos práticos, a serem realizados em grupos de estudantes.
Apresentações individuais.
Avaliação especial (TE, DA, ...)
Estudantes com estatutos especiais devem apresentar projetos de acordo com os critérios de avaliação da unidade curricular.
Melhoria de classificação
Melhoria da classificação requer melhorias nas componentes de projeto e avaliação individual.
Observações
Para aprovação na unidade curricular, todas as componentes de avaliação devem ter notas >= 8.0 valores, e a Nota Final deve ser >= 9.5.