6898 Algoritmos em Grafos

Nesta disciplina vamos estudar conceitos e definições de grafos, modelagem de problemas por grafos, algoritmos em grafos e implementação de soluções computacionais utilizando grafos.

O livro base para a disciplina é “Algoritmos: Teoria e Prática”, Cormen at. all, 3º Edição. Você também pode usar a 2º Edição do livro, neste caso, veja a errata com importantes correções nos termos usados em português. O autor do livro fornece uma errata para a 3º em inglês em sua página pessoal.

Avaliações

• Trabalho 1
  • Implementação e teste de algoritmos de geração de árvores aleatórias
  • Datas de entrega: 14/10, 21/10, 04/11, 11/11 e 25/11
• Prova 1
  • Conteúdo: conceitos, representações, buscas e aplicações, árvores geradoras mínimas
  • Data: 18/11
  • Aula de revisão: 11/11 (turma 1) e 13/11 (turma 2)
• Trabalho 2
  • Lista de exercícios
  • O trabalho é em equipe de duas pessoas. O compartilhamento de informações entre as equipes é permitido e aconselhado, mas o compartilhamento do texto das respostas não é permitido. Trabalhos que tenham respostas iguais serão anulados. Se algum aluno ficar sem equipe, ele pode fazer o trabalho individualmente e entregar apenas metade dos exercícios (os pares ou os ímpares).
  • O trabalho deve ser entregue manuscrito (pelos autores do trabalho) em papel A4.
  • Datas de entrega: 21 e 27/01/2020 (parte 1 e parte 2, respectivamente)
• Prova 2
  • Conteúdo: caminhos mínimos, fluxo em redes, ciclos eulerianos e problema do carteiro chinês, ciclos hamiltonianos e o problema do caixeiro viajante e grafos planares.
  • Data: 27/01/2020

Aulas

Atenção: o propósito das notas de aula a seguir é guiar a aula e o estudo individual, mas elas sozinhas não são suficientes para acompanhar a disciplina. Você deve ler o livro, consultar as demais referências e principalmente fazer os exercícios.