Otimização Combinatória

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.

Caracterização geral

Código

10809

Créditos

6.0

Professor responsável

Isabel Cristina Silva Correia

Horas

Semanais - 4

Totais - 56

Idioma de ensino

Português

Pré-requisitos

Os alunos devem ter conhecimentos de Programação Linear e alguma capacidade de conceber e implementar algoritmos.

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

Método de ensino

Nesta disciplina as aulas são teórico-práticas.

Nas aulas expõem-se os conceitos teóricos e efectuam-se algumas demonstrações, utilizando-se o quadro e o projetor, e são resolvidos alguns exercícios e problemas em regime de trabalho individual com algumas exemplificações pelo docente.

Parte do estudo é feito autonomamente pelo aluno, individualmente e em grupo, com recurso a suporte bibliográfico, e com o apoio do docente nas aulas e em horários pré-estabelecidos para esclarecimento de dúvidas.

Método de avaliação

Devido à situação pandémica não serão contabilizadas as presenças dos alunos nas aulas. 

Esta unidade curricular terá avaliação contínua, constituída por 2 Testes e um Exame em Época de Recurso.

Método de avaliação

1) A avaliação contínua compreende a realização de 2 testes com cotação T1 e T2 tais que T1+T2=20. Assim a classificação final de um aluno em época normal é o resultado da soma das classificações dos 2 testes.

2) Um aluno reprovado na avaliação contínua pode realizar o exame de recurso sendo a classificação final a obtida no exame de recurso.

3) Um aluno aprovado em avaliação contínua pode realizar o exame de recurso para tentar melhorar a sua classificação. Neste caso deverá inscrever-se para melhoria na Repartição Académica.

4) A obtenção de uma classificação final superior a 17 valores nesta unidade curricular requer a realização de uma prova complementar.

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

Cursos

Cursos onde a unidade curricular é leccionada: