Complexidade de Algoritmos - 2018/3
(PESC: COS841; PPGI: MAB704)

Mestrado e Doutorado

Professores

Márcia R. Cerioli
Fábio Botler
Vinícius Gusmão Pereira de Sá

Monitores

Tanilson Dias dos Santos - tanilsondiasdossantos@gmail.com

Moysés da Silva Sampaio Júnior - moysessj@cos.ufrj.br

Horário e local das aulas

Início: 10/09/2018
2a. e 4a., 10-12h, Sala H324-A

Provas

P1: 10/10/2018
P2: 12/12/2018

Cronograma previsto

Aulas da professora Márcia: 10/09 à 03/10

Aulas do professor Fábio: 15/10 à 31/10

Aulas do professor Vinícius: 05/11 à 05/12

Listas

Lista 1 : Entregar até 01/10
Lista 2 : Entregar até 15/10
Lista 3 : Entregar até 24/10
Lista 4 : Entregar até 07/11

Informações interessantes

Palestra da professora Celina sobre o problema do milênio.

Intratabilidade e Otimização

Bibliografia

• CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Introduction to Algorithms. 3rd edition. MIT Press, 2009.
• KLEINBERG, J.; TARDOS, E. Algorithm Design. Addison-Wesley, 2005.
• DASGUPTA, S.; PAPADIMITRIOU, C., VAZIRANI, U. Algorithms. McGraw-Hill, 2006.
• SZWARCFITER, J. L. Teoria Computacional de Grafos. Elsevier, 2018.
• GAREY, M. R.; JOHNSON, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
• JOHNSON, D. S. NP-Completeness Columns.
• PAPADIMITRIOU, C. H. Computational Complexity. Addison-Wesley, 1994.
• PAPADIMITRIOU, C. H.; STEIGLITZ, K. Combinatorial Optimization: Algorithms and Complexity. Dover, 1998.
• CARVALHO, M. H.; CERIOLI, M. R.; DAHAB, R.;FEOFILOFF, P.; FERNANDES,
  C. H.; FERREIRA, C. E.; GUIMARÃES, K. S.;MIYAZAWA, F. K.; PINA Jr., J. C. de; SOARES, J. A. R.; WAKABAYASHI, Y.
  Uma Introdução Sucinta a Algoritmos de Aproximação. IMPA, 2001.
• VAZIRANI, V. V. Aproximation Algorithms. Springer-Verlag, 2001.
• FIGUEIREDO, C. M. H.; FONSECA, G. D.; LEMOS, M. J. M. S.; SÁ, V. G. P. Uma Introdução aos Algoritmos Randomizados. IMPA, 2007.
• MITZENMACHER, M.; UPFAL, E. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
• MOTWANI, R.; RAGHAVAN, P. Randomized Algorithms. Cambridge University Press, 1995.
• WINGDERSON, A. Mathematics and Computation. Acesse aqui.