5189 Algoritmos em Grafos

Nesta disciplina vamos estudar definições, propriedades e algoritmos em grafos.

Veja o [programa](http://www.din.uem.br/graduacao/programas-e-criterios/5189-Algortimos em Grafos-programa.pdf) e o [critério de avaliação](http://www.din.uem.br/graduacao/programas-e-criterios/5189-Algortimos em Grafos-crit 2012.pdf) da disciplina.

Os alunos desta disciplina devem inscrever-se no grupo uem-grafos para receberem informações e discutirem o conteúdo da disciplina. Por favor, use o seu nome verdadeiro na lista para o professor poder identificá-lo.

Avaliações

• Exame
  • 26/06 - Prova escrita (conteúdo: primeira e segunda parte)
• 2° avaliação
  • 12/06 - Prova escrita (conteúdo: segunda parte). Valor: 80% da nota.
  • 16/06 - Trabalho graphard. Valor: 20% da nota.
• 1° avaliação
  • 15/04 - Prova escrita (conteúdo: primeira parte). Valor: 80% da nota.
  • 05/05 - Trabalho grafun. Valor: 20% da nota.

Material

O livro base para esta disciplina é Algoritmos: Teoria e Prática, 3ª edição.

Os materiais utilizados em sala de aula estão disponíveis para download logo abaixo. O estudo utilizando apenas este material não é suficiente para o acompanhamento da disciplina. Recomendamos a leitura das referências no final de cada apresentação e a resolução (por parte do aluno) de todos os exercícios listados no material.

Aulas

Segunda parte

• Caminhos mínimos de todos os pares (22/04)
• Caminho euleriano e o problema do carteiro chinês (Material professor Ademir) (24/04 e 29/04)
• Avaliação substitutiva (06/05)
• Caminho hamiltoniano e o problema do caixeiro viajante (Material professor Ademir) (08/05 e 15/05)
• Grafos planares (20/05)
• Implementação do trabalho (22/05)
• Correção do trabalho 1 (27/05)
• Fluxo em redes (29/06 e 03/06)
• Implementação do trabalho e resolução de exercícios (05/06 e 10/06)
• 2° avaliação (12/06)
• Resolução da avaliação 2 (reposição da aula do dia 04/02) (17/06)

Primeira parte

• Apresentação da disciplina (06/02)
• Introdução (histórico, definições e propriedades) (18/02, 20/02)
• Representações computacional - Exemplo simples de implementação (25/02, 27/02, 04/03)
• Busca em largura (06/03)
• Busca em profundidade (11/03)
• Ordenação topológica (13/03)
• Componentes fortemente conexos (18/03)
• Resolução de exercícios (20/03)
• Árvores geradoras mínimas (25/03 e 27/03)
• Apresentação do trabalho (01/04)
• Caminhos mínimos de única origem (03/04 e 08/04)
• Resolução de exercícios (10/04)
• 1° avaliação (15/04)
• Resolução da 1° avaliação (17/04)