Tópicos de Otimização Combinatória

Caracterização geral

Pré-requisitos

A disponibilizar brevemente

Bibliografia

B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 2012.

L. Lovász and M.D. Plummer, Matching Theory, North-Holland Mathematics Studies, 1986.

A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, Springer, 2003.

A. Schrijver, A Course in Combinatorial Optimization, 2013 available from http://homepages.cwi.nl/~lex/files/dict.pdf

D.B. West, Introduction to Graph Theory, Prentice Hall, 2001.

Método de ensino

A uc funciona em aulas teórico-práticas, onde se apresentam os conceitos teóricos e se efectuam demonstrações de alguns resultados e onde são resolvidos e discutidos exercícios propostos; estudo fora das salas de aula, onde o aluno, com recurso ao material disponibilizado e com o apoio do docente, nas aulas e em períodos de atendimento pré-estabelecidos, assimila a matéria teórica e procura resolver os exercícios sugeridos para realizar em ambiente não presencial.

Durante o período letivo será realizado um teste e, elaborado e apresentado oralmente, um relatório escrito sobre um assunto a definir. O aluno pode também optar por realizar um exame final.

Método de avaliação

Durante o período letivo será realizado um teste e, elaborado e apresentado oralmente, um relatório escrito sobre um assunto a definir. O aluno pode também optar por realizar um exame final.

Conteúdo

1. Generalidades sobre grafos;

2. Poliedros

3. Emparelhamentos e coberturas em grafos bipartidos

4. Fluxos

5. Matroides

6. Complexidade computacional

7. Programação linear inteira e matrizes totalmente unimodulares

Cursos

Cursos onde a unidade curricular é leccionada: