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
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: