Complexidade de Algoritmos - 2023/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: 26/09/2023
terças e quintas, 13h-15h

Monitores

Diego Amaro Ferraz da Costa

Guilherme Adamatti Bridi

Oscar Martins Wanderley Filho

Grupo de Whatsapp

Listas

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

• Lista 1: Entregar até 18/10/2023 - Gabarito
• Lista 2: Entregar até 10/11/2023 - Gabarito
• Lista 3: Entregar até 06/12/2023

Provas

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

• Prova 1: Entregar até 28/11/2023 Gabarito
  
• Prova 2: Entregar até P2/P2/2023 Gabarito

Cronograma previsto

Setembro
26	Apresentação do curso;
26	Notação assintótica; Relações de recorrência; Teorema Mestre. - notas
28	Lower bounds (árvore de decisão e método do adversário), ordenação em tempo linear - notas
Outubro
3	Dividir e conquistar, quicksort - notas
5	Programação dinâmica - notas
10	Algoritmos gulosos - notas
17	Backtracking (e/ou mais exemplos das técnicas anteriores) - notas
19	Problemas de decisão. Problemas de otimização. - notas
24	Certificados. A Classe NP. Transformações polinomiais. problemas NP-Completos - notas
26 31	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 1 notas 2
31	Um pouco de probabilidade. Análise probabilística e Algoritmos randomizados. - notas
Novembro
7	Não haverá aula
9	Algoritmos randomizados.- notas
14	Métodos probabilísticos.- notas reducao-CH-SAT
16	Revisão para P1
21	P1
23	Correção P1
28	Algoritmos aproximativos e razão de aproximação. Notas
30	Cobertura de vértices e cobertura de conjuntos. Notas
Dezembro
5	Esquemas de aproximação polinomial para o problema da mochila. Notas,
7	Esquemas de aproximação polinomial para o problema do caixeiro viajante. Notas
12 - 14	Complexidade Parametrizada. Notas 1, Notas 2
19	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..