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

Mestrado e Doutorado

Nesta página vocês terão todas as informações a respeito do curso, por isso sempre estejam de olho nela.

Programa de Engenharia de Sistemas e Computação, COPPE, UFRJ
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/12/2021
segundas e quartas, 10h-12h,

Monitores

Mariana Martins Ferreira da Cruz
Rafael Almeida da Costa Schneider

Grupo de Telegram

Listas

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

Provas

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


Cronograma previsto

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


Informações interessantes

Palestra da professora Celina sobre o problema do milênio.
Intratabilidade e Otimização
FEOFILOFF, P. O que é uma prova?

Bibliografia

Edições anteriores deste curso

2020/3 2019/3 2018/3 2017/3