Objetivos | Esta unidade curricular visa tornar os estudantes aptos a analisar algoritmos (do ponto de vista da correção e da utilização de recursos, em particular o tempo de execução), bem como a utilizar algoritmos sobre estruturas de dados avançadas, nomeadamente os grafos. A UC introduz ainda conceitos elementares de complexidade algorítmica, como a noção de problema NP-completo. |
Programa | 1. Introdução à análise de correção de algoritmos: pré e pós-condições; invariantes de ciclo; anotação de programas.
2. 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.
3. Estruturas de dados eficientes: árvores AVL, tabelas de dispersão, heaps. Implementação eficiente de buffers e dicionários.
4. Algoritmos fundamentais sobre grafos; estratégia algorítmica greedy e programação dinâmica.
5. Introdução às classes de problemas de decisão P, NP, e NP-completo |
Bibliografia | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009.
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. Algorithms in C: parts 1-4, Fundamentals, Data Structures, Sorting, and Searching, third edition. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1997. |
Resultados da aprendizagem | Após a frequência da UC os alunos serão capazes de:
- Analisar a correção de algoritmos face a especificações lógicas (contratos), recorrendo à noção de invariante de ciclo.
- Analisar a complexidade assimptótica de um algoritmo iterativo ou recursivo.
- Reconhecer e utilizar estratégias algorítmicas fundamentais.
- Utilizar estruturas de dados eficientes e conceber algoritmos sobre elas (árvores AVL, tabelas de dispersão, e heaps).
- Utilizar e conceber algoritmos sobre grafos.
- Identificar problemas NP-completos. |
Método de avaliação | A avaliação é feita através de dois testes, um intercalar e outro final, ambos com peso de 50%, sendo requisito para a aprovação a obtenção de uma classificação mínima de 25% em cada um dos testes. |
Departamento de Informática (UM)