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 - 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 3 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 2018/2019 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: