Estruturas de Dados e Algoritmos II

Cód.: INF13196L

6 ECTS

Duração: 15 semanas/156 horas

Área Científica: Informática

Língua(s) de lecionação: Português

Língua(s) de apoio tutorial: Português, Inglês

Regime de Frequência: Presencial

Objetivos de Desenvolvimento Sustentável

Educação de qualidade - Assegurar a educação inclusiva, e equitativa e de qualidade, e promover oportunidades de aprendizagem ao longo da vida para todos.

Objetivos de Aprendizagem

O aluno deverá:
- aprofundar os conhecimentos sobre a análise das complexidades espacial e temporal de algoritmos;
- ficar a conhecer alguns algoritmos e técnicas de programação avançados;
- ser capaz de desenhar algoritmos aplicando essas técnicas, de analisar a sua complexidade e de os implementar;
- ficar a conhecer aplicações de grafos e algoritmos sobre eles;
- conseguir escolher as estruturas de dados e os algoritmos apropriados para a resolução de um problema;
- compreender a diferença entre problemas tratáveis e não tratáveis;
- conseguir mostrar que um problema é não tratável;
- conseguir desenhar algoritmos e descrever os seus princípios e o seu funcionamento.

Conteúdos Programáticos

Análise das complexidades temporal e espacial: Complexidade amortizada
Construção de algoritmos: divisão e conquista, algoritmos greedy, programação dinâmica
Grafos: Orientados e não orientados, pesados e não pesados, representação por listas de adjacências e por matriz de adjacências; Percursos em largura e em profundidade, ordenação topológica, componentes conexas e fortemente conexas; Árvore de cobertura mínima: algoritmos de Prim e de Kruskal; O tipo abstracto de dados Partição (union-find); Caminhos mais curtos: algoritmos de Bellman-Ford e de Dijkstra, algoritmo para DAGs; Caminhos mais curtos entre cada dois vértices: algoritmo de Floyd-Warshall; Fluxos.
Teoria da complexidade: Classes P e NP, redução de problemas.

Métodos de Ensino

As aulas dividem-se em aulas de exposição e aulas de aplicação prática das técnicas expostas. Nas aulas de exposição são introduzidas as bases teóricas para o estudo complexidade de algoritmos, que são aplicadas a casos concretos. São também apresentados, descritos e analisados os vários algoritmos, e estudado o seu funcionamento.

Nas aulas práticas, as técnicas expostas são aplicadas a diferentes casos. São, também, propostos problemas para análise, estudo de soluções e implementação.

A avaliação divide-se em avaliação da componente teórica (peso de 70%), que consiste realização de testes durante o semestre ou de um exame final, e avaliação da componente prática (peso de 30%).

A componente prática da disciplina é avaliada através da realização de três trabalhos práticos, exclusivamente durante o período de aulas, envolvendo desenho ou escolha de algoritmos, desenvolvimento de programas e elaboração de relatórios.

Bibliografia

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford
Stein. Introduction to Algorithms, 4th ed. 2022, MIT Press. (Ou a 3ª
edição.)

Thomas H. Cormen. Algorithms Unlocked. 2013, MIT Press.

Slides e elementos de apoio fornecidos pelos docentes.