Teoria dos Grafos COS242 - 2022/2

Retirado do Wikipedia

• Daniel Ratton Figueiredo
• Fábio Happ Botler

• Maria Luiza C. Wuillaume - marialuizacw [AT] poli.ufrj.br
• Grupo do Whatsapp: ver mensagem no quadro de avisos do Moodle e se inscrever

• Sala H-324B, segundas e quartas das 13h às 15h

Todos devem se inscrever no Moodle da discilina. O código de acesso para auto-inscrição é codigo242.

Aula	Data	Comentário	Slides	Vídeos	Tarefa
1	29/8	Logística e regras do jogo. Objetivo, definindo grafos, exemplos, e problemas reais	aula_0.pdf aula_1.pdf	Aula 0 Aula 1
2	31/8	Definições importantes, algumas propriedades, algumas classes de grafos	aula_2.pdf	Aula 2	Saiu lista 1
3	5/9	Representando grafos, matriz e lista, operações básicas, tempos de acesso	aula_3.pdf	Aula 3	Fazer lista 1
-	7/9	Não teremos aula: Feriado nacional do Dia da Independência			Saiu lista 2
4	12/9	Explorando grafos, algoritmo genérico, BFS, camadas, distâncias, árvore geradora, caminho mínimo	aula_4.pdf	Aula 4	Entregar lista 1
5	14/9	Implementando a BFS, DFS e suas implementações, complexidade	aula_5.pdf	Aula 5	Saiu TP 1
6	19/9	Componentes conexos, grafos direcionados, busca em grafos direcionados, grafos fortemente conexos	aula_6.pdf	Aula 6	Fazer lista 2, começar TP 1
7	21/9	DAG, execução de tarefas, ordenação topológica, algoritmo eficiente	aula_7.pdf	Aula 7	Entregar lista 2
8	26/9	Grafos com pesos, comprimento, distâncias, ideia e algoritmo de Dijkstra, Dijkstra - o próprio. Documentário: Discipline in Thought (2000)	aula_8.pdf	Aula 8	Saiu lista 3, fazer TP 1
9	28/9	Corretude de Dijkstra, fila de prioridades, heap binário, Dijkstra eficiente, tempos de execução	aula_9.pdf	Aula 9	Fazer TP 1
10	3/10	Problema do labirinto (pathfinding), busca informada, best-first search, A* Introduction to A* no "Red Blob Games" por Amit Patel	aula_10.pdf	Aula 10	Terminar TP 1
11	5/10	Projetando redes, MST, algoritmos de Prim e Kruskal, propriedades do corte e do ciclo	aula_11.pdf	Aula 11	Saiu lista 4
12	10/10	Discussão, dúvidas, e perguntas visando a P1. Tragam suas dúvidas!			Entregar TP 1
-	12/10	Não teremos aula: Feriado nacional do Dia de Nossa Senhora Aparecida (Padroeira do Brasil)			Entregar Lista 3
13	17/10	Primeira Prova. Início pontualmente às 13h. Rever todas as listas em preparação para a prova			Entregar lista 4
14	19/10	Paradigma guloso, coloração em grafos, número cromático, algoritmo guloso, Teorema das 4 cores	aula_12.pdf	Aula 12	Saiu TP 2
15	24/10	Grafos com pesos negativos, caminho mais curto entre todos os pares, programação dinâmica, algortimo de Floyd-Warshall, melhorias	aula_13.pdf	Aula 13	Saiu Lista 5
16	26/10	Problema da soma do subconjunto (subset sum), recursão, programação dinâmica, problema da mochila. Discussão e vista da P1	aula_17b.pdf		Fazer TP 2
17	31/10	Caminho mínimo com pesos negativos, programação dinâmica, algoritmo de Bellman­-Ford, melhorias, roteamento em redes	aula_14.pdf	Aula 14	Fazer TP 2
-	2/11	Feriado Nacional: Dia de Finados			Fazer TP 2 e Lista 5
18	7/11	Emparelhamentos em grafos bipartidos, algoritmo, análise de complexidade	aula_15.pdf	Aula 15	Fazer Lista 5
19	9/11	Apresentação e discussão do TP2. Iremos votar no melhor trabalho (ver resultado abaixo).			Entregar TP2
-	14/11	Enforcado pelo Feriado Nacional: Dia da Proclamação da República			Fazer TP 2 e Lista 5
20	16/11	Redes de fluxo, problema do fluxo máximo, problema do corte mínimo, dualidade	aula_16.pdf	Aula 16	Fazer Lista 5, saiu Lista 6
21	21/11	Fluxo máximo, algoritmo de Ford-Fulkerson, análise, melhorias	aula_17.pdf	Aula 17	Entregar Lista 5, saiu TP 3
22	23/11	Aplicações do fluxo máximo: emparelhamento, caminhos distintos, corte mínimo, segmentação de imagens	aula_18.pdf	Aula 18	Fazer Lista 6 e TP 3
-	28/11	Não teremos aula (ponto facultativo): Jogo do Brasil na Copa do Qatar			Fazer Lista 6 e TP 3
23	30/11	Apanhado final, caminho trilhado, futuro em grafos (ciência das redes e teoria dos grafos), avaliação da disciplina Veja palestra-duelo dos professores sobre Ciência das Redes e Teoria dos Grafos	aula_19.pdf	Aula 19	Fazer Lista 6 e TP 3
-	5/12	Não teremos aula (ponto facultativo): Jogo do Brasil na Copa do Qatar			Fazer Lista 6 e TP 3
24	7/12	Segunda Prova. Início pontualmente às 13h. Rever todas as listas depois da P1 em preparação para a prova			Entregar Lista 6
25	12/12	Apresentação e discussão do TP 3. Iremos votar no melhor trabalho (ver resultado abaixo)			Entregar TP 3
-	14/12	Não teremos aula: Se preparar para a PF, tirar dúvidas com a monitora
26	19/12	Prova Final. Início pontualmente às 13h. Refazer e rever todas as listas em preparação para a prova

