MAC0325 + MAC5781 Otimização Combinatória

  Otimização combinatória é um campo da matemática aplicada que usa técnicas de combinatória, programação matemática e teoria de algoritmos para resolver problemas em otimização sobre estruturas discretas.

  Problemas em otimização combinatória têm sido um tópico central para a evolução de algoritmos e da teoria de complexidade computacional. Pesquisadores têm apresentado muitas idéias criativas para o projeto de algoritmos eficientes baseados em conceitos e resultados na área. Métodos desenvolvidos para problemas em fluxos em redes, como o primal-dual, têm se mostrado muito úteis no projeto e análise de uma variedade de algoritmos para problemas em outros domínios. Muitas das idéias inovadoras têm se baseado em um conjunto não muito grande de princípios comuns que são simultaneamente simples e poderosos, como scaling.

  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).