Análise e Desenho de Algoritmos
Objetivos
Saber
Definir e identificar três técnicas de desenho de algoritmos: estratégias greedy, programação dinâmica e transformação-e-conquista.
Conhecer os algoritmos fundamentais de grafos, os tipos abstratos de dados envolvidos e as estruturas de dados usadas para os implementar com eficiência.
Compreender complexidade amortizada.
Definir algumas classes de complexidade e compreender alguns problemas em aberto.
Saber Fazer
Conceber e analisar um algoritmo aplicando programação dinâmica.
Formalizar um problema concreto em termos de grafos e adaptar um algoritmo clássico para o resolver.
Escolher, comparar, adaptar e utilizar estruturas de dados adequadas ao problema a resolver.
Calcular a complexidade de algoritmos com base na complexidade amortizada das funções auxiliares e calcular a complexidade amortizada dessas funções.
Avaliar soluções e efetuar escolhas fundamentadas.
Provar que um problema é NP-completo.
Caracterização geral
Código
8154
Créditos
6.0
Professor responsável
Margarida Paula Neves Mamede
Horas
Semanais - 5
Totais - 67
Idioma de ensino
Português
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 (4th ed.). The MIT Press, 2022.
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 (3rd ed.). Springer, 2020.
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 for entregue no Moodle 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, presenciais 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):
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, presenciais, 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).
Há pré-inscrição nos testes.
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):
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.3 CompL + 0.7 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.
Melhoria de Nota de Alunos Aprovados em 2021/22
De acordo com o Regulamento de Avaliação de Conhecimentos da FCT NOVA, a nota final dos alunos aprovados em 2021/22 que realizem o exame de melhoria de nota em 2022/23 é calculada com as regras de 2021/22. Portanto, nesses casos, a nota final é:
- F = Ex, se Ex < 9.5;
- F = 0.25 CompL + 0.75 Ex, se Ex >= 9.5 ,
onde Ex é a nota do exame realizado em 2022/23 e CompL é a nota da componente laboratorial obtida em 2021/22.
Frequência e Classificações Obtidas em Anos Anteriores
Os alunos que obtiveram frequência em 2020/21 ou 2021/22 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 2020/21, em 2021/22 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.