As listas devem ser entregue no Moodle da disciplina, até o final do dia de entrega. Listas entregues com atraso serão penalizadas em 10% ao dia.

• Primeira Lista de Exercícios - Entrega: 12/09
• Segunda Lista de Exercícios - Entrega: 21/09
• Terceira Lista de Exercícios - Entrega: 10/10 - adiado para: 12/10
• Quarta Lista de Exercícios - Entrega: 17/10
• Quinta Lista de Exercícios - Entrega: 16/11 - adiado para: 21/11
• Sexta Lista de Exercícios - Entrega: 5/12 - adiado para: 7/12

Os trabalhos práticos devem ser entregue no Moodle da disciplina, até o final do dia de entrega. Trabalhos entregues com atraso serão penalizadas em 10% ao dia.

• Trabalho de Disciplina - Parte 1 - Entrega: 05/10 - adiado para: 10/10

  • Grafos a serem analisados nos estudos de caso (arquivos zipados):

    grafo_2.txt.gz [< 1 MB]
    grafo_3.txt.gz [2 MB]
    grafo_4.txt.gz [19 MB]
    grafo_5.txt.gz [114 MB]
    grafo_6.txt.gz [198 MB]
    

• Trabalho de Disciplina - Parte 2 - Entrega e apresentação: 9/11

  • Grafos a serem analisados nos estudos de caso (arquivos zipados):

    grafo_W_1_1.txt.gz [< 1 MB]
    grafo_W_2_1.txt.gz [2 MB]
    grafo_W_3_1.txt.gz [20 MB]
    grafo_W_4_1.txt.gz [222 MB]
    grafo_W_5_1.txt.gz [233 MB]
    

  • Rede de colaboração entre pesquisadores da Computação.
    rede_colaboracao.txt [40 MB]
    rede_colaboracao_vertices.txt [15 MB]: mapeamento entre os índices dos vértices da rede e o nome dos pesquisadores.
    Atenção: Esta rede é apenas uma projeção da real rede de colaboração, pois foi construído considerando apenas os artigos científicos que estavam listados no DBLP em 2009. Ou seja, a rede de colaboração acima não está completa nem atualizada!
  • Utilize este modelo de tabela para apresentar seus resultados no relatório e apresentação oral.

  Resultado da votação dos alunos no melhor trabalho (juri popular). Parabéns ao Patrick Trindade pelo primeiro lugar recebendo votação unânime. Tivemos 10 alunos votando e um total de 20 votos (máximo de 2 votos por aluno), e todos votaram no Patrick!
  

• Trabalho de Disciplina - Parte 3 - Entrega e apresentação: 7/12 - adiado para: 12/12

  • Grafos a serem analisados nos estudos de caso (arquivos zipados):

    grafo_rf_1.txt.gz [< 1 MB]
    grafo_rf_2.txt.gz [< 1 MB]
    grafo_rf_3.txt.gz [< 1 MB]
    grafo_rf_4.txt.gz [< 1 MB]
    grafo_rf_5.txt.gz [7 MB]
    grafo_rf_6.txt.gz [9 MB]
    grafo_rf_7.txt.gz [79 MB]
    grafo_rf_8.txt.gz [101 MB]
    

  Resultado da votação dos alunos no melhor trabalho (juri popular). Parabéns (novamente) ao Patrick Trindade pelo primeiro lugar recebendo votação unânime. Tivemos 10 alunos votando e um total de 20 votos (máximo de 2 votos por aluno), e todos votaram no Patrick!
  

• Primeira prova: 17/10, segunda, às 13h (pontualmente), com 2h de duração
• Segunda prova: 5/12 - adiado para 7/12, segunda, às 13h (pontualmente), com 2h de duração
• Prova Final: 14/12 - adiado para 19/12 às 13h (pontualmente), com 2h de duração

As notas de aulas serão tiradas principalmente dos seguintes referências:

• Algorithm Design por Jon Kleinberg e Éva Tardos, Addison-Wesley, 2005.
• Teoria Computacional de Grafos por Jayme Szwarcfiter, Elsevier, 2018
• Introduction to Algorithms por Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein, McGraw Hill, 2002 (2a. edição).
• Wikipedia: Graph Theory (e links relacionados).