MAC5781 + MAC0325
Otimização Combinatória
2002 semestre 1
Minhas notas de aulas, em formato PDF. Use o Acrobat Reader para tirar proveito dos hyperlinks.
Esta disciplina estuda um dos assuntos mais úteis da Otimização Combinatória: o fluxo em redes (= network flow). O problema mais geral da área é o do fluxo viável de custo mínimo (min-cost flow), que generaliza problemas célebres e importantes como o do caminho mínimo, o do fluxo máximo, o do transporte, o da circulação viável, o do emparelhamento máximo, etc. Pretendemos estudar algoritmos eficientes para todos esses problemas. MAC5781 é disciplina de pós-graduação em Ciência da Computação da USP. MAC0325 é disciplina optativa do curso de graduação em Ciência da Computação da USP.
MAC5781 não tem pré-requisitos oficiais. O pré-requisito oficial de MAC0325 é MAC0122 (Princípios de Desenvolvimento de Algoritmos). No entanto, é recomendável que os alunos já tenham cursado Análise de Algoritmos (MAC5711 ou MAC0338), Estruturas de Dados (MAC5710 ou MAC0323) e Teoria dos Grafos (MAC5770 ou MAC0328). Também são úteis conhecimentos de Programação Linear (MAC5790 ou MAC0315).
Paulo Feofiloff, sala 287, bloco A. |