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

Mestrado e Doutorado

4a-feira, dia 22/11, não haverá aula.

Professores

Celina Miraglia Herrera de Figueiredo
Franklin de Lima Marquezino
Vinícius Gusmão Pereira de Sá

Monitores

Alexandre Santiago de Abreu - santiago@cos.ufrj.br

Alexsander Melo - aamelo@cos.ufrj.br

Horário e local das aulas

Início: 20/09/2017
4a. e 6a., 10-12h, Sala H324-A

Horário e local da monitoria

Toda quarta-feira de 15h às 16h. Sala H318-B (sala de reuniões).

Provas

P1: 18/10/2017 - Teremos aula de dúvidas 4a-feira, dia 11/10.
P2: 13/12/2017

Cronograma previsto

Aulas do professor Franklin: 20/09 à 06/10

Aulas da professora Celina: 20/10 à 10/11

Aulas do professor Vinícius: 17/11 à 06/12

Listas

As listas deverão ser entregues até a data determinada, podem ser enviadas por email, porém é preferível que seja entregue, ainda que posteriormente, também a versão em papel.

• Lista 1: Entregar até 04/10

• Lista 2 (Atualizada em 05/10): Entregar até dia 11/10 aqueles que desejarem ter a correção dos exercícios antes da prova, ou dia 18/10.

• Lista 3: Entregar até 08/11

• Lista 4 : Entregar até 06/12

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. Grafos e Algoritmos Computacionais. Campus, 1988.
• 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.