Análise e Desenho de Algoritmos

Caracterização geral

Pré-requisitos

Os alunos devem:

(a) ter destreza em programação orientada por objetos;

(b) estar familiarizados com as estruturas de dados fundamentais (listas ligadas, tabelas de dispersão, árvores binárias de pesquisa, heaps binários);

(c) saber calcular as complexidades temporal e espacial de algoritmos.

Bibliografia

Referências Principais

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd ed.). The MIT Press, 2009.

Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005.

Referências Complementares

Anany Levitin. Introduction to The Design and Analysis of Algorithms (3rd ed.). Addison-Wesley, 2012.

S. Sridhar. Design and Analysis of Algorithms. Oxford University Press, 2014.

Dexter Kozen. The Design and Analysis of Algorithms. Springer, 1992.

Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.

Steven S. Skiena. The Algorithm Design Manual (2nd ed.). Springer, 2008.

Steven S. Skiena and Miguel A. Revilla. Programming Challenges: The Programming Contest Training Manual. Springer, 2003.

Método de ensino

O ensino consiste na exposição da matéria em aulas teóricas e na resolução de problemas em aulas práticas de laboratório. No laboratório, os alunos desenham, analisam e implementam algoritmos.

Método de avaliação

Componentes da Avaliação

A avaliação é constituída por duas componentes: a componente laboratorial e a componente teórico-prática.

Componente Laboratorial e Frequência

A componente laboratorial é composta por três trabalhos. Cada trabalho consiste no desenho, na análise e na implementação de um algoritmo para resolver um problema de um concurso de programação, na elaboração de um relatório e na realização de uma discussão. As duas primeiras partes do trabalho (programa e relatório) são realizadas em grupo de dois alunos; a discussão é individual.

Um grupo entrega um trabalho se o seu programa for aceite pelo Mooshak e o respetivo relatório (em papel) for entregue na Secretaria do DI dentro do prazo. As notas dos trabalhos entregues variam entre 10 e 20 valores.

As discussões (para aferir o conhecimento que cada aluno tem sobre os trabalhos que entregou) são obrigatórias e individuais. A nota de um aluno num trabalho depende do trabalho que entregou (realizado em grupo), do seu desempenho na discussão e do desempenho do seu colega de grupo na discussão, caso os desempenhos de ambos sejam significativamente desequilibrados. Consequentemente, as notas dos dois elementos do grupo podem ser diferentes (e variam entre 0 e a nota do trabalho).

A nota da componente laboratorial (CompL) é a média das notas do aluno nos três trabalhos (P1, P2 e P3):

CompL = (P1 + P2 + P3) / 3.

Para obter frequência, é necessário que CompL >= 7.0 .

As discussões dos trabalhos serão efetuadas no fim do semestre, apenas com os alunos que puderem ter frequência.

Componente Teórico-Prática

A componente teórico-prática é composta por dois testes (no período de aulas) ou por um exame (na Época de Recurso). As três provas são individuais, escritas e com consulta. Cada aluno pode consultar todo o material que quiser, desde que esteja em papel e o tenha levado para a prova. Não são permitidos dispositivos eletrónicos (e.g. calculadoras, telemóveis, smartwatches e portáteis).

A nota da componente teórico-prática (CompTP) é a média das notas dos testes (T1 e T2) ou a nota do exame (Ex):

CompTP = (T1 + T2) / 2   ou   CompTP = Ex.

Para obter aprovação, é necessário que CompTP >= 9.5 .

Nota Final

A nota final (F) dos alunos com frequência é:

• F = CompTP,   se CompTP < 9.5;
• F = 0.4 CompL + 0.6 CompTP,   se CompTP >= 9.5 .

Todas as notas (P1, P2, P3, T1, T2, Ex, CompL e CompTP) são arredondadas às décimas, exceto a nota final (F) que é arredondada às unidades.

Frequência e Classificações Obtidas em Anos Anteriores

Os alunos que obtiveram frequência em 2017/18 ou 2018/19 têm automaticamente frequência. No cálculo da nota final, a nota da componente laboratorial é o máximo das notas (da componente laboratorial) obtidas em 2017/18, em 2018/19 e este ano.

Conteúdo

(1) Programação dinâmica.

(2) Introdução ao estudo de grafos. Definições fundamentais. Tipos abstratos de dados grafo não orientado e grafo orientado. Implementações de grafos.

(3) Algoritmos elementares de grafos. Percursos em profundidade e em largura. Ordenação topológica.

(4) Árvores mínimas de cobertura. Algoritmo de Kruskal. Tipo abstrato de dados partição.

(5) Complexidade amortizada. Método do potencial.

(6) Algoritmo de Prim. Tipo abstrato de dados fila com prioridade adaptável.

(7) Redes de fluxos. Fluxos máximos. Método de Ford-Fulkerson. Algoritmo de Edmonds-Karp. Emparelhamentos máximos em grafos bipartidos. Cortes mínimos.

(8) Caminhos mais curtos. Algoritmos de Dijkstra, Bellman-Ford e Floyd-Warshall.

(9) Introdução à Teoria da Complexidade. As classes P, NP, PSPACE e EXPTIME. Os sufixos difícil e completo. Redução de problemas. Alguns problemas em aberto.

Cursos

Cursos onde a unidade curricular é leccionada: