OTIMIZAÇÃO COMBINATÓRIA
Algorithms Design. Tardos & Kleinberg
Network Flows. Ahuja, Magnanti & Orlin
Introduction to Algorithms. Cormen, Leiserson and Rivest and Cliff Stein
Approximation Algorithms. V. Vazirani
Randomized Algorithms. R. Motwani and P. Raghavan
Introduction to Linear Optimization. D. Bertsimas and J. Tsitsiklis
Probability and Computing. M. Mitzenmacher and E. Upfal
- 0.4*P1+0.4*P2+0.2*Trabalho
Tópicos em ordem cronológica. (sujeito a atualizações)
Fluxo em Redes (2.5 aulas)
Cap 7 Algorithms Design e Cap 3 e 9 Network Flows.
Programação Linear (1 aula)
Cap 3 e 4, Introduction to Linear Optimization.
Cap 29, Introduction to Algorithms.
Aleatorização (2.5 aulas)
Cap 13 Algorithms Design e Cap 1,3,4 e 5 Randomized Algorithms.
Algoritmos Paramétricos
Cap 11 Algorithms Design
Algoritmos de Aproximação:
Cap 13 Algorithms Design; Cap 2,3,16,17 Approximation Algorithms; Cap 35 Introduction to Algorithms
Listas
Fluxo em Redes
Cap 7 de Tardos&Kleinberg - 3 -5 - 7 - 10 -12 - 15 - 18 -22 -29 - 42 (a). Tendo tempo recomendo fazer os demais
Algoritmos Aleatorizados
Cap 13 de Tardos&Kleinberg 1,2,4,6,7,9,10,11,12,13,15,17
Análise Amortizada
Cap 17 do Cormen, 17-1-1, 17-1-2, 17-1-3, 17-3-2, 17-3-3, Problemas 17-2, 17-1, 17-3
Algortimos Paramétricos
Cap 10 de Tardos&Kleinberg 1,2,3,5(a),9
Algoritmos de Aproximação
Cap 11 de Tardos&Kleinberg 1-11, exceto o exercício 4
Datas dos Trbalhos
Cadeias de Markov
Daniel e Thuener, 10/11
Sugestões de temas para trabalhos
Algoritmos polinomiais para fluxo máximo em redes
Cap 7, Network Flows. Ahuja, Magnanti & Orlin
Cadeias de Markov
Cap 6, Randomized Algorithms. R. Motwani and P. Raghavan
Cap 7,11 Probability and Computing.
O método Probabilístico
Cap 5, Randomized Algorithms. R. Motwani and P. Raghavan
Splay Trees
Sleator, Daniel D. & Tarjan, Robert E. (1985), "Self-Adjusting Binary Search Trees", Journal of the ACM 32(3): pp. 652-686, <http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf>
Dynamic Optimality–-Almost
(Erik Demaine, Dion Harmon, John Iacono,
and Mihai Pǎtraşcu)
Randomized Data Structures
Cap 8, Randomized Algorithms
Geometric Algorithms
Cap 9, Randomized Algorithms