Análise e Desenho de Algoritmos
Código
8154
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Informática
Créditos
6.0
Professor responsável
Luís Manuel Marques da Costa Caires, Margarida Paula Neves Mamede
Horas semanais
4
Total de horas
57
Língua de ensino
Português
Objectivos
Saber
Conhecer os algoritmos fundamentais de grafos, os tipos abstratos de dados envolvidos e as estruturas de dados usadas para os implementar com eficiência.
Definir e identificar três técnicas de desenho de algoritmos: programação dinâmica, estratégias greedy e transformação e conquista.
Compreender complexidade amortizada.
Saber Fazer
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.
Conceber e analisar um algoritmo aplicando programação dinâmica.
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 efectuar escolhas fundamentadas.
Pré-requisitos
Os alunos deverão ter realizado as seguintes unidades curriculares:
- Introdução à Programação;
- Programação Orientada pelos Objectos;
- Matemática Discreta;
- Algoritmos e Estruturas de Dados.
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. Teste à aciclicidade.
(4) Árvores mínimas de cobertura. Algoritmo de Kruskal. Tipo abstrato de dados partição.
(5) Algoritmo de Prim. Tipo abstrato de dados fila com prioridade adaptável.
(6) Caminhos mais curtos. Algoritmos de Dijkstra e Bellman-Ford.
(7) Fluxos máximos. Método de Ford-Fulkerson. Algoritmo de Edmonds-Karp. Emparelhamentos máximos em grafos bipartidos. Cortes mínimos.
(8) Complexidade amortizada. Método do potencial.
Bibliografia
Referências Principais
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd edition). 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 edition). Addison-Wesley, 2011
Steven S. Skiena. The Algorithm Design Manual (2nd edition). 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 é realizado em grupo (de dois alunos) ou individualmente. 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.
A nota da componente laboratorial (CompL) é a média simples das notas dos três trabalhos (TP1, TP2 e TP3):
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 podem 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.
A nota da componente teórico-prática (CompTP) é a média pesada 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 (NF) dos alunos com frequência é:
- NF = CompTP, se CompTP < 9.5;
- NF = 0.4 CompL + 0.6 CompTP, se CompTP >= 9.5 .
Todas as notas (TP1, TP2, TP3, T1, T2, Ex, CompL e CompTP) são arredondadas às décimas, exceto a nota final (NF) que é arredondada às unidades.
Frequência e Classificações Obtidas em Anos Anteriores
Os alunos que já obtiveram frequência alguma vez têm automaticamente frequência. Sejam:
- CompL-Anterior a média das notas dos trabalhos realizados anteriormente;
- CompL-2014/15 a média das notas dos trabalhos realizados este ano letivo (que é zero, se nenhum trabalho for entregue).
No cálculo da nota final, a nota da componente laboratorial é o máximo entre CompL-Anterior e CompL-2014/15.
Os alunos que obtiveram pelo menos 9.5 na nota da componente teórico-prática em 2013/14 também estão dispensados de realizar os testes e o exame. Sejam:
- CompTP-Anterior a nota da componente teórico-prática obtida em 2013/14 (que tem de ser superior ou igual a 9.5);
- CompTP-2014/15 a nota da componente teórico-prática obtida este ano letivo (que é zero, se nenhuma prova for entregue).
No cálculo da nota final, a nota da componente teórico-prática é o máximo entre CompTP-Anterior e CompTP-2014/15.