Algoritmos em Grafos

Algoritmos em Grafos

Objetivo do curso

O curso de Algoritmos em Grafos tem o objetivo de apresentar e analisar a estrutura de dados grafos e seus algoritmos. Entender certos problemas que envolvem grafos e estudar algoritmos eficientes para esses problemas. Além de estudar algumas técnicas de projetos de algoritmos.

Ementa

Análise de Algoritmos. Representações de Grafos. Percursos em Grafos. Ordenação Topológica. Árvore Geradora Mínima. Caminhos Mínimos. Fluxo Máximo. Emparelhamento Máximo. Algoritmos Gulosos. Programação Dinâmica.

Horário de Aula

• Quintas 13:25hs - 17:00hs

Horário de atendimento

• Quintas 10:00hs - 12:00hs

Notas de Aula

• Aula 00 - Apresentação da Disciplina

• Aula 01 - Introdução à Análise de Algoritmos

• Aula 02 - Introdução à Teoria do Grafos

• Aula 03 - Representação, operações

• Aula 04 - Percurso em grafos

• Aula 05 - Árvore Geradora Mínima

• Aula 06 - Caminhos Mínimos

• Aula 07 - Backtracking + Divisão e Conquista

• Aula 08 - Algoritmos Gulosos

• Aula 09 - Programação Dinâmica

• Aula 10 - Fluxo Máximo

• Aula 11 - Emparelhamento Máximo

Exercícios

• Arquivos de instâncias pequenas de grafos

• Percurso em grafos

  1. Mice and Maze

  2. Highways

  3. Ir e vir

  4. Transmissão de energia

  5. Mesa

  6. Pedágio

• Árvore Geradora Mínima

• • Rede Ótica

  • Interligando a Sildávia

  • Lazy Student (A2)

  • The child and zoo (A2)

• Caminhos Mínimos

• • Engarrafamento

  • Caminho das pontes

  • Final mundial

• Revisão para prova

• • Apostila e exercícios de Teoria dos grafos (USP)

    • Capítulos 1, 2, 6, 7, 14, 15.

  • Grafos uma introdução

    • Capítulos 1, 2, 3, 4

Temas para Trabalhos

Descrição do Trabalho e formato de entrega

• Trabalho

***************************

Importante

1. Comece a fazer o trabalho logo, enquanto o problema está fresco na memória e o prazo para terminá-lo está tão longe quanto jamais poderá estar!

2. Graphviz

3. Prova dia -

4. Apresentação de trabalho Prático -