Algoritmos em Grafos - TCC-00.176
Segundo Semestre de 2011 - Turma A-1
Prof. Fábio Protti - sala
301 (3o. andar - Bloco E - Instituto de Computação) – fabio@ic.uff.br
Horário da disciplina: 2as e 5as, 7:00 - 9:00
Local: Sala 235 (segundas) e Sala 233
(quintas)
ATENÇÃO – NOTAS DA VS
CARLOS HEITOR 6.0, GUILHERMO 6.0, MARCO GABRIEL 7.0, MAXIMIANO 5.0,
THIAGO MILANEZ 6.0
CALENDÁRIO DO CURSO:
AGOSTO
08 – Introdução a grafos. Definições
básicas. Grafos como estruturas de dados.
11 – Conceitos importantes de Teoria de
Grafos. Explicação sobre o Trabalho de Implementação.
15 – Grafos Eulerianos.
Algoritmo para Trilhas Eulerianas.
18 – Busca em profundidade em grafos.
22 – Algoritmo para determinar articulações
e blocos de um grafo.
25 –
Conceito de digrafo
(grafo direcionado). Busca em profundidade em digrafos.
29 – Algoritmo para determinar
componentes fortemente conexas de um digrafo.
SETEMBRO
01 – Busca em largura em grafos.
05 – Algoritmo de Dijkstra
para caminhos mínimos em digrafos.
08 – Algoritmo de Floyd-Warshall para caminhos mínimos entre todos os pares de
vértices de um digrafo.
12 – Algoritmos de Kruskal
e Prim para determinação de árvores geradoras
mínimas.
15 – Aula de revisão e exercícios.
19 – Primeira Prova
22
– Resolução e Vista da Primeira Prova
26 – Algoritmos de ordenação topológica
de um dígrafo acíclico.
29
– Fluxos em redes – Parte I.
OUTUBRO
03
– Fluxos em redes – Parte II.
06
– Fluxos em redes – Parte III.
10 – Não haverá aula (prof. em viagem de
intercâmbio)
13 – Não haverá aula (prof. em viagem de
intercâmbio)
17 – Não haverá aula (Semana Acadêmica)
20 – Não haverá aula (Semana Acadêmica)
24
– Emparelhamentos – Algoritmo dos caminhos aumentantes.
27
– Método Húngaro para emparelhamentos em
grafos bipartidos – Parte I.
NOVEMBRO
03
– Método Húngaro para emparelhamentos em
grafos bipartidos – Parte II.
10 – O Problema do Caixeiro Viajante
(PCV). Algoritmo exato para o PCV.
14 – Não haverá aula (Recesso: República)
17 –
O Problema do Carteiro Chinês.
21 – Não haverá aula (Recesso: Araribóia)
24 – Resolução
de dúvidas sobre o Trabalho de Programação
28 – Aula de revisão e exercícios para a
Segunda Prova.
DEZEMBRO
01 – Segunda Prova
04 – DATA LIMITE PARA ENTREGA DOS TRABALHOS (é um domingo)
05
– Resolução e Vista da Segunda Prova
08 – VS
12
– Resolução e Vista da VS
15 – FINAL DO PERÍODO
Estrutura do Curso
Aulas Teóricas. Lista de
Exercícios Sugeridos. Trabalho de Implementação.
Recomendo fortemente que os
alunos resolvam a Lista de Exercícios Sugeridos.
Calendário de Provas
Primeira Prova: dia 19 de setembro de 2011 (resultado: dia 22 de setembro)
Segunda Prova: dia 01 de dezembro de 2011 (resultado: dia 05 de dezembro)
VS: dia 08 de dezembro de 2011 (resultado: dia 12 de dezembro)
Avaliação
Seja M=(2*P1+2*P2+T)/5, onde T é a nota do Trabalho de Implementação.
Se M >= 6,0, o aluno está aprovado.
Se M < 4,0, o aluno está reprovado.
Se 4 <= M < 6,0, o aluno deve fazer a VS.
A nota da VS deverá ser maior ou igual a 6,0.
Sobre o Trabalho de Implementação...
O Trabalho consistirá na implementação de um algoritmo, com apresentação nos dias 24 e 28 de novembro (por ordem alfabética de nome).
Cada aluno receberá o seu próprio algoritmo para implementar.
A linguagem de implementação pode ser Pascal, C, C++ ou Java.
Use o site http://uva.onlinejudge.org
O aluno deve enviar um e-mail com o fonte do algoritmo (arquivo texto)
até o prazo máximo de 27 de novembro (domingo) às 23:59:59.
Trabalhos
enviados em data/horário posterior receberão descontos proporcionais ao tempo
de atraso.
TRABALHOS
Bernardo
F. Juncal - 784 - Maze Exploration
Carlos
Heitor Diniz Moreira - 10305 - Ordering Tasks
Cinthya
de Melo França -
10099 - The Tourist Guide
Débora
de Sousa Ribeiro - 762
- We Ship Cheap
Gabriel Baptista Baleroni - 10054 - The Necklace
Guilhermo Danilo Montoya - 10067 - Playing with Wheels
Ian Castro Gopfert -
523 - Minimum Transport Cost
João
Augusto B. V. de Souza - 532 - Dungeon Master
João
Paulo F. de Melo - 10034 - Freckles
Jorge
Thiago Peregrino de Oliveira - 10004 - Bicoloring
Julio
Cesar do Nascimento Rocha - 10099 - The Tourist Guide
Leonardo Lessa Aramaki - 532 - Dungeon Master
Leonardo
Muniz Nascimento - 523
- Minimum Transport Cost
Marco Gabriel Moreira
Barcellos - 10054
- The Necklace
Marcos
Antônio Almeida Paulino - 10305 - Ordering Tasks
Maximiano Campos Pereira - 10067 -
Playing with Wheels
Matheus Lima - 10034 - Freckles
Robison Meirelles
Jr. - 762 - We Ship Cheap
Thiago
Milanez - 784 -
Maze Exploration
Ygor
Ferreira de Carvalho - 10004 - Bicoloring
Bibliografia
Jayme L. Szwarcfiter. Grafos e Algoritmos Computacionais. Campus, Rio de Janeiro, 1986.
Alan Gibbons.
Algorithmic Graph Theory. . Cambridge University Press, 1985.
T. H. Cormen
e outros. Algoritmos (tradução da 2a.
Edição Americana). Campus, RJ, 2002.
Downloads
Lista de
Exercícios Sugeridos - I
Lista de Exercícios Sugeridos -II