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
73
Língua de ensino
Português
Objectivos
- Conhecer os algoritmos fundamentais de grafos, os tipos abstractos de dados envolvidos e as estruturas de dados usadas para os implementar com eficiência.
- Conhecer três técnicas de desenho de algoritmos: programação dinâmica, estratégias greedy e transformação e conquista.
- Compreender complexidade amortizada.
- Definir algumas classes de complexidade e compreender alguns problemas em aberto. Reconhecer os problemas da classe NP.
- 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.
- Provar que um problema é NP-completo.
- Aptidão para avaliar soluções e efectuar escolhas fundamentadas.
- Capacidade de gestão do tempo e cumprimento dos prazos.
- Capacidade de comunicação escrita: relatório sobre o desenho, a análise e a implementação de um algoritmo.
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;
- Teoria da Computação.
Conteúdo
Programação dinâmica.
Introdução ao estudo de grafos. Definições fundamentais. Tipos abstractos de dados grafo não orientado e grafo orientado. Implementações de grafos.
Algoritmos elementares de grafos. Percursos em profundidade e em largura. Ordenação topológica. Teste à aciclicidade.
Árvores mínimas de cobertura. Algoritmo de Kruskal. Tipo abstracto de dados partição.
Complexidade amortizada. Métodos da contabilidade e do potencial.
Algoritmo de Prim. Tipo abstracto de dados fila com prioridade adaptável. Filas binomiais e de Fibonacci.
Caminhos mais curtos. Algoritmos de Dijkstra, Bellman-Ford e Floyd-Warshall.
Fluxos máximos. Método de Ford-Fulkerson. Algoritmo de Edmonds-Karp. Emparelhamentos máximos em grafos bipartidos. Cortes mínimos.
Introdução à Teoria da Complexidade. As classes P, FP, NP, PSPACE e EXPTIME. Os afixos co, 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, 2006.
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, 1990.
- 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. Algumas aulas práticas são dedicadas à realização dos trabalhos de avaliação.
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 efectuadas 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, excepto a nota final (NF) que é arredondada às unidades.
Frequência Obtida 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 e
- CompL-2012/13 a média das notas dos trabalhos realizados este ano lectivo (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-2012/13.