Otimização Combinatória
Código
10809
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Matemática
Créditos
6.0
Professor responsável
Isabel Cristina Silva Correia
Horas semanais
4
Língua de ensino
Português
Objectivos
(i) Compreensão dos conceitos fundamentais de grafos, poliedros e matróides
(ii) Desenvolvimento da capacidade de concepção de algoritmos
(iii) Desenvolvimento da capacidade de formulação de problemas
(iv) Amadurecimento da formação matemática
Pré-requisitos
Os alunos devem ter conhecimentos de Programação Linear e alguma capacidade de conceber e implementar algoritmos.
Conteúdo
1. Grafos
2. Modelação com variáveis binárias
3. Programação inteira
4. Árvores
5. Caminhos mais curtos
6. Emparelhamentos
7. Fluxos
8. Matroides
9. Complexidade computacional
10. Algoritmos aproximativos
Bibliografia
L.A. Wolsey, Integer Programming, Wiley, 1998.
D.B. West, Introduction to Graph Theory, Prentice Hall, 2001
A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, Springer, 2003
A. Schrijver, A Course in Combinatorial Optimization, 2013
B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 2008
rithms