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 - 66
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ÊNCIA PRINCIPAL
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (4th ed.). The MIT Press, 2022.
REFERÊNCIAS COMPLEMENTARES
Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005.
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.
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 discussão de um trabalho consiste em fazer alterações ao código do trabalho entregue para que o novo programa resolva uma variante do problema original, definida no enunciado da discussão, que difere pouco do problema resolvido no trabalho. As notas das discussões e os respetivos critérios são os seguintes:
- 20: a alteração está globalmente certa;
- 16: a alteração está confusa ou muito incompleta, mas o caminho poderia ser o seguido;
- 12: a alteração não está certa, havendo "algumas coisas bem e outras muito mal";
- 4: não foi feita qualquer alteração ou as alterações feitas são ínfimas (e.g. alterar apenas a leitura) ou as alterações feitas não fazem sentido.
Regra geral, a nota de um aluno num trabalho é o mínimo entre a nota do trabalho que entregou (realizado em grupo) e a sua nota na discussão desse trabalho (que é zero, se o aluno faltou). A nota de um aluno num trabalho pode ser inferior à obtida pela regra anterior, caso o desempenho do seu colega de grupo na discussão de todos os trabalhos seja muito mau (avaliado com 4). 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 indivisível (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, tablets e portáteis).
Regra adicionada a 20-junho-2025: Durante uma prova de avaliação, um estudante não pode ter junto a si dispositivos eletrónicos com capacidade de acesso à internet ou ligação bluetooth (e.g., smartphones, smartwatches, smartglasses, tablets, laptops, etc.), ainda que desligados. A violação desta regra implica a reprovação liminar na unidade curricular por exclusão e será comunicada à Comissão Científica do respetivo Curso.
Há pré-inscrição nos testes. Quando for divulgada a distribuição dos estudantes pelas salas, será identificada uma sala onde os alunos que não se inscreveram no teste talvez o possam realizar, de acordo com a seguinte regra. Se 15 minutos após o início efetivo do teste, o número de estudantes não inscritos que pretendem realizar o teste tiver lugar na sala referida e existirem enunciados disponíveis, esses estudantes podem realizar o teste, não lhes sendo concedido tempo extra. Se não existirem lugares ou enunciados para todos esses estudantes, nenhum realizará o teste.
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.
Frequência e Classificações Obtidas em Anos Anteriores
Os alunos que obtiveram frequência em 2022/23 ou 2023/24 estão dispensados de realizar os trabalhos.
Se não entregarem qualquer trabalho, têm automaticamente frequência e a nota da Componente Laboratorial (CompL) obtida anteriormente será usada no cálculo da nota final.
Se optarem por entregar algum trabalho, as suas notas nos três trabalhos (P1, P2 e P3) serão todas calculadas com base nos elementos de avaliação entregues este semestre, sendo possível que não obtenham frequência.
Fraude e Plágio
As questões de fraude e plágio serão tratadas de acordo com o Regulamento de Avaliação de Conhecimentos da FCT NOVA.
Os alunos podem conversar com os colegas sobre os trabalhos e discutir soluções, mas não podem partilhar código (mesmo que sejam "poucas linhas") em nenhuma circunstância, oralmente ou por escrito. A escrita de código tem de ser uma tarefa interna a cada grupo. Por exemplo, não é permitido mostrar código no ecrã, ditar código, enviar ficheiros com código nem colocá-los em sítios acessíveis a terceiros. Considera-se que:
- um grupo que dá ou que recebe código comete fraude;
- um grupo em que só um dos membros trabalha comete fraude;
- os alunos que realizam o trabalho em grupos maiores, partilhando código, cometem fraude.
A utilização de ferramentas de IA (como, por exemplo, ChatGPT ou Copilot) tem de ser explicitamente referida no código. Considera-se que um grupo que use estas ferramentas durante a realização de um trabalho e omita que as usou comete plágio.
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) Caminhos mais curtos. Algoritmos de Dijkstra, Bellman-Ford e Floyd-Warshall.
(8) Redes de fluxos. Fluxos máximos. Método de Ford-Fulkerson. Algoritmos de Edmonds-Karp e Dinic. Emparelhamentos máximos em grafos bipartidos. Cortes mínimos.
(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.