Guia de Cursos

Queres conhecer a oferta de cursos da NOVA, nas áreas das licenciaturas, mestrados e doutoramentos?
No nosso Guia de Cursos encontras informação útil sobre Faculdades, Institutos e Escolas.
Podes ainda aceder a informações complementares necessárias a uma completa integração.

saber mais Guia de Cursos

Faculdade de Ciências e Tecnologia

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

Português

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.

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.

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.

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

Cursos