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

Mestrado e Doutorado

Professores

Celina Miraglia Herrera de Figueiredo
Fábio Botler
Franklin Marquezino

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 randomizados. Algoritmos aproximativos. Problemas de otimização. Esquemas de aproximação em tempo polinomial. Max SNP-completo. Complexidade parametrizada

Horário e local das aulas

Início: 01/02/2021
segundas e quartas, 10h-12h, Google Meet

Monitores

Diego Athayde - diegoathayde@cos.ufrj.br

Luiz Hoffman - hoffmann@cos.ufrj.br

Grupo de Telegram

Cronograma previsto

Fevereiro
1	Apresentação do curso; Notação assintótica; Relações de recorrência; Teorema Mestre. Notas.
3	Lower bounds (árvore de decisão e método do adversário) Notas.
8	Dividir e conquistar; Ordenação em tempo linear Notas.
10	Programação dinâmica Notas.
22	Algoritmos gulosos Notas.
24	Backtracking (e/ou mais exemplos das técnicas anteriores) Notas.
Março
1	Problemas de decisão. Problemas de otimização. Notas
3	Certificados. A Classe NP. Notas
8	Transformações polinomiais. problemas NP-Completos Notas
10	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. Notas
15 - 17	P1
22	Análise probabilística e Algoritmos randomizados. Notas, Quadro
24	Algoritmos randomizados. Notas, Quadro
29	Algoritmos aproximativos e razão de aproximação. Notas
31	Cobertura de vértices e cobertura de conjuntos. Notas
Abril
5	Esquemas de aproximação polinomial para o problema da mochila. Notas 1,
7	Esquemas de aproximação polinomial para o problema do caixeiro viajante. Notas 2
12 - 14	Complexidade Parametrizada. Notas 1, Notas 2
19 - 21	P2

Listas

As listas deverão ser entregues até a data determinada, podem ser enviadas por email.

• Lista 1: Entregar até 14/02/2021
• Lista 2: Entregar até 08/03/2021
• Lista 3: Entregar até 05/04/2021

Provas

As provas deverão ser entregues até a data determinada por email.

• Prova 1: Entregar até 21/03/2021 Gabarito
  
• Prova 2: Entregar até 21/04/2021 Gabarito

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.
• DOS SANTOS, V. F.; SOUZA, U. S..
  Uma introdução à complexidade parametrizada.
• 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..