Licenciatura: Matemática

Ano Lectivo: 2002/03

Programa:

1. Formulações algébricas de problemas de Optimização Discreta.
2. Relaxações (lineares, combinatórias e Lagrangeanas; dualidade em Optimização Discreta).
3. Conjuntos Poliédricos Integrais (integralidade dual total e unimodularidade total).
4. Submodularidade (algoritmo guloso e matroides).
5. Emparelhamentos e Afectação (algoritmos para os emparelhamentos de cardinalidade máxima e de peso máximo e para o problema da afectação).
6. Introdução à Programação Dinâmica (aplicação aos problemas de loteamento e da mochila).
7. Algoritmos Branch and Bound e de Planos Cortantes.