Esta unidade curricular visa tornar os estudantes aptos a analisar algoritmos do ponto de vista da sua correcção e tempo de execução. Visa também tornar os estudantes proficientes na utilização de estruturas de dados avançadas, por exemplo grafos. A UC introduz ainda conceitos elementares de complexidade algorítmica, tais como a noção do problema NP-completo.
- Introdução à análise de correção de algoritmos: pré e pós-condições; invariantes de ciclo; anotação de programas.
- Análise de tempo de execução de algoritmos: modelo de complexidade assimptótica; estratégias algorítmicas; recorrências; análise de melhor caso, pior caso, e caso médio; análise amortizada; casos de estudo.
- Estruturas de dados eficientes: árvores AVL, tabelas de dispersão, heaps. Implementação eficiente de buffers e dicionários.
- Algoritmos fundamentais sobre grafos; estratégia algorítmica greedy e programação dinâmica.
- Introdução às classes de problemas de decisão P, NP, e NP-completo.
| Datas | TPs | Ts |
|---|---|---|
| 15.Set a 19.Set | Apresentação. Introdução à correcção de Programas Imperativos. Especificações e triplos de Hoare | |
| 22.Set a 25.Set | Ficha 1.1 (Especificações) | Validade de um Triplo de Hoare. Regras de prova: Sequencia, atribuição e condicionais |
| 29.Set a 3.Out | Ficha 1.2 (Correcção) | Correcção de ciclos: variantes e invariantes. |
| 6.Out a 10.Out | Ficha 1.3 (Invariantes) | Introdução à análise de complexidade. Tamanho do input. Melhor e pior casos. Caso médio. |
| 13.Out a 17.Out | Ficha 2.1 (Contagem) | Análise de definições recursivas. Relações de recorrência. Complexidade de algoritmos de ordenação. |
| 20.Out a 24.Out | Ficha 2.2 (Recorrências) | Análise amortizada |
| 27.Out a 30.Out | Ficha 2.(3,4) (Caso médio/Amortizada) | Estruturas de dados para representar dicionarios: tabelas de Hash |
| 3.Nov a 7.Nov | Ficha 3.1 (min-heaps) | Árvores AVL: motivação e algoritmo de inserção balanceada |
| 10.Nov a 14.Nov | Revisões | Revisões |
| 17.Nov a 21.Nov | Ficha 3.2 (THash) | Grafos: representações e funções de consulta |
| 24.Nov a 28.Nov | Ficha 4.1 (Representações de grafos) | Grafos: travessias |
| 1.Dez a 5.Dez | Ficha 4.2 (Travessias de grafos) | Grafos pesados: algoritmo de Dijkstra, Prim e Floyd Warshal |
| 8.Dez a 12.Dez | Ficha 4.3 (Grafos pesados/problema) |
Será constituída por dois testes nas seguintes datas:
- 15 Novembro 2025
- 10 Janeiro 2026
O exame de recurso será no dia 24 Janeiro 2026.
- Exame 24-25
- Teste 2 24-25
- Teste 1 24-25
- Exame 23-24
- Teste 2 23-24
- Teste 1 23-24
- Exame 22-23
- Teste 2 22-23
- Teste 1 22-23
- C1. Especificação e Correcção de Algoritmos
- C2. Correcção de Algoritmos com Ciclos
- T1. Tempo de Execução de Algoritmos Iterativos
- T2. Análise de Pior Caso, Melhor Caso, e Caso Médio
- T3. Análise do Tempo de Execução de Algoritmos Recursivos
- T4. Tópicos sobre Algoritmos de Ordenação
- T5. Análise Amortizada de Algoritmos
- ED2. Filas com Prioridades e “Heaps”
- ED4. Tabelas de “hash”
- G1. Representação de Grafos em Computador
- G2. Algoritmos de Travessia de Grafos
- G3. Algoritmos sobre Grafos Pesados: Estratégia Greedy
- G4: Algoritmos sobre Grafos Pesados: Programação Dinâmica
| Docente | Horário Atendimento |
|---|---|
| José Bacelar Almeida | 5a-f, 11h00-13h00 |
| José Bernardo Barros | 3a-f tarde |
| Renato Neves | 3a-f tarde |
| Jorge Sousa Pinto | 6a-f, 9h00-11h00 |
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Fourth Edition. The MIT Press, 2022.
Donald E. Knuth. The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison- Wesley, 1973.
Donald E. Knuth. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, 1973.
Donald E. Knuth. The Art of Computer Programming, Volume II: Seminumerical Algorithms, 2nd Edition. Addison- Wesley, 1981.
Robert Sedgewick, Kevin Wayne. Algorithms. Addison-Wesley, 4th edition (March 24, 2011).