Algoritmos e Complexidade

Universidade do Minho // 2026-27

Introdução e objectivos

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.

  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

Datas TPs Ts
14.Set a 18.Set   Apresentação. Introdução à correcção de Programas Imperativos. Especificações e triplos de Hoare
21.Set a 24.Set Ficha 1 (Especificação) Validade de um Triplo de Hoare. Regras de prova: Sequência, atribuição e condicionais
28.Set a 02.Out Ficha 1 (Correcção) Correcção de ciclos: variantes e invariantes.
05.Out a 09.Out Ficha 1 (Correcção) Introdução à análise de complexidade. Tamanho do input. Melhor e pior casos. Caso médio.
12.Out a 16.Out   Análise de definições recursivas. Relações de recorrência. Complexidade de algoritmos de ordenação.
19.Out a 23.Out   Análise amortizada
26.Out a 29.Out   Revisões
02.Nov a 06.Nov   Estruturas de dados para representar dicionários: tabelas de Hash
09.Nov a 13.Nov   Árvores AVL: motivação e algoritmo de inserção balanceada
16.Nov a 20.Nov   Grafos: representações e funções de consulta
23.Nov a 27.Nov   Grafos: travessias
30.Dez a 04.Dez   Grafos pesados: algoritmo de Dijkstra, Prim e Floyd Warshal
8.Dez a 12.Dez   Revisões

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 (enviar e-mail antes)
Renato Neves 3a-f tarde (enviar e-mail antes)
Jorge Sousa Pinto 4a-f, 9h00-11h00 (enviar e-mail antes)
Alcino Cunha 4a-f tarde (enviar e-mail antes)

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