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é 12 de Fevereiro.
As notas do primeiro exame (enunciado,resolução) podem ser consultadas aqui. Quem quiser ver o exame pode solicitar tal a qualquer altura.
A data da última ficha foi alterada o enunciado será posto nesta página dia 7 de Dezembro e os alunos tem até dia 15 de Dezembro para entregar as suas resoluções (nao haverá realização da ficha na aula).
A definição 3.44 dos apontamentos deste ano foi modificada.
Estarei disponível para tirar dúvidas em qualquer altura que esteja no gabinete (piso 4) sem nada prioritário para fazer, podendo garantir que segundas e quartas entre as 16h00m e as 18h00m estarei nessas condições (salvo raras excepções).
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, versão actualizada (em construção ao longo do semestre,
comunicação de gralhas ou erros são bem-vindas). Nota: não foi dada nas aulas a matéria referente ao último capítulo (matróides) e como é tal, esta não será avaliada em exame.
Apontamentos das aulas teóricas (versão de 2009).
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 e tiver pelo menos 7 valores na nota de exame. A nota final é calculada a partir da nota
de exame (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). Conta a melhor nota dos dois.
O exame de primeira época realiza-se dia 21 de Janeiro de 2011 às 8h00m na sala PA2.
O exame de segunda época realiza-se dia 1 de Fevereiro de 2011 às 15h00m na sala V1.11.
Para a avaliação
contínua conta a média das 5 melhores notas das 6
fichas realizadas
ao longo do semestre. O enunciado das fichas é entregue uma semana antes
de serem feitas presencialmente no final da aula práctica. 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: Entrega do enunciado a 24 de Setembro; realização a 1 de Outubro.
ficha 2: Entrega do enunciado a 8 de Outubro; realização a 15 de Outubro.
ficha 3: Entrega do enunciado a 22 de Outubro; realização a 29 de Outubro (Nota: a duração da realização desta ficha é de 50 minutos em vez dos usuais 30 minutos, assim começará a ser feita 50 minutos antes do fim da aula práctica).
Resolução do problema 3 da ficha 3
ficha 4: Entrega do enunciado a 5 de Novembro; realização a 12 de Novembro.
ficha 5: Entrega do enunciado a 19 de Novembro; realização a 26 de Novembro (Nota: a duração da realização desta ficha é de 50 minutos em vez dos usuais 30 minutos, assim começará a ser feita 50 minutos antes do fim da aula práctica).
ficha 6: Entrega do enunciado a 7 de Dezembro; prazo de entrega a 15 de Dezembro.
Notas das fichas Páginas da cadeira em anos anteriores