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:
Teofilo F. Gonzalez (Ed.). Handbook of Approximation Algorithms and Metaheuristics, Second Edition: Methodologies and Traditional Applications. CRC Press, 2018.
Patrick Siarry (Ed.). Metaheuristics. Springer, 2016.
Rafael Martí, Pardalos Panos, and Maurício Resende (Eds.). Handbook of Heuristics. Springer, 2017.
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 um trabalho, elaborado em grupo de dois alunos. 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 (efetuada no fim do semestre). As notas dos dois elementos do grupo podem ser diferentes, se os desempenhos na discussão forem significativamente desequilibrados.
A nota da componente laboratorial (CompL) é a média das notas das duas fases do trabalho (P1 e P2):
Para obter frequência, é necessário que CompL >= 9.
Componente Teórico-Prática
A componente teórico-prática é composta por dois testes (no período de aulas) ou por um exame com duas partes (na Época de Recurso). As provas são presenciais (se as restrições relacionadas com a pandemia COVID o permitirem), individuais, escritas e com consulta. No primeiro teste e na primeira parte do exame, cada aluno pode consultar todo o material que quiser, desde que esteja em papel e o tenha levado para a prova; não são permitidos dispositivos eletrónicos (e.g. calculadoras, telemóveis, smartwatches e portáteis). No segundo teste e na segunda parte do exame, podem ser consultados quaisquer elementos em papel ou no computador pessoal, mas não são permitidos acessos à Internet.
A nota da componente teórico-prática (CompTP) é a média das notas dos testes (T1 e T2) ou a nota do exame (Ex):
Para obter aprovação, é necessário que CompTP >= 9.
Nota Final
A nota final (F) dos alunos com frequência é:
- F = CompTP, se CompTP < 9;
- F = (CompL + CompTP) / 2, se CompTP >= 9.
Todas as notas (P1, P2, T1, T2, Ex, CompL e CompTP) são arredondadas às décimas, exceto a nota final (F) que é arredondada às unidades.
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.