19/04 - Aproximação Arbitrariamente boa para o Problema da Mochila e Uma busca local para o problema do Corte Máximo (que também é uma 1/2-aproximação). Slides
12/04 - Algoritmo Exato para o TSP (Programação Dinâmica) e Algoritmo 1/2-aproximado para Problema da Mochila. Slides
05/04 - Prova que VERTEX-COVER é NP-Completo. Como resolver um problema NP-Difícil? Algoritmo exato para o VERTEX-COVER. Slides
22/03 - Provas que CIRCUIT-SAT, SAT, 3-CNF-SAT e CLICK são NP-Completos. Slides
15/03 - Classes de Complexidade, P, NP, NP-Difícil e NP-Completo. Slides
Avaliação:
Pt média da prova do bimestre t de 0 a 10.
Tt média do bimestre t das notas nos trabálhos práticos
Nota do bimestre t, Nt = Tt x Pt / 10
Comprometimento: Se em todas as aulas a presença de alunos superar 50%, Pt = 10 para todos.
Bônus: até 1 ponto pode ser somado em Nt por participações excepcionais.
Média parcial M = (N1 + N2) / 2
Se frequência menor que 75% o aluno reprovou-se.
Senão se, M maior ou igual a 6, o aluno aprovou-se.
Senão se, M menor que 6, o aluno faz uma Sub que substitui a menor entre N1 e N2.
Em caso de plágio, fraude, tentativa de burlar os sistemas, nota zero será aplicado na disciplina a todos os envolvidos e estarão automaticamente reprovado.
Referências bibliográficas e Material de Apoio:
004.421 / C811a - CORMEN, Thomas H et al. Algoritmos: teoria e prática. 3a ed. Rio de Janeiro: Campus, 2012. 926 p. ISBN 978-85-352-3699-6.
004.421 / D229a - DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos; VAZIRANI, Umesh. Algoritmos. São Paulo: McGraw Hill, 2009. 320 p. ISBN 978-85-7726-032-4.
