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
Jorge Orestes Cerdeira
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
Frequência: Obtida com pelo menos 2/3 de presenças nas aulas práticas.
Avaliação:
Contínua:
Dois testes a realizar durante o período letivo, cada um com a cotação de 5 valores. Elaboração, durante o período letivo, de um relatório escrito, sobre um tópico a definir, e apresentação oral do trabalho, com a cotação de 10 valores.
Considera-se aprovado o aluno com frequência e soma das classificações obtidas nos três elementos de avaliação >=10. A classificação final será o valor dessa soma.
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 que obtenha frequência e nota de exame final >=10 valores.