Docente: Rui Carpentier (rcarpent@math.ist.utl.pt)
Avisos
ERRATA: No problema 3 da ficha 4 onde se lê - "Use o teorema da dualidade para determinar as soluções dos seguintes problemas de programação linear" - deve-se ler - "Use o teorema da dualidade para determinar o valor optimal para cada um dos seguintes problemas de programação linear"
Na última aula práctica (19/9/2008) foi detectada uma gralha na resolução do último exercício, a resolução correcta pode ser vista aqui.
Programa
Elementos de geometria convexa e programação linear: Poliedros e polítopos, lema de Farkas, teorema da dualidade, método do simplexo.
Teoria dos Grafos: Coloração de grafos. Matroides. Optimização em grafos.
Bibliografia
A Course in Combinatorial Optimization, Alexander Schrijver
An introduction to convexity, polyhedral theory and Combinatorial Optimization, Geir Dahl
Geometric Algorithms and Combinatorial Optimization, M. Grotschel, L. Lovasz, A. Schrijver, 1993, Springer Verlag.
The Four-Color Theorem: Assaults and Conquest, T.L. Saaty and P.C. Kainen, Dover Publications, New York, 1977.
Combinatorial Theory, M. Aigner, 1997, Springer Verlag.
Avaliação de Conhecimentos:
A nota final da
cadeira é um inteiro de 0 a 20. Um aluno fica aprovado se a sua nota
final for maior ou igual a 10. A nota final é calculada a partir da nota
das provas escritas (NE) e da nota da avaliação
contínua (NC) de acordo com a seguinte fórmula:
Nota final = 0.5 NC + 0.5 NE
Há dois exames finais com a
duração de 3 horas (um em cada época de exames).
O exame de primeira época realiza-se dia 19 de Janeiro às 17h00m na sala P12.
O exame de segunda época realiza-se dia 4 de Fevereiro às 17h00m na sala V1.25.
Avaliação
contínua
Para a avaliação
contínua conta a média das 8 melhores notas das fichas semanais realizadas
ao longo do semestre (em princípio serão entre 11 a 13 fichas).
Cada ficha é cotada de 0 a 20 valores (caso o aluno
não entregue a resolução, a nota da ficha será
zero).
Ficha 2, (Resolução do problema 4 da Ficha 2)
Confiram as vossas médias das 8 melhores fichas (AC).
Se alguem tem algo a reclamar faça-o até a próxima sexta dia 13 (altura em que lançarei as notas na secretaria).
Obs.: Apesar de algumas questões do exame tipo coincidirem com exercícios das fichas o mesmo não irá acontecer no exame a valer. Servem apenas para mostrar o tipo de perguntas e a matéria sobre a qual incide o exame (excepto o exercício 7 que pode incidir sobre qualquer parte da matéria). O exame tipo tem uma pergunta a mais em relação aos exames de 19/01 e 04/02.
Horário de dúvidas: