6898 Algoritmos em Grafos
Edição 2014/1 - Ciência da Computação
Nesta disciplina vamos estudar definições, propriedades e algoritmos em grafos.
Veja o [programa](http://www.din.uem.br/graduacao/programas-e-criterios/6898-Algoritmos em Grafos-2013.pdf) e o [critério de avaliação](http://www.din.uem.br/graduacao/programas-e-criterios/6898-Algoritmos em Grafos-crit 2013.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.
Atendimento
- Segunda-feira, 18:00 as 19:10, sala 204
- Quinta-feira, 15:30 as 17:10, sala 204
- Entre em contado com o professor se precisar de atendimento em outro horário
Plano de acompanhamento de estudos
O aluno matriculado em componente curricular em regime de dependência e com conflito de horário deve requerer pela secretaria acadêmica virtual o plano de acompanhamento de estudos até o dia 28/02 (Portaria 010/2014-PEN).
De acordo com o plano de acompanhamento de estudos, os alunos devem desenvolver uma atividade após cada módulo como forma de obter presença na disciplina.
As atividades devem estar de acordo com as seguintes normas:
- Manuscrito de punho próprio
- Papel A4 branco
- Escrever na primeira linha com caneta vermelha: nome do acadêmico e RA
- Escrever na segunda linha com caneta vermelha: código da disciplina, turma e número da atividade
Avaliações
- 1° avaliação (peso 4)
- 02/04 - Prova escrita (conteúdo: primeira parte)
- 23/04 - Prova substitutiva (conteúdo: primeira parte)
- 2° avaliação (peso 1)
- 22/04 (até as 23h) - Trabalho graphun
- 3° avaliação (peso 4)
- 11/06 - Prova escrita (conteúdo: segunda parte)
- 4° avaliação (peso 1)
- 16/06 (até as 23h) - Trabalho tsp
- Exame
- Data a definir - Prova escrita (conteúdo: primeira e segunda parte)
Material
O livro base para esta disciplina é Algoritmos: Teoria e Prática, 3ª edição.
Aulas
Segunda parte
| Data | Conteúdo | Downloads | Plano de acompanhamento de estudos |
|---|---|---|---|
| 25/04 e 30/05 | Árvores geradoras mínimas | Notas de aula, exercícios | Exercícios: 9.3, 9.4, 9.8 e 9.9. Data de entrega: 07/05 |
| 07, 09 e 14/05 | Fluxo em redes | Notas de aula, exercícios | Exercícios: 10.2, 10.4, 10.7 e 10.9. Data de entrega: 21/05 |
| 16/05 | Ciclos eulerianos e o problema do carteiro chinês | Notas de aula, exercícios | Exercícios: 11.2 a 11.4. Data de entrega: 23/05 |
| 21 e 23/05 | Ciclos hamiltonianos e o problema do caixeiro viajante | Notas de aula, exercícios | Exercícios: 12.1 e 12.2. Data de entrega: 06/06 |
| 28/05 | Apresentação do trabalho tsp | ||
| 30/05 | Grafos planares | Notas de aula, exercícios | Exercícios: 13.1 a 13.3. Data de entrega: 06/06 |
| 04/06 | Coloração de grafos | Notas de aula, exercícios | |
| 06/06 | Exercícios | ||
| 11/06 | Avaliação |
Primeira parte
| Data | Conteúdo | Downloads | Plano de acompanhamento de estudos |
|---|---|---|---|
| 05/02 | Apresentação da disciplina | ||
| 07/02 | Introdução | Notas de aula, exercícios | Exercícios: todos. Data de entrega: 07/03 |
| 12, 14 e 19/02 | Representação computacional | Notas de aula, exemplos de implementação, exercícios | Exercícios: 2.1 a 2.5. Data de entrega: 07/03 |
| 21/02 | Busca em largura | Notas de aula, exercícios | Exercícios: 3.4 a 3.7. Data de entrega: 12/03 |
| 26/02 | Busca em profundidade | Notas de aula, exercícios | Exercícios: 4.5 a 4.10. Data de entrega: 12/03 |
| 28/02 | Ordenação topológica | Notas de aula, exercícios | Exercícios: 5.3 a 5.5. Data de entrega: 14/03 |
| 07/03 | Componentes fortemente conexos | Notas de aula, exercícios | Exercícios: 6.1 a 6.4. Data de entrega: 14/03 |
| 12/03 | Apresentação trabalho grafun | ||
| 14 e 19/03 | Caminhos mínimos de única origem | Notas de aula, exercícios | Exercícios: 7.2 a 7.4, 7.9 e 7.11. Data de entrega: 26/03 |
| 26 e 28/03 | Caminhos mínimos de todos os pares | Notas de aula, exercícios | Exercícios: 8.1 a 8.4. Data de entrega: 04/04 |
| 02/04 | 1° avaliação | ||
| 04/04 | Correção da 1° avaliação | ||
| 09, 11 e 16/04 | Revisão e exercícios | ||
| 23/04 | 1° avaliação (sub) |