Otimização Combinatória
Código
10809
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Matemática
Créditos
6.0
Professor responsável
Isabel Cristina Silva Correia
Horas semanais
4
Língua de ensino
Português
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
Pré-requisitos
Os alunos devem ter conhecimentos de Programação Linear e alguma capacidade de conceber e implementar algoritmos.
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
Bibliografia
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 available from http://homepages.cwi.nl/~lex/files/dict.pdf
B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 2008
L.A. Wolsey, Integer Programming, Wiley, 1998.
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
Regras de avaliação.
Frequência: Obtida com pelo menos 2/3 de presenças nas aulas teórico-práticas.
Avaliação:
Por testes:
Três testes a realizar durante o semestre fora do período das aulas. Considera-se aprovado o aluno com frequência e soma das classificações obtidas nos testes >=9.5.
Por exame final:
Só os alunos com frequência podem realizar exame final (ver data no calendário de exames).
Considera-se aprovado o aluno com frequência e nota de exame final >=9.5 valores.
Há defesa de nota (trabalho complementar e/ou prova oral) para classificações superiores a 17.