Docente: Rui Carpentier (rcarpent@math.ist.utl.pt)
Avisos
A pauta com as notas do segundo exame e notas finais pode ser consultada aqui. Quem tiver algo a reclamar pode fazer-lo até o início Fevereiro.
As notas do primeiro exame (enunciado,resolução) podem ser consultadas aqui, aqueles cuja nota não aparece devem falar com o docente. Quem quiser ver o exame pode solicitar tal a qualquer altura.
Em baixo encontra-se o enunciado da ficha 7 que serve para cobrir a restante matéria da cadeira.
No exercício 3(a) da ficha 1, o conjunto C-p é o transladado de C por -p e não o conjunto C excepto o ponto p. Ou seja C-p:={x-p: x ε C}.
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: Optimização em grafos (caminho mais curto, árvore geradora mínima, fluxos em grafos). Coloração de grafos. Matroides.
Bibliografia
Apontamentos das aulas teóricas (em construção ao longo do semestre,
comunicação de gralhas ou erros são bem-vindas).
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.
Linear and nonlinear programming, D.G. Luenberger,2nd ed. 2003, Kluwer Academic Publishers.
Convex Polytopes, B. Grünbaum, 2nd ed. 2003, 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.4 NC + 0.6 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 9 de Janeiro de 2010 às 9h00m na sala V1.07.
O exame de segunda época realiza-se dia 23 de Janeiro de 2010 às 9h00m na sala P12.
Para a avaliação
contínua conta a média das 5 melhores notas das 6
fichas (quinzenais e com prazo de entrega semanal) realizadas
ao longo do semestre.
Cada ficha é cotada de 0 a 20 valores (caso o aluno
não entregue a resolução, a nota da ficha será
zero).
Datas de entrega do enunciado das fichas:.
ficha 1 (Resolução do problema 3 da Ficha 1): 25 de Setembro;
ficha 2: 9 de Outubro;
ficha 3: 23 de Outubro;
ficha 4: 6 de Novembro;
ficha 5: 20 de Novembro;
ficha 6: 4 de Dezembro.
ficha 7: ficha de preparação (serve como elemento de estudo para a matéria da cadeira que não foi coberta pelas fichas de avaliação).
Pauta da avaliação contínua A entrega dos enunciados das fichas será
feita na aula práctica e os alunos devem entregar as suas resoluções até
ao início da aula teórica de sexta da semana seguinte.