Desenho de Algoritmos para Problemas de Otimização (2017/2018) - Departamento de Informática
Descrição

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.

Nesta UC estudam-se vários algoritmos (de aproximação e de pesquisa local), 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.

Objectivos

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.

Programa

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.

Bibliografia Principal

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 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.

Requisitos Prévios

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.

Esforço do Aluno
  Horas por crédito 28
  Horas p/ semana Semanas Horas
Aulas práticas e laboratoriais   26.0
Aulas teóricas   26.0
Avaliação   5.0
Estudo   48.0
Orientação tutorial   3.0
Projectos e trabalhos   60.0
Total de Horas 168
ECTS 6.0