Departamento de Informática (UM)

Página de Unidade Curricular

DesignaçãoCódigoCursoRegimeRegente

Algoritmos e Complexidade

14305 [J303N6]

Licenciatura em Engenharia Informática [ENGINF]

S3

Jorge Miguel Matos Sousa Pinto

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.

Funcionamento

Turno: T 1; Docente: Jorge Miguel Matos Sousa Pinto; Dep.: DI; Horas: 30.
Turno: TP 1; Docente: Jorge Miguel Matos Sousa Pinto; Dep.: DI; Horas: 30.
Turno: T 2; Docente: José Bernardo Santos Monteiro Vieira Barros; Dep.: DI; Horas: 30.
Turno: TP 2; Docente: Jorge Miguel Matos Sousa Pinto; Dep.: DI; Horas: 30.
Turno: TP 3; Docente: Manuel Alcino Pereira Cunha; Dep.: DI; Horas: 30.
Turno: TP 4; Docente: José Carlos Bacelar Ferreira Junqueira Almeida; Dep.: DI; Horas: 30.
Turno: TP 5; Docente: José Carlos Bacelar Ferreira Junqueira Almeida; Dep.: DI; Horas: 30.
Turno: TP 6; Docente: José Bernardo Santos Monteiro Vieira Barros; Dep.: DI; Horas: 30.
Turno: TP 7; Docente: Olga Maria Gomes Martins Pacheco; Dep.: DI; Horas: 30.

[ Outras UCs do Departamento ]