2023

Estruturas de Dados e Algoritmos II

Nome: 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

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, 3rd ed. 2009, MIT Press.

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

Slides e elementos de apoio fornecidos pelos docentes.