Análise e Projeto de Algoritmos II - Turma 01 - 2022s1

Informações:

• Prof: Pedro H. D. B. Hokama - IMC
• Aulas: Terças 15:45 até 18:30 na sala B4213, atendimento a combinar.

Noticias:

1. 02/08 - Atualizado as notas.
2. 29/07 - Atualizado as notas.
3. 29/07 - Resultado do Projeto.
4. 25/07 - Resultado do Aquecimento do Projeto.
5. 21/06 - Divulgado enunciado do Projeto.
6. 21/06 - Resultado do Trabalho 01.
7. 14/06 - A aula de 14/06 será no LDC1 no IMC.
8. 04/06 - Resultado do Aquecimento do Trabalho 01.
9. 16/03 - Página da disciplina no Ar

Aulas:

• 19/07 - Projeto. Código feito em aula: bnb_simples.c
• 12/07 - Programação Por Restrições. Slides
• 05/07 - Programação Linear Inteira. Slides
• 28/06 - Programação Linear. Slides
• 21/06 - Projeto
• 15/06 - Limitantes e Branch-and-Bound. Slides Problema da Virtualização de Máquinas
• 07/06 - Fundamentos de Criptografia. Algoritmo RSA. Slides
• 31/05 - Trabalho 01.
• 24/05 - Busca Local para o problema do Corte Máximo.
• 17/05 - Heurística Gulosa, Algoritmo de 1/2 aproximação e Algoritmo de (1 - ε) aproximação para o Problema da Mochila. Slides
• 10/05 - Revisão.
• 03/05 - TSP e SUBSET-SUM. Algoritmos Exatos para VERTEX-COVER e TSP. Slides
• 26/04 - SAT, 3-CNF-SAT, VERTEX-COVER e HAM-CYCLE. Slides
• 19/04 - Classes de Complexidade P, NP e NP-Completo. CIRCUIT-SAT, CLICK. Slides
• 12/04 - Algoritmo de Jonhson para Caminhos mínimos de única fonte na presença de pesos negativos. Introdução à Classes de Complexidade. Slides
• 05/04 - Algoritmo de Bellmond-Ford para Caminhos mínimos de única fonte na presença de pesos negativos. Slides
• 29/03 - Apresentação, Programação Dinâmica, Problema da Mochila. Slides

Avaliação:

• Sub: 02/08/2022, a prova será sobre um dentre os seguintes tópicos (a ser sorteado):
• Programação Dinâmica.
• Reduções e NP-Completude.
• Programação Linear e Programação Linear Inteira.
• Projeto - primeira entrega 10/07 (não obrigatória), segunda entrega 17/07 (obrigatória), entrega final 27/07, tudo no run.codes.
• Enunciado: projeto.pdf
• Codigo: codigo.zip você deve alterar e submeter só o resolvedor.c
• Para testar o jogo: Flood It!
• Casos de teste: casos_testes2.zip
• entrada01.txt     entrada01.png
• entrada02.txt     entrada02.png
• entrada03.txt     entrada03.png
• entrada04.txt     entrada04.png
• entrada05.txt     entrada05.png
• entrada06.txt     entrada06.png
• Trabalho 01 - primeira entrega 02/06, entrega final 09/06:
• Cadastre seu grupo (mesmo que com 1 pessoa) nesse formulário até dia 28/05 (precisa de uma conta @unifei.edu.br
• Enunciado: trabalho01.pdf
• Codigo: codigo.zip você deve alterar e submeter só o resolvedor.c
• Para testar o jogo: Flood It!
• Casos de teste: casos_teste.zip
• entrada01.txt     entrada01.png
• entrada02.txt     entrada02.png
• entrada03.txt     entrada03.png
• entrada04.txt     entrada04.png
• entrada05.txt     entrada05.png

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.
• Curso Algorithms 1 de Tim Roughgarden (Stanford)
• Curso Algorithms 2 de Tim Roughgarden (Stanford)