05/06 - Limitante Primal, Limitante Dual, e Algoritmo de Branch-and-Bound. Slides
29/05 - Revisão
22/05 - Revisão
15/05 - Heurística para o Problema da Mochila, Algoritmo de 1/2-Aproximação para o problema da Mochila, e Algoritmo de (1-epsilon)-Aproximação para o problema da Mochila. Slides
08/05 - Algoritmos Exatos para o VERTEX-COVER e para o TSP. Slides
24/04 - HAM-CYCLE, TSP e SUBSET-SUM são NP-Completos. Slides
10/04 - 3-CNF-SAT, CLICK, SAT e VERTEX-COVER são NP-Completos. Slides
03/04 - Classes de Complexidade P, NP, NP-Difícil e NP-Completo. Um primeiro problema NP-Completo: Satisfabilidade de Circuitos (CIRCUIT-SAT). Slides
20/03 - Caminhos Mínimos entre todos os pares de vértices: Algoritmo de Floyd-Warshall e Algoritmo de Johnson. Slides
13/03 - Apresentação, Programação Dinâmica, Problema da Mochila. Algoritmo de Bellmond-Ford para Caminhos mínimos de única fonte na presença de pesos negativos. Slides
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.
