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

Manuel Valdemar Cabral Vieira

Horas

Semanais - 4

Totais - 70

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

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

Só os alunos com frequência poderão obter aprovação nesta unidade curricular.

Obtenção de frequência

1) A frequência é concedida a todos os alunos que compareçam em pelo menos 2/3 de todas as aulas leccionadas.

2) Os alunos que tenham obtido frequência no ano lectivo 2019/2020 ou que tenham estatuto de Trabalhador – Estudante estão dispensados da obtenção de frequência no corrente ano letivo.

Método de avaliação

1) A avaliação contínua compreende a realização de 2 testes. Cada teste terá uma cotação de 10 valores. 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) 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: