A Otimização Combinatória trata de problemas computacionais básicos como caminho mínimo, árvore geradora mínima, fluxo máximo, corte mínimo, emparelhamento máximo, etc. A solução desses problemas envolve ideias e conceitos da programação linear e combinatória poliédrica.
Estas notas de aula foram escritas para as disciplinas de Otimização Combinatória do Instituto de Matemática e Estatística da Universidade de São Paulo. Presume-se que o leitor tem algum conhecimento prévio de teoria dos grafos, de programação linear, de análise de algoritmos, e de estruturas de dados básicas. Os sete apêndices fazem um rápido resumo dos três primeiros pré-requisitos.
As notas foram baseadas, em grande parte, no livro de Cook, Cunningham, Pulleyblank e Schrijver e nas notas de aula de Schrijver. A maior parte das figuras foi copiada (sem permissão) daquele livro e daquelas notas. Os livros de Schrijver, Grötschel–Lovász–Schrijver, Ahuja–Magnanti–Orlin, e Bondy–Murty também serviram de referência e fonte de material. A maneira de escrever pseudocódigo foi copiada de Cormen–Leiserson–Rivest–Stein.
Os exercícios marcados com ★ complementam pontos que o texto indicou mas não desenvolveu. Exercícios particularmente interessantes ou importantes também são marcados com ★. Mas essas indicações não são sistemáticas nem consistentes.
Sumário do livro:
Outros assuntos:
Projeto de Algoritmos em C |
Livro Algoritmos em C
|
Algorithms Design in C |
Desenvolvimento de Algoritmos |
Estruturas de Dados |
Literate Programming & CWEB |
O que é uma prova? |
Uma Introdução Sucinta à Teoria dos Grafos |
Exercícios de Teoria dos Grafos |
Graph Theory Exercises |
Digrafos |
Algoritmos em Grafos com Stanford GraphBase |
Algoritmos para Grafos via Sedgewick |
Teoria dos Grafos via Diestel |
Análise de Algoritmos |
Minicurso de Análise de Algoritmos |
Algoritmos de Programação Linear |
Algoritmos de Aproximação