Teoria dos Grafos COS242 - 2011/2

Retirado do Wikipedia

• Daniel Ratton Figueiredo
• Celina Miraglia Herrera de Figueiredo

• Rodrigo Paim
• Horário de atendimento: Terças das 15:15 às 16:15
• Local: Sala I-246 (CT, Bloco I, segundo andar), tocar campainha (Carol)

• Sala H-304A (CT, Bloco H, terceiro andar)
• Dia/horário: segundas das 10h às 12h e quartas das 8h às 10h.

• Todos os alunos devem se inscrever na lista de email abaixo. A lista será utilizada para enviar avisos e discussão de dúvidas em geral. Alunos também podem (e devem) contribuir para a lista, tanto com perguntas como com respostas.
• Para se inscrever na lista, envie uma mensagem para grafos-2011-join@land.ufrj.br sem nada no assunto ou no corpo da mensagem. Depois confirme sua inscrição na mensagem que você irá receber do servidor da lista.
• Para sair da lista, envie uma mensagem para grafos-2011-leave@land.ufrj.br sem nada no assunto ou no corpo da mensagem.

Aula	Data	Comentário	Slides	Tarefa
1	8/08	Logística, regras, definição de grafos, introdução, motivação com problemas reais, formando casais	aula_0.pdf aula_1.pdf	Procurar livro sobre algoritmos e grafos (ver referências abaixo)
2	10/08	Mais problemas reais, definições importantes, algumas propriedades	aula_2.pdf	Saiu lista 1. Arrumar livro texto.
3	15/08	Representando grafos, matriz e lista, tempo de acesso	aula_3.pdf	Terminar lista 1. Arrumar livro texto.
4	17/08	Introdução ao problema de busca em grafos, algoritmos genéricos de busca		Entregar lista 1
5	22/08	Busca em grafos, BFS (Busca em Largura), árvore geradora, caminhos mínimos	aula_5.pdf	Saiu lista 2
6	24/08	Implementação, complexidade, BFS e DFS (Busca em Profundidade), componentes conexas	aula_6.pdf	Saiu trabalho parte 1. Fazer lista 2
7	29/08	Classe de funções e notação O, Omega, Theta, propriedades da notação, funções usuais, tempo de execução e algoritmos	aula_7.pdf	Começar trabalho parte 1. Terminar lista 2
8	31/08	Grafos direcionados, busca em grafos direcionados, DAG, ordenação topológica	aula_8.pdf	Entregar lista 2. Fazer trabalho parte 1
9	5/09	Grafos com pesos, distâncias, algoritmo de Dijkstra.	aula_9.pdf	Fazer lista 3
-	7/09	Feriado nacional: Dia da Independência do Brasil.		Fazer lista 3. Continuar trabalho!
10	12/09	Dijkstra, análise de corretude, implementação com heap, complexidade	aula_9.pdf	Fazer lista 3
11	14/09	MST (Árvore Geradora Mínima), algoritmos de Prim e Kruskal.	aula_11.pdf	Entregar lista 3. Continuar trabalho.
12	19/09	Propriedades da MST (corte e ciclo), corretude dos algoritmos de Prim e Kruskal, algoritmos gulosos.	aula_11.pdf	Terminar trabalho.
13	21/09	Entrega e apresentação dos trabalhos práticos. Cada grupo terá 10min para expor oralmente seu trabalho (tragam seus slides também em PDF). Ver detalhes da avaliação no email enviado para a lista.		Entregar trabalho. Saiu lista 4
14	26/09	Algoritmos gulosos, princípio e exemplos. Discussão para a prova (tragam suas dúvidas).	aula_14.pdf	Fazer lista 4.
15	28/09	Primeira prova. Início às 8h pontualmente. Sala a ser determinada. Refazer todas as listas para se preparar para a prova.		Entregar lista 4. Saiu parte 2 do trabalho.
16	3/10	[Aula opcional, presença não obrigatória] Pontes de Königsberg, ciclo Euleriano, ciclo Hamiltoniano, e "Quem foi Turing?"	aula_16.pdf	Fazer lista 5 (resumo de trabalhos da JIC). Começar trabalho parte 2.
-	5/10	Não teremos aula. Semana da Jornada de Iniciação Científica (JIC) da UFRJ.		Fazer lista 5 (resumo de trabalhos da JIC). Começar trabalho parte 2.
-	10/10	Não teremos aula. Professor participando de um Workshop na área de Redes de Computadores. Ver aula de reposição dia 13/10.		Entregar resumos da JIC. Fazer trabalho parte 2.
-	12/10	Feriado nacional: Dia de Nossa Senhora Aparecida, padroeira do Brasil.		Fazer trabalho parte 2.
17	13/10	[Aula de reposição: 15h, sala H304] Coloração em grafos, número cromático, algoritmo guloso, coloraçao de mapas	aula_17.pdf	Fazer trabalho parte 2.
18	17/10	Clusterização de objetos, métricas, algoritmo guloso e variações	aula_18.pdf	Saiu lista 6. Saiu datasets.
19	19/10	Escalonando tarefas no tempo com pesos, análise da solução ótima, algoritmo recursivo, iterativo, programação dinâmica	aula_19.pdf	Fazer lista 6. Terminar trabalho.
20	24/10	Problema da soma do subconjunto (subset sum), programação dinâmica, problema da mochila.	aula_20.pdf	Fazer lista 6. Terminar trabalho.
21	26/10	Discussão e vista da primeira prova.		Trabalho adiado. Fazer lista 6.
22	31/10	Entrega e apresentação do trabalho prático parte II. Cada grupo terá 10m para expor oralmente seu trabalho (tragam seus slides também em PDF). Ver detalhes da avaliação no email enviado para a lista.		Entregar trabalho. Entregar lista 6
-	2/11	Feriado nacional: Dia de Finados.		Saiu lista 7
23	7/11	Grafos com pesos negativos, caminho mais curto entre todos os pares, algortimo de Floyd-Warshall, programação dinâmica.	aula_23.pdf	Fazer lista 7
24	9/11	Caminho mínimo em grafos com pesos negativos, algoritmo de Bellman-Ford, programação dinâmica, algoritmo distribuído.	aula_24.pdf	Saiu trabalho prático. Fazer lista 7.
-	14/11	Enforcado pelo Feriado Nacional: Dia da Proclamação da República do Brasil		Terminar lista 7
25	16/11	Redes de fluxo, problema do fluxo máximo, problema do corte mínimo, dualidade.	aula_25.pdf	Entregar lista 7.
26	21/11	Algoritmo de Ford-Fulkerson, análise, melhorias.	aula_26.pdf	Saiu lista 8.
27	23/11	Aplicação de fluxo máximo e redução. Emparelhamento perfeito, caminho distintos, etc.	aula_27.pdf	Fazer lista 8.
28	28/11	Mais aplicação de fluxo máximo e redução.	aula_27.pdf	Fazer lista 8 e trabalho prático.
29	30/11	Resumo da ópera: apanhado final, futuro em redes, discussão, dúvidas das listas	aula_29.pdf	Terminar lista 8. Finalizar trabalho
30	5/12	Entrega e apresentação do trabalho prático parte III. Cada grupo terá 10m para expor oralmente seu trabalho (tragam seus slides também em PDF).		Entregar trabalho.
31	7/12	Segunda prova. Início às 8h pontualmente. Sala a ser determinada. Refazer todas as listas para se preparar para a prova, dando maior ênfase às listas pós-P1.		Entregar lista 8.
32	14/12	Prova final. Início às 8h pontualmente na sala H304. Refazer todas as listas para se preparar para a prova. Participar da monitoria.

