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
5
Total de horas
67
Língua de ensino
Português
Objectivos
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.
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.
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. Algoritmo de Edmonds-Karp. 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.
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
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 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). 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 das notas dos 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 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 (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 2015/16 ou 2014/15 têm automaticamente frequência. Sejam:
- CompL-Anterior a média das notas dos trabalhos realizados anteriormente;
- CompL-2016/17 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-2016/17.
Os alunos que obtiveram frequência em 2013/14 ou anteriormente têm de realizar os trabalhos este ano.
Os alunos que obtiveram pelo menos 9.5 na componente teórico-prática em 2015/16 estão dispensados de realizar os testes e o exame. No cálculo da nota final, a nota da componente teórico-prática é o máximo entre a nota da componente teórico-prática obtida o ano passado e a nota da componente teórico-prática obtida este ano.