Teoria dos Grafos COS242 - 2021/2

Retirado do Wikipedia

• Daniel Ratton Figueiredo
• Fábio Happ Botler

• Felipe Schreider - @ cos.ufrj.br
• Grupo do Whatsapp: ver mensagem no fórum do Moodle

• Google Meet: https://meet.google.com/tin-rrzx-exz
• Dia/horário: segundas e quartas das 13h às 15h - aula síncrona às 14h

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	17/11	Logística e regras do jogo. Objetivo, definindo grafos, exemplos, e problemas reais	aula_0.pdf aula_1.pdf	Aula 0 Discussão Aula 1 Discussão	Saiu lista 1
2	22/11	Definições importantes, algumas propriedades, algumas classes de grafos	aula_2.pdf	Aula 2 Discussão	Fazer lista 1
3	24/11	Representando grafos, matriz e lista, operações básicas, tempos de acesso	aula_3.pdf	Aula 3 Discussão	Fazer lista 1
4	29/11	Explorando grafos, algoritmo genérico, BFS, camadas, distâncias, árvore geradora, caminho mínimo	aula_4.pdf	Aula 4 Discussão	Entregar lista 1, saiu lista 2
5	1/12	Implementando a BFS, DFS e suas implementações, complexidade	aula_5.pdf	Aula 5 Discussão	Fazer lista 2, saiu TP 1
6	6/12	Componentes conexos, grafos direcionados, busca em grafos direcionados, grafos fortemente conexos	aula_6.pdf	Aula 6 Discussão	Fazer lista 2, começar TP 1
7	8/12	DAG, execução de tarefas, ordenação topológica, algoritmo eficiente	aula_7.pdf	Aula 7 Discussão	Entregar lista 2
8	13/12	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 Discussão	Saiu lista 3, fazer TP 1
9	15/12	Corretude de Dijkstra, fila de prioridades, heap binário, Dijkstra eficiente, tempos de execução	aula_9.pdf	Aula 9 Discussão	Fazer TP 1
10	20/12	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 Discussão	Terminar TP 1
11	22/12	Projetando redes, MST, algoritmos de Prim e Kruskal, propriedades do corte e do ciclo	aula_11.pdf	Aula 11 Discussão	Entregar TP 1, saiu lista 4
-	27/12	Recesso de final de ano!
12	3/1	Discussão, dúvidas, e perguntas visando a P1. Tragam suas dúvidas!		Discussão	Entregar lista 3
13	5/1	Paradigma guloso, coloração em grafos, número cromático, algoritmo guloso, Teorema das 4 cores	aula_12.pdf	Aula 12 Discussão	Fazer lista 4
14	10/1	Discussão, dúvidas, e perguntas visando a P1. Tragam suas dúvidas!		Discussão	Entregar lista 4
15	12/1	Primeira Prova. Início pontualmente às 13h. Rever todas as listas em preparação para a prova			Saiu TP 2
16	17/1	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 Discussão	Saiu Lista 5
17	19/1	Caminho mínimo com pesos negativos, programação dinâmica, algoritmo de Bellman­-Ford, melhorias, roteamento em redes	aula_14.pdf	Aula 14 Discussão	Fazer TP 2, Lista 5
18	24/1	Emparelhamentos em grafos bipartidos, algoritmo, análise de complexidade	aula_15.pdf	Aula 15 Discussão	Fazer lista 5
19	26/1	Emparelhamentos em grafos bipartidos com pesos nas arestas	aula_15_2.pdf	Aula 15_2 Discussão	Fazer lista 5
20	31/1	Redes de fluxo, problema do fluxo máximo, problema do corte mínimo, dualidade	aula_16.pdf	Aula 16 Discussão	Entregar lista 5
21	2/2	Fluxo máximo, algoritmo de Ford-Fulkerson, análise, melhorias	aula_17.pdf	Aula 17 Discussão	Saiu lista 6
22	7/2	Aplicações do fluxo máximo: emparelhamento, caminhos distintos, corte mínimo, segmentação de imagens	aula_18.pdf	Aula 18 Discussão	Fazer TP 2
23	9/2	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 Discussão	Fazer Lista 6
-	14/2	Não teremos aula: 11ª SIAc - Semana de Integração Acadêmica Tarefa: Assistir a duas apresentações da Jornada de Iniciação Científica Tecnológica, Artística e Cultural (JICTAC), e preparar um resumo de 1 página para cada apresentação (submeter no Moodle, vale como uma lista de exercícios)			Fazer TP2
-	16/2	Não teremos aula: 11ª SIAc - Semana de Integração Acadêmica Tarefa: Assistir a duas apresentações da Jornada de Iniciação Científica Tecnológica, Artística e Cultural (JICTAC), e preparar um resumo de 1 página para cada apresentação (submeter no Moodle, vale como uma lista de exercícios)			Entregar TP 2
24	21/2	Discussão e votação do melhor TP2. Discussão, dúvidas, e perguntas visando a P2. Tragam suas dúvidas!		Discussão	Entregar Resumos JICTAC
25	23/2	Segunda Prova. Início pontualmente às 13h. Rever todas as listas depois da P1 em preparação para a prova.			Entregar lista 6
-	28/2	Não teremos aula: Recesso de Carnaval
-	2/3	Não teremos aula: Recesso de Carnaval
26	7/3	Discussão, dúvidas, e perguntas visando a PF. Tragam suas dúvidas!		Discussão
27	9/3	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: 29/11
• Segunda Lista de Exercícios - Entrega: 8/12
• Terceira Lista de Exercícios - Entrega: 3/1
• Quarta Lista de Exercícios - Entrega: 5/1 - adiada para 10/1
• Quinta Lista de Exercícios - Entrega: 31/1
• Sexta Lista de Exercícios - Entrega: 23/2
• Resumos (dois) de apresentações da Jornada de Iniciação Científica Tecnológica, Artística e Cultural (JICTAC) - Entrega: 21/2

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: 22/12 - adiado para 24/12

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

    grafo_1.txt.gz [< 1 MB]
    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: 16/2 - adiado para 18/2

  • 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]
    

    Novos grafos direcionados com pesos negativos:
    grafo_W_1_0.txt.gz [< 1 MB]
    grafo_W_2_0.txt.gz [< 1 MB]
    grafo_W_3_0.txt.gz [3 MB]
    grafo_W_4_0.txt.gz [3 MB]
    grafo_W_5_0.txt.gz [16 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!
  • Use este modelo de tabela para apresentar os resultados em seu relatório e apresentação.

  Resultado da votação dos alunos no melhor trabalho (juri popular). Parabéns às duplas "Br2uno e João" e "Yasmin e Maria Luiza", empatadas em primeiro lugar com 8 votos cada! Tivemos 17 alunos votando e um total de 33 votos (máximo de 2 votos por aluno)
  

  Grupos (duplas):
  1 Ananias Sousa Machado e Aline Jacinto P. Capucho
  2 Antonny Victor Da Silva e Sávio Barreto Teles Da Silva
  3 Eduardo Canova e Igor Telles
  4 Felipe Vilela M. Casalecchi e Sylvio S. da Costa Mello
  5 Felipe Takasawa Paiva e João Pedro Regazzi F. da Silva
  6 Frederico Januario Lisbôa e Bernardo Oliveira Cunha
  7 Breno Castilho Santos e João Pinheiro
  8 Laura Daflon e Pedro Siqueira
  9 Lucas Tiné e Victor Ribeiro
  10 Paulo Victor Innocencio e Nuno Correia
  11 Pedro Lucas Ravaglia e André Hoffman
  12 Rafael Martins
  13 Rayssa Almeida
  14 Gabriel Bulhões e Rui Aldé Lopes
  15 Nayara Gomes e Victor Assis
  16 Felipe Vianna e William Lucas
  17 Yasmin Forestti Romeiro e Maria Luiza Cantanhede
  

• Primeira prova: 5/1, quarta, às 13h (pontualmente), com 2h de duração - adiada para 12/1
• Segunda prova: 23/2, quarta, às 13h (pontualmente), com 2h de duração
• Prova Final: 9/3, quarta, à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).