Universidade Federal do Espírito Santo

Portal do Ementário

Informações Gerais
Disciplina:
Otimização em Grafos ( PINF6020 )
Unidade:
Coordenação do Programa de Pós-Graduação em Informática
Tipo:
Optativa
Período Ideal no Curso:
Sem período ideal
Nota Mínima para Aprovação:
6.00
Carga Horária:
45
Número de Créditos:
3

Objetivos

Ementa
* Introdução aos Problemas de Fluxo em Redes: Modelo Geral de Fluxo de Custo Mínimo, Subproblemas e Aplicações. * Ferramentas Básicas de Grafos: Algoritmos de busca e Ordenação Topológica. Problemas de Caminhos Mínimos: Caracterização, Aplicações e Algoritmos de Rotulação. * Problemas de Fluxo Máximo: Caracterização, Aplicações, Procedimento Básico do Caminho de Incremento de Fluxo, * Algoritmos de Rotulação, * Teorema básico de Max-Flow e Min-Cut e suas implicações combinatoriais. Problema de Fluxo de Custo Mínimo: Condições de Otimalidade, Dualidade, Algoritmo de Cancelamento de Ciclos.

Bibliografia
* Ahuja, R.K., Magnanti, T.L. and Orlin, J.B. (1993) . Network Flows: Theory, Algorithms, and Applications, ed. Prentice Hall. * Bertsekas, D.P. (1998) - Network Optimization . Continuous and Discrete Models, ed. Athena Scientific, Belmont, Mass. USA.

Bibliografia Complementar
Carregando...