MAC0328 (2019)
Algoritmos em Grafos
MAC0328 é disciplina optativa eletiva
(6-o semestre)
do BCC (Bacharelado em Ciência da Computação).
Programa
Ementa oficial
(conforme
catálogo de graduação do IME e
catálogo de graduação da USP):
Conexão de grafos: componentes, grafos biconexos.
Digrafos fortemente conexos (algoritmo de Kosaraju-Sharir, algoritmo de Tarjan).
Emparelhamentos máximos em grafos bipartidos.
Emparelhamentos em grafos arbitrários (algoritmo de Edmonds).
Fluxo máximo (algoritmo de Ford-Fulkerson).
Coloração de vértices.
Circuitos hamiltonianos.
Tópicos opcionais:
link analysis, network analysis, redes aleatórias.
(Mas não prometo seguir essa ementa à risca.)
Requisitos
O requisito oficial de MAC0328 é
MAC0121 (Algoritmos e Estruturas de Dados I).
Provavelmente, muitos dos alunos também já cursaram
MAC0323 (Algoritmos e Estruturas de Dados II).
Horário, sala, professor
As aulas serão dadas na sala
B-142,
segundas-feiras às 10:02 e sextas-feiras às 8:04.
As aulas começam no dia 2/8/2019 (sexta-feira)
e terminam no dia 6/12/2019 (sexta-feira).
As aulas serão dadas pelo professor Paulo Feofiloff
(sala C-103).
Por enquanto, não temos monitor.
Para discussões, perguntas, avisos, mensagens,
e entrega de tarefas,
usaremos o Paca (Moodle).
Você deve se inscrever o quanto antes.
Livros e material didático
Principais referências:
-
R. Sedgewick,
Algorithms in C (part 5: Graph Algorithms),
3rd edition,
Addison-Wesley/Longman, 2002.
-
R. Sedgewick and
K. Wayne,
Algorithms, 4th edition,
Addison-Wesley, 2011.
-
P. Feofiloff,
Algoritmos para Grafos em C (via Sedgewick),
IME-USP.
Referências adicionais:
-
K. Wayne and R. Sedgewick,
Algorithms, part I,
Princeton University, Coursera online course.
-
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein,
Introduction to Algorithms, 3rd edition,
MIT Press, 2009.
Exercícios e tarefas
Os exercícios serão feitos durante as aulas
e não terão nota.
As
tarefas serão feitas fora das aulas e valerão nota.
(Mas estou pensando em fazer
algumas tarefas durante as aulas,
no estilo provinha-surpresa.)
Critério de avaliação
Teremos três provas e várias tarefas.
A nota final será composta por
70% da média das provas
e 30% da média das tarefas.
Entretanto,
se a média das provas ou a média das tarefas ficar abaixo de 5,
a nota final será a menor das duas.
Administração
Veja a lista de alunos
e a tabela de notas.
Calendário de aulas e provas
Sujeito a muitas alterações.
- Aula 1: 2/8 (sexta)
-
Apresentação. Regras do jogo.
-
Esclarecimento de dúvidas.
-
Minhas
notas de aula.
-
Quando estudar minhas notas de aulas, comece pelo exemplos.
Estude cada exemplo detalhadamente.
Ganha pontos quem encontrar erros.
-
Grafos.
- Estruturas de dados para grafos.
- A biblioteca GRAPHlists.
-
Lista de exercícios E01.
- Aula 2: 5/8 (segunda)
-
Grafos aleatórios.
-
Caminhos e ciclos.
-
Numerações e permutações de vértices.
-
Grafos topológicos.
-
Lista de exercícios E02.
-
Tarefa A, para 8/8.
- Aula 3: 9/8 (sexta)
-
Florestas radicadas e vetor de pais.
-
Árvores radicadas.
-
Acessibilidade (existência de caminho).
-
Busca em profundidade (DFS).
-
Lista de exercícios E03.
- Aula 4: 12/8 (segunda)
-
Floresta DFS.
-
Arcos de retorno, arcos cruzados.
-
Lista de exercícios E04.
-
Tarefa B, para 15/8.
- Aula 5: 16/8 (sexta)
- Numeração em pós-ordem.
- Intervalos de vida de vértices.
- Arcos de avanço, de retorno, e cruzados.
-
Lista de exercícios E05.
- Aula 6: 19/8 (segunda)
- Comentários sobre a tarefa B.
- Ciclos e dags.
-
Lista de exercícios E06.
-
Tarefa C.
- Aula 7: 23/8 (sexta)
-
Caminhos de comprimento mínimo.
-
Distâncias, potencial e relaxação.
-
Busca em largura (BFS).
-
Lista de exercícios E07.
- Aula 8: 26/8 (segunda)
- Algoritmo de caminhos mínimos.
- Grafos conexos.
- Componentes conexas.
- Circuitos e florestas.
- Tarefa C, para sexta.
- Aula 9: 30/8 (sexta)
- [Estou pensando em trocar a aula por uma provinha-surpresa.]
- Detecção de circuitos.
- Feriado (Semana da Pátria): 2/9 (segunda)
- Feriado (Semana da Pátria): 6/9 (sexta)
- Aula 10: 9/9 (segunda)
- Grafos aresta-biconexos.
- Algoritmo de Tarjan para grafos aresta-biconexos.
- Tarefa E, para sexta.
- Aula 11: 13/9 (sexta)
- Grafos aresta-biconexos.
- Tarefa F, durante a aula.
- Veja aula de Naveen Garg sobre componentes aresta-biconexas
(em inglês e hindi). Pode começar em 21:50.
-
Prova 1: 16/9 (segunda)
-
Você já estudou o
gabarito da prova?
- Aula 12: 20/9 (sexta)
- Componentes aresta-biconexas.
- Algoritmo de Tarjan para componentes biconexas.
- Lista de exercícios E12.
- Aula 13: 23/9 (segunda)
- Coloração de vértices.
- Lista de exercícios E13.
- Tarefa G, para quinta-feira.
- Aula 14: 27/9 (sexta)
- Grafos bipartidos e circuitos ímpares.
- Lista de exercícios E14.
- Aula 15: 30/9 (segunda)
- Emparelhamentos.
- Emparelhamentos máximos em grafos bipartidos.
- Lista de exercícios E15.
- Aula 16: 4/10 (sexta)
- Emparelhamentos máximos e coberturas mínimas em grafos bipartidos.
- Lista de exercícios E16.
- Break do BCC (Padroeira do Brasil): 7/10 (segunda)
- Break do BCC (Padroeira do Brasil): 11/10 (sexta)
- Aula 17: 14/10 (segunda)
- Árvores geradoras de grafos não-dirigidos.
- Grafos com custos nos arcos.
- Árvores geradoras de custo mínimo (MST).
- Lista de exercícios E17.
- Aula 18: 18/10 (sexta)
- Algoritmo de Prim para MST.
- Lista de exercícios E18.
- Prova 2: 21/10 (segunda)
-
Gabarito da prova.
-
Tarefa H, para quarta-feira.
- Aula 19: 25/10 (sexta)
- Algoritmo de Kruskal para MST.
-
Tarefa H, para quarta-feira.
-
Lista de exercícios E19.
- Feriado: 28/10 (segunda)
- Aula 20: 1/11 (sexta)
- Distâncias e potenciais sob custos positivos.
- Algoritmo de Dijkstra para SPT.
- Lista de exercícios E20.
- Aula 21: 4/11 (segunda)
- O problema do fluxo máximo.
- Algoritmo de Ford-Fulkerson.
- Lista de exercícios E21.
- Aula 22: 8/11 (sexta)
- Fluxo máximo e corte mínimo.
- Implementação do algoritmo de Ford-Fulkerson.
-
Tarefa I, para a outra quarta-feira.
-
Lista de exercícios E22.
- Break do BCC (Proclamação da República): 11/11 (segunda)
- Feriado (Proclamação da República): 15/11 (sexta)
- Aula 23: 18/11 (segunda)
- Implementação do algoritmo de Ford-Fulkerson.
- Caminhos aumentadores mínimos.
- Aula 24: 22/11 (sexta)
- Discussão da tarefa I.
- Fluxo: caminhos aumentadores de máxima capacidade.
- Aula 25: 25/11 (segunda)
- Algoritmo de Bellman-Ford.
- Aula 26: 29/11 (sexta)
- Exercícios sobre fluxo, grafos aresta-biconexos,
caminhos de custo mínimo
- Aula 27: 2/12 (segunda)
- Laboratório de exercícios.
- Prova 3: 6/12 (sexta, 10h)
- Atendendo a pedidos, a prova começará às 10h
(e terminará às 11:55).
- Prova substitutiva: 9/12 (segunda, 10h)
- Só para quem não fez alguma das provas regulares.
- Prova 2-a avaliação: 22/1/2020
- (mais conhecida como reavaliação, ou recuperação)
- 9h, sala C-103.
Algumas edições anteriores de MAC0328
-
2016: Paulo Feofiloff
-
2014: Arnaldo Mandel
-
2012: Arnaldo Mandel
-
2008: José Coelho
Curiosidades