Desenho de Algoritmos para Problemas de Otimização
Código
11556
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Informática
Créditos
6.0
Professor responsável
Margarida Paula Neves Mamede, Pedro Manuel Corrêa Calvente Barahona
Horas semanais
4
Total de horas
55
Língua de ensino
Inglês
Objectivos
Saber
Definir e identificar algoritmos de aproximação, aleatórios e de pesquisa local.
Conhecer alguns métodos gerais para conceber algoritmos de aproximação, aleatórios e de pesquisa local.
Compreender heurísticas e meta-heurísticas.
Saber Fazer
Conceber um algoritmo de aproximação, um algoritmo aleatório e um algoritmo de pesquisa local para um problema de otimização concreto.
Calcular o rácio de aproximação de um algoritmo de aproximação.
Efetuar a análise probabilística de um algoritmo aleatório.
Selecionar as técnicas apropriadas a um problema.
Competências Complementares
Capacidade de investigação e autonomia.
Pré-requisitos
Os alunos devem:
(a) ter destreza em programação;
(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;
(d) conhecer os conceitos básicos da Teoria da Complexidade.
(e) conhecer os conceitos básicos de pesquisa em espaço de estados.
Conteúdo
(1) Problemas de decisão e problemas de otimização. Problemas tratáveis e problemas difíceis. Técnicas de desenho de algoritmos para problemas de otimização difíceis.
(2) Algoritmos de aproximação. Rácio de aproximação. Estratégias greedy. Os métodos primal-dual e primal. Esquemas de aproximação.
(3) Algoritmos de aproximação aleatórios. Análise probabilística.
(4) Algoritmos de pesquisa local. Recomeços. Pesquisa tabu. Arrefecimento simulado. Pesquisa com vizinhança variável. Pesquisa em grandes vizinhanças. Colónias de formigas.
Bibliografia
Referências Principais
Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2006.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd edition). The MIT Press, 2009.
Pascal van Hentenryck and Laurent Michel, Constraint-Based Local Search, MIT Press, 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.
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
A avaliação é composta por um trabalho e dois testes.
O trabalho é realizado em duas fases, entregues em datas distintas, e consiste num estudo comparativo, teórico e experimental, de soluções alternativas para um problema de otimização, incluindo a elaboração de dois relatórios (um por fase) e na realização de uma discussão. Os testes e o exame são com consulta.
Condição para obter aprovação:
NotaP >= 9 e NotaT >= 9 e NotaF = (NotaP + NotaT) / 2 >= 10,
onde:
- NotaP é a nota do trabalho, calculada com as notas das duas fases;
- NotaT é a média das notas dos testes ou a nota do exame;
- NotaF é a nota final.
Em caso de reprovação, se a nota do trabalho não for inferior a 9, os alunos podem realizar um exame final, cuja nota substitui a anterior NotaT.