Desenho de Algoritmos para Problemas de Otimização
Objetivos
Os problemas de otimização são centrais em diversas áreas de atividade mas a sua resolução exata não é geralmente possível, devido à sua natureza combinatória (complexidade NP-difícil) e ao tamanho das instâncias nas aplicações reais. Neste contexto, existem várias técnicas de desenho de algoritmos que, não garantindo soluções exatas, permitem conceber algoritmos muito competitivos, não só pela sua eficiência, como pelas garantias de obtenção de soluções aceitáveis com recursos limitados, nomeadamente:
Os Algoritmos de Aproximação polinomiais calculam soluções aproximadas, no sentido em que se determina um limite superior para o erro entre a solução computada e a solução ótima. Os algoritmos de aproximação aleatórios, que exploram a aleatoriedade na geração de soluções, oferecem garantias na probabilidade da quantidade de recursos necessários para obter soluções aproximadas.
Algoritmos de Pesquisa Local que, não oferecendo as garantias formais dos algoritmos anteriores, permitem obter frequentemente melhores soluções com um bom compromisso com os recursos necessários para a sua obtenção.
Nesta UC estudam-se vários destes algoritmos, bem como a sua aplicação a diversos problemas, de forma a que os alunos possam explorar diferentes métodos para solucionar problemas de otimização e apreender as vantagens e desvantagens das alternativas estudadas.
Caracterização geral
Código
11556
Créditos
6.0
Professor responsável
Margarida Paula Neves Mamede, Pedro Manuel Corrêa Calvente Barahona
Horas
Semanais - 4
Totais - 55
Idioma de ensino
Português
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 de pesquisa em espaço de estados.
Bibliografia
Referências Principais:
Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd ed.). 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 ed.). Addison-Wesley, 2012.
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. 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 a 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.
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. Algoritmos "greedy". Esquemas de aproximação. Programação linear e arredondamento. O método primal-dual. Algoritmos aleatórios de aproximação. Análise probabilística.
3. Algoritmos de pesquisa local. Recomeços. Pesquisa tabu. Arrefecimento simulado. Pesquisa com vizinhança variável. Colónias de formigas. Pesquisa Evolucionária Híbrida. Pesquisa Local Guiada. Pesquisa em grandes vizinhanças.