COS608, Otimização de Fluxos em Grafos

MAB353 - Tópicos de Matemática Aplicada A

2024/1, Engenharia de Computação e Informação, Engenharia Matemática, Bacharelado em Ciência da Computação e Bacharelado em Matemática Aplicada
Professora Márcia R. Cerioli, Instituto de Matemática e PESC/COPPE - UFRJ

Objetivos:

Conhecer com detalhes o Problema do Fluxo Máximo com Redes, seus algoritmos (com corretude e complexidade) suas variantes e suas aplicações.

Programa:

  1. Conceitos, definições e notações de grafos, digrafos e redes
  2. Grafos com pesos nas arestas e redes
  3. Corte em grafos e corte mínimo
  4. O problema do fluxo máximo
  5. ...
  6. Teorema de Ford e Fulkerson
  7. Busca em Grafos: Largura e Profundidade (revisão)
  8. Caminhos mínimos em grafos (revisão)
  9. Vários algoritmos para a resolução do problema do fluxo máximo com capacidades racionais
  10. ...
  11. O problema do fluxo de custo mínimo
  12. Vários algoritmos para a resolução do problema do fluxo de custo mínimo
  13. Exemplos de aplicações do problema

Ementa (formal, do SIGA):

Fluxo em redes; modelos; algoritmo genérico de aumento de fluxo, algoritmo de rotulação, Ford-Fulkerson; complexidade; fluxo máximo com limite inferior positivo; fluxo de custo mínimo, algoritmo de Busacker-Gowen; algoritmo out-of-kilter-

Pré-requisitos:

Alguma maturidade em grafos, algoritmos ou em técnicas de provas de teoremas. Em geral, a partir do terceiro ou quarto período, tendo obtido aprovação em boa parte das disciplinas do primeiro ano. Para os alunos da ECI, os pré-requisitos formais são COS242 e COS360. Porém, todos os resultados serão revisados nesta disciplina, logo é possível pedir dispensa do pré-requisito (a ser negociado com o coordenador do curso). Os algoritmos de busca em grafos, e de caminho mínimo em grafos que forem necessários para o entendimento dos algoritmos de fluxo máximo serão revisados com os devidos detalhes ao longo do semestre e não é necessário conhecê-los a priori.

Informações importantes:

Esta é uma das Disciplinas Optativas (Escolha Condicionada) da grade do curso de Engenharia de Computação e Informação. Carga horária de 5 créditos, com 4 horas de aula por semana.
Para os alunos de Matemática Aplicada e de Engenharia Matemática, ela está sendo oferecida também como MAE353 - Tóps em Mat Aplicada A (Otim Fluxo Grafos). Observe que que ao se inscrever nesta turma, no histórico aparecerá MAE353 - Tópicos em Matemática Aplicada A e, portanto, não é uma disciplina de ECI, mas é da listagem de escolha restrita da MAP-Computação científica.
No curso de Ciência da Computação, não foi possível negociar uma equivalência com disciplina eletiva de escolha condicionada mas sempre pode ser cursada como eletiva livre.
Se você é aluno de outro curso não listado aqui e deseja cursar esta disciplina, veja com seu coordenador, ou diretamente com a professora, sobre quais as possibilidades para a inscrição ser efetivada e como ela será melhor aproveitada em seu curso.
Página atualizada em 27 mar 2024 por Márcia R. Cerioli