MAC0328 Algoritmos em Grafos

Bem-vindo!

Bem-vindo à MAC0328 Algoritmos em Grafos. Esta é uma disciplina introdutória em projeto, análise e implementação de algoritmos envolvendo grafos. Abaixo encontra-se uma descrição de alguns dos ingredientes principais desta disciplina.

Introdução

MAC0328 Algoritmos em Grafos é uma disciplina introdutória em projeto e análise de algoritmos em grafos. Nesta disciplina veremos algumas técnicas e algoritmos muito bacanas (e muito utilizados).

MAC0328 não é uma disciplina do tipo tradicional. MAC0328 não é uma disciplina "de teoria". MAC0328 é um laboratório de algoritmos em grafos.

Vamos usar o Stanford GraphBase (SGB), seguindo a tradição inaugurada pelo professor Yoshiharu Kohayakawa em 1996. Todas as implementações serão feitas em C utilizando a plataforma do SBG. Além disso os alunos são encorajados a escreverem seus programas utilizando a dupla CWEB+SGB.

Dá para se divertir bastante em MAC0328.

Divirtam-se!

Objetivos  e  conteúdo

O objetivo desta disciplina é apresentar técnicas, algoritmos e estruturas de dados empregados no projeto e implementação de algoritmos para resolução de problemas envolvendo grafos. Pretendemos mostrar estratégias clássicas e muito bacanas de solução de alguns problemas em grafos. Segundo o programa oficial, o conteúdo de MAC0328 é o seguinte

Grafos: estruturas de dados para representação de grafos.
Caminhos de comprimento mínimo.
Árvores: árvores geradoras e cortes.
Grafos biconexos: pontes, circuitos.
Grafos orientados: grafos fortemente conexos.
Emparelhamentos: emprarelhamentos máximos em grafos bipartidos.
Introdução ao problema do fluxo máximo.
Alguns problemas (NP-)díficeis: coloração de vértices, coloração de arestas, circuitos hamiltonianos.

Pré-requisitos

O único pré-requisito de MAC0328 é MAC122 (Princípios de Desenvolvimento de Algoritmos).   Em particular, supõe-se que os alunos tenham um razoável conhecimento da linguagem C.

Critério de avaliação

A nota final na disciplina será baseada em dois componentes:

Exercícios-programas. Nesta disciplinas teremos uma meia duzia de 7 ou 8 exercícios-programas (EPS) em C. Cada EP vale um certa número de pontos, dependendo da sua dificuldade. A nota E de exercícios-programas será calculada pela fórmula  

E = 10×X/S

onde  X  é o total de posntos acumulado pelo aluno  e  S  é o total de pontos possíveis.

Provas. Teremos 3 provas nesta disciplina. Todas as provas serão às quartas-feiras. Veja as datas no registro de conteúdo das aulas. Não haverá prova substitutiva. A média P das provas será  

P = (P1 + P2 + P3)/3

onde, P1, P2 e P3 são as notas das três provas.

Nota final. A nota final;  F,  será calculada pela regra  

se  P >= 5  e  E >= 5 , então  F = 0,6×P + 0,4×E , senão  F = min{P,E}

Recuperação. Os alunos que obtiverem  F  entre 5 e 3 e tiverem freqüência >= 70% poderão se submeter à prova de recuperação. Veja a data da prova no registro de conteúdo das aulas.  A nota final depois da recuperação será a maior dentre 

0,5×F + 0,5×R 

e  F ,  onde R é a nota da prova de recuperação. 

Bibliografia  e  implementações

Para preparar as aulas desta disciplina estarei consultando as notas de aula das edições passadas desta disciplina (edição de 1998, edição de 2001) e os livros descritos mencionados abaixo.

Nosso principal material de estudo será o pacote de software Stanford GraphBase (SGB, para simplificar). O pacote está extremamente bem documentado no livro

Donald E. Knuth,
The Stanford GraphBase: A Platform for Combinatorial Computing,
ACM Press e Addison-Wesley, 1993.

Veja o extended abstract [dvi, ps, pdf] que descreve o livro e o software. Há uma cópia desse extended abstract, em papel, na pasta ?? da loja de reprografia no bloco B do IME.  O SGB está instalado nas redes UNIX e Linux do IME.  Além disso, com excessão feita aos 3 primeiros capítulos do livro, uma cópia eletronica dos demais capítulos está disponível em http://www.ime.usp.br/~coelho/grafos/sgb/src.

Como referência para os conceitos e fatos básicos da teoria dos grafos, usaremos o livro

J.A. Bondy, U.S.R. Murty,
Graph Theory with Applications,
MacMillan, London, 1976.

Podemos complementar esse livro com as seções 5.4 e 5.5 e os capítulos 23 a 27 de

T.H. Cormen, C.E. Leiserson, R.L. Rivest,
Introduction to Algorithms,
MIT Press & McGraw-Hill, 1992

ou ainda com o recém publicado

Robert Sedgewick,
Algorithms in C Part 5: Graph Algorithms, 3rd.ed.
Addison Wesley, 2000.

Há uma grande quantidade de outros livros sobre teoria dos grafos nas bibliotecas e livrarias. Escolha um!

Todos os exercícios-programas de MAC0328 serão escritos em C.

O primeiro exercício-programa é um exercício de CWEB. Nesta disciplina não é importante que você aprenda a fazer programas em CWEB. O fundamental é que você saiba como lê-los. Este primeira EP deve prepará-los suficientemente para isto. O uso de CWEB nos demais EPS é facultativo, embora seja incentivado.

Todos os EPS envolvendo grafos utilizarão a plataforma para algoritmos combinatórios do SGB.

Algoritmos em Grafos na Internet

Existe muito material muito bom de Algoritmos em Grafos na Internet. Durante o andamento da disciplina estarei mantendo, na página

http://www.ime.usp.br/~coelho/grafos/sitios/,

uma lista de alguns sítios de Algoritmos em Grafos, programação literária, CWEB, SGB. Está página será atualizada e expandida a medida que eu receber o endereço de outros sítios relevantes para a disciplina. Se você encontrar algum sítio de Grafos (ou de qualquer outra coisa) que achar bacana, por favor, não deixe de me avisar.

Monitor

Os monitores desta disciplina serão monitor-1 e monitor-2. e-mail monitor-1@linux.ime.usp.br e monitor-2@linux.ime.usp.br.

Outras informações

A minha sala é a B-164, o número do meu telefone é 3091-6295 e meu endereço eletrônico é coelho@ime.usp.br.

Manterei uma página de MAC0328 no URL

http://www.ime.usp.br/~coelho/grafos/.

Nessa página colocarei o material da disciplina (como, por exemplo, exercícios-programas e notas de aula). Por favor, dê uma olhada nesta página regularmente.

Será mantida uma lista de discussão que tem como objetivo servir de suporte para a disciplina. Recomenda-se que você mande para esta lista suas dúvidas, sugestões, críticas ou observações sobre o andamento da disciplina. Assim, se você pretende cursar MAC0328, por favor, veja a página

http://www.ime.usp.br/~coelho/grafos/lista/

e inscrevá-se na lista de discussão. Sinta-se a vontade para me escrever e fazer perguntas ou comentários sobre a disciplina. Comentários anônimos podem ser enviados através de um link da página principal de Algoritmos em Grafos.