Algoritmos e Complexidade

Universidade do Minho // 2026-27

Introdução e objectivos

eeeEsta 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.

  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.

Programa // Plano

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   Validade de um Triplo de Hoare. Regras de prova: Sequencia, atribuição e condicionais
29.Set a 3.Out   Correcção de ciclos: variantes e invariantes.
6.Out a 10.Out   Introdução à análise de complexidade. Tamanho do input. Melhor e pior casos. Caso médio.
13.Out a 17.Out   Análise de definições recursivas. Relações de recorrência. Complexidade de algoritmos de ordenação.
20.Out a 24.Out   Análise amortizada
27.Out a 30.Out   Estruturas de dados para representar dicionarios: tabelas de Hash
3.Nov a 7.Nov   Árvores AVL: motivação e algoritmo de inserção balanceada
10.Nov a 14.Nov   Revisões
17.Nov a 21.Nov   Grafos: representações e funções de consulta
24.Nov a 28.Nov   Grafos: travessias
1.Dez a 5.Dez   Grafos pesados: algoritmo de Dijkstra, Prim e Floyd Warshal
8.Dez a 12.Dez    

Avaliação

Será constituída por dois testes nas seguintes datas:

O exame de recurso será no dia tba.

Testes e exames anteriores

Material

Notas/slides JSP

Notas JBB

Contactos

Docente Horário Atendimento
José Bernardo Barros 3a-f tarde
Renato Neves 3a-f tarde
Jorge Sousa Pinto 6a-f, 9h00-11h00

Bibliografia

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).