🇬🇧 EN

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.

Assim, 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

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

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Fourth Edition. The MIT Press, 2022.
  2. Donald E. Knuth. The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison- Wesley, 1973.
  3. Donald E. Knuth. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, 1973.
  4. Donald E. Knuth. The Art of Computer Programming, Volume II: Seminumerical Algorithms, 2nd Edition. Addison- Wesley, 1981.
  5. Robert Sedgewick, Kevin Wayne. Algorithms. Addison-Wesley, 4th edition (March 24, 2011).

Atualizado: