Algoritmos e Complexidade

Informação geral

Código: 14305
Área científica predominante: Informática
Regime: Semestral
ECTS: 5
Tipo de ensino: Presencial

Carga Horária

Trabalho autónomo: 80 horas

Aulas:
30 horas - Teóricas
30 horas - Teórico-práticas

Objetivos de ensino

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.

Resultados de 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.

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

Métodos de ensino

A escolaridade da UC é utilizada da seguinte forma:

• Duas horas téoricas (T) semanais são utilizadas para exposição da matéria e apresentação de casos de estudo.
• Com uma vocação complementar às anteriores, duas horas semanais teórico-práticas (TP) de utilização flexível, podem servir para a exposição sucinta de temas não abordados nas aulas teóricas, por se considerar serem particularmente adequados para a auto-aprendizagem guiada; ou também para a resolução de exercícios ou apresentação de casos de estudo.
  Sempre que adequado, as aulas TP terão um carácter mais laboratorial, com a utilização de um ambiente de desenvolvimento online.

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.