Estruturas de Dados e Algoritmos Avançados

Código:

M.EIC015

Sigla:

EDAA

Áreas Científicas
Classificação	Área Científica
OFICIAL	Programação

Ocorrência: 2022/2023 - 2S

Ativa?	Sim
Unidade Responsável:	Departamento de Engenharia Informática
Curso/CE Responsável:	Mestrado em Engenharia Informática e Computação

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

1. Estruturas de dados avançadas (e.g., árvores B);


2. Análise probabilística e algoritmos probabilísticos (randomized);


3. Algoritmos paralelos (aproximação, divisão e conquista, balanceamento, divisão geométrica);


4. Estruturas de dados e algoritmos geométricos (voronoi, quad/octree, kd-tree);


5. Otimização combinatória e programação linear;


6. Algoritmos de aproximação e heurísticas;


7. 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.