Programme
- Théorie des graphes: définitions et propriétés élémentaires, chemins, chaines et connexité, flots, couplages, recouvrements, graphes planaires, coloriages.
- Programmation dynamique: certaine, incertaine et en horizon limité.
- Programmation linéaire en nombre entiers: le problème du sac à dos simple et multidimensionnel, méthodes heuristiques et par approximations.
- Programmation linéaire: méthode du simplexe, dualité, écarts complémentaires, algorithme dual, algorithme du simplexe en variables bornées, le problème du transport.
Bibliographie
- Eléments d’algorithmique, D. Beauquier, J. Berstel, P. Chrétienne, [Masson]
- Graphes et hypergraphes, C. Berge, [Dunod]
- Graphes, C. Berge, [Gauthier-Villars]
- Graphes et algorithmes, M. Gondran, M. Minoux, [Eyrolles]
