Otimização (CI-1238)

Professor: Murilo V. G. da Silva - murilo@inf.ufpr.br

Data da primeira prova: ??/??/2025
Data da segunda prova: ??/??/2025
Data da prova final: ??/??/2025

Avaliação: duas provas (2/3) + um trabalho (1/3)

INTRODUÇÃO À OTIMIZAÇÃO
Leituras: [PAP98: sec 1.1 e 1.2] [KS99: sec. 1.1] [KT05: cap. 1]
Cronograma:
??/?? -- Apresentação do curso e conceitos preliminares
??/?? -- Problemas otimização e espaço de soluções de problemas
??/?? -- Espaço de soluções de problemas

PROGRAMAÇÃO LINEAR - MODELAGEM
Leituras: [MAT07: sec 1.1, sec 2.1-4 e 2.7]
Cronograma:
??/?? -- Introdução à Programação Linear
??/?? -- Programação Linear Inteira

PROGRAMAÇÃO LINEAR - ALGORITMO SIMPLEX
Leituras: [MAT07: sec. 4.1, 4.1, 4.4 e cap. 5]
Cronograma:
??/?? -- Formas equacionais e soluções básicas
??/?? -- Algoritmo Simplex
??/?? -- Algoritmo Simplex (cont.)
??/?? -- Dualidade em Programação Linear
??/?? -- Dualidade em Programação Linear (cont.)

??/?? -- Revisão
??/?? -- PROVA 1

TÉCNICAS PARA PROJETO DE ALGORITMOS
Leituras: [KS99: cap 1-4][CLSR: cap. 15]
Cronograma:
??/?? -- Enumeração
??/?? -- Enumeração (cont.)
??/?? -- Backtraking
??/?? -- Branch-and-Bound
??/?? -- Branch-and-Bound (cont.)
??/?? -- PD e Algoritmos Gulosos
??/?? -- PD e Algoritmos Gulosos (cont.)
??/?? -- PD e Algoritmos Gulosos (cont.)

??/?? -- Revisão
??/?? -- PROVA 2
??/?? -- PROVA FINAL

Bibliografia

[MAT07] MATOUSEK, JIRI; GARTNER, BERND. Understanding and Using Linear Programing , Springer, 2007.

[PAP98] PAPADIMITRIOU, CHRISTOS; STEIGLIZ, KENETH. Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.

[KS99] KREHER, DONALD; STINSON, DOUGLAS. Combinatorial Algorithms: Generation, Enumeration, and Search , CRC Press, 1999.

[KT05] KLEIBERG, JON; TARDOS, EVA. Algorithm Design , Pearson, 2005

[DPV06] DASGUPT, SANJOY; PAPADIMITRIOU, CHRISTOS; VAZIRANI, UMESH. Algorithms , McGraw-Hill, 2006

[CLRS09] CORMEN, THOMAS; LEISERSON, CHARLES; RIVEST, RONALD; STEIN, CLIFFORD. Introduction to Algorithms , MIT Press, 2009

Lista de exercícios: [aqui]