| MC558 A | Proj. Análise Algoritmos II - 2o.sem/2012 - Instrutor: João Meidanis | |
| C = Cormen et al., Introduction to Algorithms, 3a. edição, 2009 | ||
| W = West, Introduction to Graph Theory, 2a. edição, 2001 | ||
| S/Q | Data | Atividade |
| Mon | 30/07/2012 | |
| Wed | 01/08/2012 | Apresentação |
| Mon | 06/08/2012 | Revisão MC458: C1-2-3-4 |
| Wed | 08/08/2012 | Lab: Apresentação (LEMON) |
| Mon | 13/08/2012 | Grafos, matrizes, isomorfismo: W1.1 (14 páginas) |
| Wed | 15/08/2012 | Componentes conexas, bipartidos, eulerianos: W1.2 (12 páginas) |
| Mon | 20/08/2012 | BFS, distâncias: C22.0-1-2 (14 páginas) |
| Wed | 22/08/2012 | Lab 1: Isomorfismo |
| Mon | 27/08/2012 | DFS, ordenação topológica, conexão forte: C22.3-4-5 (14 páginas) |
| Wed | 29/08/2012 | Emparelhamentos bipartidos: W3.1, W3.2 (17 páginas - omitir seções opcionais) |
| Mon | 03/09/2012 | Prova P1 |
| Wed | 05/09/2012 | Árvores geradoras mínimas: C23 (11 páginas) |
| Mon | 10/09/2012 | Caminhos mínimos: C24.0-1-2-3 (18 páginas) |
| Wed | 12/09/2012 | Lab 2: Algoritmo húngaro |
| Mon | 17/09/2012 | Fluxos em redes: C26-0-1-2-3 (24 páginas), W4.3 (apenas apoio) |
| Wed | 19/09/2012 | Coloração de vértices: W5.1 até 5.1.7, 5.12 e 5.13, 5.1.22 só enunciado (4 pág.); W5.2.5 a 5.2.8 (3 pág.); W5.3 até 5.3.7, 5.3.12 e 5.3.13 (2 pág.); W8.1.12 a 8.1.14 (2 pág.) |
| Mon | 24/09/2012 | Planaridade: W6.1 (10 pág.). W6.2 até 6.2.2 só enunciado (2 pág.) |
| Wed | 26/09/2012 | Lab 3: Teste de Planaridade |
| Mon | 01/10/2012 | Teorema das 4 cores: W6.3 (até Coloring planar graphs, 5 pág.); definições de Hamilton cycle (W7.2.1) e Hamilton path (W7.2.15); W7.3 (até Grinberg, 5 pág.) |
| Wed | 03/10/2012 | Coloração de arestas: W7.1 (exceto opcionais, 6 pág.) |
| Mon | 08/10/2012 | Prova P2 |
| Wed | 10/10/2012 | Classes de problemas: C34.0 (6 pág.) |
| Mon | 15/10/2012 | Classe P: C34.1 (7 pág.) |
| Wed | 17/10/2012 | Lab 4: Coloração planar 5 cores |
| Mon | 22/10/2012 | Classe NP: C34.2 (5 pág.) |
| Wed | 24/10/2012 | Reduções: C34.3 (3 pág.); C34.4 (1 pág.) |
| Mon | 29/10/2012 | Primeiro problema NP-completo: C34.3 (7 pág.) |
| Wed | 31/10/2012 | Lab 5: Vizing |
| Mon | 05/11/2012 | Outros problemas NP-completos: C34.4 (6 pág.); C34.5 (5 pág.); Probl. C34-3 (1 pág.) |
| Wed | 07/11/2012 | Revisão geral |
| Mon | 12/11/2012 | Prova P3 |
| Wed | 14/11/2012 | Estudos |
| Mon | 19/11/2012 | Estudos |
| Wed | 21/11/2012 | Estudos |
| Mon | 26/11/2012 | Estudos |
| Wed | 28/11/2012 | Estudos |
| Mon | 03/12/2012 | Semana de estudos |
| Wed | 05/12/2012 | Semana de estudos |
| Mon | 10/12/2012 | Exame |
| Wed | 12/12/2012 | Entrega de notas finais |