• Primeira Lista de Exercícios - Entrega 17/08
• Segunda Lista de Exercícios - Entrega 31/08
• Terceira Lista de Exercícios - Entrega 14/09
• Quarta Lista de Exercícios - Entrega 28/09
• Quinta Lista de Exercícios - Entrega 10/10

  Escolher e assistir quaisquer duas apresentações da Jornada de Iniciação Científica da UFRJ. Escrever um resumo (meia página, no máximo) sobre cada uma das apresentações. Seu resumo deve conter o problema que foi abordado e o trabalho realizado pelo aluno (além da identificação da apresentação: título, nome do aluno apresentando, dia/hora da apresentação).

• Sexta Lista de Exercícios - Entrega 31/10
• Sétima Lista de Exercícios - Entrega 16/11
• Oitava Lista de Exercícios - Entrega 7/12

• Trabalho de Curso - Parte 1 - Entrega: 21/09 -- Apresentação: 21/09
• Grafos a serem usados nos estudos de caso do trabalho:

  • Grafo dos Sistemas Autônomos que formam a Internet: as_graph.txt
    Veja detalhes sobre o AS graph em BGP Routing Table Analysis Reports.

  • Grafo de colaboração entre pesquisadores da Computação: collaboration_graph.txt
    Veja detalhes sobre os dados em DBLP.

• Trabalho de Curso - Parte 2 - Entrega: 26/10 -- Apresentação: 26/10. Adiado para 31/10
• Estes grafos foram gerados aleatoriamente e não representam nenhum grafo real.
  grafo_1.txt
  grafo_2.txt
  grafo_3.txt
  grafo_4.txt
  grafo_5.txt
  
• Trabalho de Curso - Parte 3 - Entrega: 5/12 -- Apresentação: 5/12
• Grafos a serem utilizados nos estudos de caso:
  
• 5 pontos: points-5.txt (grafico)
• 10 pontos: points-10.txt (grafico)
• 20 pontos: points-20.txt (grafico)
• 50 pontos: points-50.txt (grafico)
• 80 pontos: points-80.txt (grafico)
• 100 pontos: points-100.txt (grafico)
• 150 pontos: points-150.txt (grafico)
• 200 pontos: points-200.txt (grafico)
• 500 pontos: points-500.txt (grafico)
• 1000 pontos: points-1000.txt (grafico)
• 1500 pontos: points-1500.txt (grafico)
• 2000 pontos: points-2000.txt (grafico)
• 2500 pontos: points-2500.txt (grafico)

Visualize aqui seu percurso e o comprimento!

Confira abaixo os grupos que realizaram o trabalho e o desempenho dos seus respectivos algoritmos em cada um dos grafos acima. O trabalho do grupo 11 (Ramon e Igor) teve o melhor desempenho em todos os casos (menos no caso 100 pontos). Parabéns aos dois pela criatividade e dedicação para encontrar percursos curtos!

• Primeira prova: 28/09 (quarta) às 8h (pontualmente).
• Segunda prova: 7/12 (quarta) às 8h (pontualmente).
• Prova final: 14/12 (quarta) às 8h (pontualmente).

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

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

• Resolver ou Verificar? Uma pergunta que vale 1 milhão de dólares, por Celina M. H. de Figueiredo, Ciência Hoje, vol. 48, Nov. 2011.
• Emparelhamento em Grafos: Algoritmos e Complexidade, por Celina M. H. de Figueiredo e Jayme L. Szwarcfiter, Jornada de Atualização em Informática (JAI), 1999.