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

Mestrado e Doutorado

Professores

Celina Miraglia Herrera de Figueiredo
Fábio Botler
Vinícius Gusmão Pereira de Sá

Ementa

Algoritmos. Notação O, Ω, θ. Problemas em P. Programação dinâmica. Método Guloso. Backtracking. Limites inferiores. Algoritmos polinomiais. Problemas de decisão. Problemas em NP. Certificados. Classe NP. NP-completo. NP-completo Forte. Algoritmos aproximativos. Problemas de otimização. Esquemas de aproximação em tempo polinomial. Max SNP-completo.

Horário e local das aulas

Início: 27/09/2019
6a., 9-13h, H-318B

Monitores

Judismar Arpini Junior - jj.arpini@gmail.com

Wanderson Douglas Lomenha Pereira - wlomenha@cos.ufrj.br

Grupo de WhatsApp

Horário e local da monitoria

Quartas-feiras das 10h às 12h
Sala H318-B

Provas

P1: 01/11/2019
P2: 13/12/2018

Vistas de prova

P1: 04/12/2019, 10h, sala H318B
P2: 18/12/2019, 10h, sala H318B

Cronograma previsto

Setembro
27	Notação O, Ω, θ. Algoritmos polinomiais. A Classe P.
Outubro
4	Programação dinâmica. Método Guloso.
11	Problemas de decisão. Problemas de otimização. Algs. eficientes, probs. tratáveis/intratáveis, probs. algorímicos, codificações, tipos de problemas. A Classe P, probs. aparentemente difíceis.
18	Certificados. A Classe NP. A classe NP, P versus NP, complementos de problemas. Transformações polinomiais, alguns problemas NP-Completos.
25	Reduções. NP-Completo. NP-Completo forte. Reduções de Karp X Reduções de Cook, restrições e extensões de problemas. Algoritmos superpolinomiais, isomorfismo de grafos, algoritmos pseudopolinomiais, problemas numéricos.
Novembro
1	P1
8	Backtracking. Limites inferiores.
15	Feriado: Proclamação da República
22	Algoritmos aproximativos
29	Esquemas de aproximação polinomial.
Dezembro
4	Vista da P1, 10h, sala H318B
6	Algoritmos randomizados.
13	P2
18	Vista da P2, 10h, sala H318B

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é 11/10/2019
• Lista 2: Entregar até 18/10/2019
• Lista 3: Entregar até 01/11/2019
• Lista 4: Entregar até 22/11/2019
• Lista 5: Entregar até 13/12/2019

Informações interessantes

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

Intratabilidade e Otimização

FEOFILOFF, P. O que é uma prova?

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..