Departamento de Informática (UM)

Página de Unidade Curricular

DesignaçãoCódigoCursoRegimeRegente

Algoritmos e Complexidade

[8503O8]

Licenciatura em Ciências da Computação [CCOM]

S3

José Bernardo Santos Monteiro Vieira Barros

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

Programa sucinto
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

Bibliografia essencial

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

Métodos 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: José Bernardo Santos Monteiro Vieira Barros; Dep.: DI; Horas: 30.
Turno: TP 1; Docente: Manuel Alcino Pereira Cunha; Dep.: DI; Horas: 30.
Turno: TP 2; Docente: Jorge Miguel Matos Sousa Pinto; Dep.: DI; Horas: 30.

[ Outras UCs do Departamento ]