Otimização Combinatória
Objetivos
(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 - 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
Esta unidade curricular terá avaliação contínua, constituída por 2 Testes e um trabalho de grupo, e um Exame em Época de Recurso.
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 lecionadas.
2) Os alunos que tenham obtido frequência no ano letivo 2017/2018 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 e um trabalho de grupo. Cada teste terá uma cotação de 8 valores e o trabalho 4 valores. A classificação final de um aluno em época normal é o resultado da soma das classificações dos 2 testes e da classificação do trabalho.
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