Otimização em Redes - CC0322

Informações Gerais

Nome Código
Otimização em Redes CC0322
Unidade Departamento
Centro de Ciências Estatística e Matemática Aplicada
Curso Currículo Caráter Semestre
Matemática Industrial 2011.1G Eletivo 5º
Regime
Semestral

Justicativa

Grande parte dos problemas de otimização combinatória de alta complexidade computacional ocorre em uma estrutura denominada de rede ou grafo (um conjunto de pontos relacionados por um conjunto de conexões entre eles). Exemplos práticos são as redes de transporte de corrente elétrica, de telecomunicações, de transporte terrestre e ferroviário, de abastecimento de água, de coleta e transporte de petróleo bruto de poços à refinarias, etc. Quantos aos diversos tipos de problemas com essa estrutura, citamos o roteamento de custo mínimo entre dois pontos de uma rede terrestre, o transporte de dados em redes de telecomunicações e expansão de capacidade de transporte de tais redes, localização de estações de base de transmissão celular e alocação de freqüências de comunicação entre elas, etc. Modelos matemáticos para esses problemas são obtidos a partir da estrutura em grafo que o representa e as técnicas de resolução são baseadas em algoritmos clássicos em grafos envolvendo, por exemplo, percurso, árvore geradora, emparelhamento, coloração de vértices ou arestas, etc.

Objetivos

Possibilitar ao aluno aprofundar seus conhecimentos em problemas práticos de otimização combinatória com estrutura de rede, desenvolvendo algoritmos específicos para esses problemas.

Ementa

Conceitos e definições de grafos. Representação de grafos. Grafos Eulerianos e Hamiltonianos. Percurso em grafos. Conexidade. Árvore geradora mínima e variações. Caminhos mínimos. Fluxo máximo e variações. Emparelhamentos. Localização de facilidades. Coloração. Problemas de transporte. Aplicações em grafos.

Carga Horária

Semanas Créditos Total (horas) Teórica (horas) Prática (horas) EaD (horas) Extensão (horas)
16 4 64 48 16 0 0

Bibliografia

Básica

Complementar