Programa
Segundo o programa oficial, os objetivos de MAC328 são (1) estudo de problemas básicos da teoria dos grafos e (2) análise e desenvolvimento de algoritmos para esses problemas. Ainda segundo o programa oficial, o conteúdo de MAC328 é o seguinte:
Grafos: estruturas de dados para representação de grafos.
Caminhos de comprimento mínimo.
Árvores: árvores geradoras de grafos.
Grafos conexos: componentes e cortes.
Grafos biconexos: pontes, circuitos.
Grafos dirigidos: grafos fortemente conexos.
Emparelhamentos: emparelhamentos máximos em grafos bipartidos.
Introdução ao problema do fluxo máximo.
Alguns problemas difíceis: coloração de vértices, coloração de arestas, circuitos hamiltonianos.
Vamos usar o
Stanford GraphBase
(seguindo a tradição inaugurada pelo
professor Yoshiharu Kohayakawa em 1996).
Com isso, o programa oficial poderá não ser seguido à
risca.
MAC328 não é uma disciplina do tipo tradicional.
MAC328 não é uma disciplina "de teoria".
MAC328 é um laboratório de algoritmos em grafos.
Pré-requisitos
O único pré-requisito de MAC328 é MAC122 (Princípios de Desenvolvimento de Algoritmos). Em particular, supõe-se que os alunos tenham um razoável conhecimento da linguagem C.
Livros e software
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 [ps, pdf] que descreve o livro e o software. Há uma cópia desse extended abstract, em papel, na pasta 6 da loja de reprografia no bloco B do IME. O SGB está instalado nas redes UNIX e Linux do IME.
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!
Horário, critério de avaliação, etc.
A disciplina tem carga horária semanal de 4 horas de aulas (aproximadamente 30 horas de aulas no semestre) e dá direito a 4 créditos.
Horário: Terças-feiras das 10h00m às 11h50m e sextas-feiras da 8h00m às 9h50m.
Local: Sala 3 do bloco B, prédio do IME.
Provas: Teremos 3 provas, no horário da aula da terça-feira. Veja datas no registro de aulas e provas. Não haverá prova substitutiva. A média das provas será P = (P1 + P2 + P3 - Q)/2 , onde P1, P2 e P3 são as notas das provas e Q é a pior das três notas.
Exercícios: Teremos alguns (uma dezena, talvez) exercícios/projetos. Alguns serão do tipo lapis-e-papel, podendo acontecer durante uma aula; outros envolverão criação e teste de um programa C. Cada exercício valerá um certo número de pontos. A nota de exercícios será calculada pela fórmula E = 10×X/S , onde X é o total de pontos acumulado pelo aluno e S é o total de pontos que um bom aluno obteria.
Publicação das notas: Minha avaliação dos alunos será publicada na página www.ime.usp.br/~pf/mac328/marks/notas.html.
Critério de avaliação: A nota final, F, será calculada pela fórmula se P > 5 e E > 5 então F = 0,65×P + 0,35×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 data da prova no cronograma. 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.
Mailing list
Há uma mailing list para troca de mensagens, avisos e informações entre os envolvidos com MAC328 (alunos, professores, demais interessados). Qualquer mensagem para o endereço
xxxx
será automaticamente redistribuída para todos os assinantes da lista. A lista se destina principalmente à troca de idéias entre os alunos. Eu pretendo participar, mas meu papel será secundário.
Procure mandar mensagens sem qualquer formatação (sem mime, sem html, em texto puro). Ao mandar uma mensagem, não deixe de dizer qual o assunto (campo "Subject"). Só use reply (resposta) a partir de uma mensagem se você estiver tratando do mesmo assunto que a mensagem em questão; caso contrário, componha uma nova mensagem. A propósito, veja a página de netiqueta de Maria Alice Soares de Castro.
- Assinatura
-
- Todos os alunos de MAC328 devem ser assinantes da mailing list. Candidatos a alunos e demais interessados também são bem-vindos. O procedimento de assinatura é simples: basta mandar uma mensagem vazia, sem subject, para
xxxx
- Você receberá um pedido de confirmação por e-mail; basta dar um reply. Para pedir ajuda sobre o funcionamento da lista (por exemplo, instruções para cancelar a inscrição), mande mensagem vazia para xxxx.
- Todos os alunos de MAC328 devem ser assinantes da mailing list. Candidatos a alunos e demais interessados também são bem-vindos. O procedimento de assinatura é simples: basta mandar uma mensagem vazia, sem subject, para
- Arquivo da lista
-
- As mensagens enviadas para a lista serão arquivadas de maneira organizada. Você pode examinar as mensagens arquivadas por assunto ou em ordem cronológica inversa.