Complexidade de Algoritmos - 2021/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: 17/11/2021
segundas e quartas, 10h-12h, Google Meet

Monitores

Mariana Martins Ferreira da Cruz

Rafael Almeida da Costa Schneider

Grupo de Whatsapp

Listas

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

• Lista 1: Entregar até 08/12/2021
• Lista 2: Entregar até 17/01/2021
• Lista 3: Entregar até 02/02/2021

Provas

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

• Prova 1: Entregar até 17/12/2021 Gabarito
  
• Prova 2: Entregar até 18/02/2022 Gabarito

Cronograma previsto

Novembro
17	Apresentação do curso;
17	Notação assintótica; Relações de recorrência; Teorema Mestre. - notas
22	Lower bounds (árvore de decisão e método do adversário), ordenação em tempo linear - notas
24	Dividir e conquistar, quicksort - notas
29	Programação dinâmica - notas
Dezembro
1	Algoritmos gulosos - notas
6	Backtracking (e/ou mais exemplos das técnicas anteriores) - notas
8	Problemas de decisão. Problemas de otimização. - notas
10 - 17	P1
20	Certificados. A Classe NP. Transformações polinomiais. problemas NP-Completos - notas
Janeiro
5	Reduções de Karp X Reduções de Cook, restrições e extensões de problemas. Algoritmos superpolinomiais, isomorfismo de grafos. - notas 1 notas 2
10	Algoritmos pseudopolinomiais, problemas numéricos - notas
10	Um pouco de probabilidade - notas
12	Análise probabilística e Algoritmos randomizados. - notas 1 notas 2
17	Algoritmos randomizados.- notas
19	Métodos probabilísticos.- notas reducao-CH-SAT
24	Algoritmos aproximativos e razão de aproximação. Notas
26	Cobertura de vértices e cobertura de conjuntos. Notas
31	Esquemas de aproximação polinomial para o problema da mochila. Notas,
Fevereiro
2	Esquemas de aproximação polinomial para o problema do caixeiro viajante. Notas
7 - 9	Complexidade Parametrizada. Notas 1, Notas 2
11 - 18	P2

Informações interessantes

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

Intratabilidade e Otimização

FEOFILOFF, P. O que é uma prova?

Prof. Uéverton dos Santos Souza - Algoritmos Parametrizados

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