Algoritmos em Grafos

MAC0328 | Aulas | Tarefas | Notas

MAC0328 (2016): Aulas e Provas

Este calendário de aulas e provas está sujeito a muitas alterações e ajustes.

Aula 1 (3/8, quarta)

• Apresentação de MAC0328.
• Regras do jogo.
• Dúvidas, perguntas e respostas.
• Minhas notas de aula.
• Estude Grafos e digrafos.
• Tarefa A, para 5/8, sexta-feira, até 10h00m.

Aula 2 (5/8, sexta)

• Estruturas de dados para digrafos.
• Digrafo e grafos aleatórios.
• Tarefa B, para 10/8, quarta-feira, até 7h00m.

Aula 3 (10/8, quarta)

• Caminhos e ciclos em digrafos.
• Numeração de vértices e ordenamento de vértices.
• Alguns tipos de digrafos.
• Lista de exercícios E03.

Aula 4 (12/8, sexta)

• Um programa não é uma coisa suja que você escreve apenas para que o computador faça o que você quer. Um programa é uma peça de literatura (como um conto ou uma reportagem) que você escreve com carinho e cuidado para que outras pessoas leiam com prazer.
• Existência de caminho.
• Busca em profundidade (DFS).
• Floresta de busca em profundidade.
• Lista de exercícios E04.
• Tarefa C, para 17/8, quarta-feira, até 7h00m.

Aula 5 (17/8, quarta)

• Pós-ordem.
• Componentes conexas de grafos.
• Observações sobre a tarefa B.
• Lista de exercícios E05.
• Tarefa D, para 19/8, sexta-feira, até 9h55m.

Aula 6 (19/8, sexta)

• Ciclos versus DAGs.
• Solução da tarefa D.
• Lista de exercícios E06.
• Comentários sobre o exercício E05 da última aula.
• Comentários sobre a tarefa C.

Aula 7 (24/8, quarta)

• Ciclos versus DAGs.
• Comentários sobre o exercício E06 da última aula.
• Componentes fortes.
• Lista de exercícios E07.
• Tarefa E (ciclo ou ordenamento topológico), para 31/8, quarta-feira, até 6h50m.

Aula 8 (26/8, sexta)

• Comentários sobre a tarefa C (rastreamento versus classificação dos arcos).
• Tarefa E (ciclo ou ordenamento topológico), para 31/8, quarta-feira, até 6h50m.
• Componentes fortes de digrafos.
• Lista de exercícios E08.

Aula 9 (31/8, quarta)

• Algoritmo de Kosaraju-Sharir.
• Lista de exercícios E09.

Aula 10 (2/9, sexta)

• Comentários sobre exercícios E09.
• Algoritmo de Kosaraju-Sharir.
• Busca em largura.
• Lista de exercícios E10.
• Tarefa F (componentes fortes de digrafos aleatórios), para 14/9, quarta-feira, até 6h30m.

Feriado (7/9, quarta) (Semana da Pátria)

Feriado (9/9, sexta) (Semana da Pátria)

Aula 11 (14/9, quarta)

• Caminhos de comprimento mínimo.
• Comentários sobre a tarefa E (ciclo ou ordenamento topológico).
• Atualizações incrementais das bibliotecas DIGRAPHlists e DIGRAPHmatrix: basta colocar na biblioteca as versões mais completas de DIGRAPHdfs(), de DIGRAPHhasCycle(), etc.
• Lista de exercícios E11.

Prova 1 (16/9, sexta)

• Gabarito

Aula 12 (21/9, quarta)

• Ciclos não triviais em grafos.
• Florestas e árvores.
• Lista de exercícios E12.

Aula 13 (23/9, sexta)

• Grafos bipartidos versus ciclos ímpares.
• Comentários sobre a tarefa F (componentes fortes de digrafos aleatórios).
• Comentários sobre os exercícios E11 da penúltima aula.
• Comentários sobre os exercícios E12 da última aula.
• Lista de exercícios E13.

Aula 14 (28/9, quarta)

• Tarefa G (small world): para 5/10, quarta-feira, às 6:30.
• Comentários sobre E11.4 (compara duas partições).
• Comentários sobre a lista de exercícios E13.
• Coloração de vértices.
• Lista de exercícios E14.

Aula 15 (30/9, sexta)

• Comentários sobre E14.2.
• Coloração de vértices.
• Lista de exercícios E15.

Aula 16 (5/10, quarta)

• Emparelhamento máximo em grafos bipartidos.
• Comentários sobre a tarefa F (componentes fortes de digrafos aleatórios).
• Lista de exercícios E16 (emparelhamentos).

Aula 17 (7/10, sexta)

• Comentários sobre a lista de exercícios E14 e E15 (coloração de vértices).
• Emparelhamento máximo e cobertura mínima em grafos bipartidos.
• Comentários sobre a lista de exercícios E16 (emparelhamento máximo).
• Lista de exercícios E17 (emparelhamentos).

12/10, quarta: feriado

14/10, sexta: não há aula (break do BCC)

Aula 18 (19/10, quarta)

• Pontes e grafos aresta-biconexos.
• Lista de exercícios E18 (pontes).

Prova 2 (21/10, sexta)

• Gabarito

Aula 19 (26/10, quarta)

• Warnings de compilação: você usa a opção  -O2  do compilador gcc?  Tem certeza?
• Caminhos de custo mínimo (SPT).
• Lista de exercícios E19.

28/10, sexta: não há aula (dia do funcionário público)

2/11, quarta: não há aula (finados)

Aula 20 (4/11, sexta)

• Caminhos de custo mínimo
• Solução do exercício E19.4.
• Algoritmo de Dijkstra.
• Comentários sobre a tarefa G (small world).
• Lista de exercícios E20.

Aula 21 (9/11, quarta)

• Mais comentários sobre a tarefa G (small world).
• Relaxação.
• Algoritmo de Dijkstra.
• Lista de exercícios E21.

Aula 22 (11/11, sexta)

• Árvores geradoras de grafos.
• Árvores geradoras de custo mínimo (MST).
• Lista de exercícios E22.

16/11, quarta: não há aula (break do BCC)

• Tarefa H (para 1/12, quinta-feira, até 7h00m).

18/11, sexta: não há aula (break do BCC)

Aula 23 (23/11, quarta)

• Algoritmo de Prim.
• Comentários sobre a lista de exercícios E22.
• Lista de exercícios E23.

Aula 24 (25/11, sexta)

• Algoritmo de Kruskal.
• Comentários sobre a lista de exercícios E23.
• Lista de exercícios E24.

Aula 25 (30/11, quarta)

• Caminhos em DAGs.
• Comentários sobre a lista de exercícios E24.
• Lista de exercícios E25.
• Caminhos de custo máximo.

Aula 26 (2/12, sexta)

• O problema do fluxo máximo.
• Algoritmo de Ford e Fulkerson.

Aula 27 (7/12, quarta)

• Fluxo máximo e corte mínimo.
• Implementação do algoritmo de Ford e Fulkerson.
• Caminhos aumentadores mínimos.

Prova 3 (9/12, sexta)

• Gabarito

Recuperação

Prova de recuperação

• Quarta-feira, 14/12/2016, das 10h às 12h, sala A-268