Graphes et programmation dynamique

Les graphes sont un objet mathématique très simple composé d'un ensemble de sommets dont certains sont deux à deux reliés par des arêtes. Malgré leur simplicité, ils modélisent des situations très variées et de nombreux problèmes d'optimisation sont formulés en termes de graphes. Le cours introduira les notions de base sur les graphes, leurs représentations en mémoire, les problèmes algorithmiques classiques sur ces objets et les techniques pour les résoudre. Le cours abordera en particulier les problèmes suivants: - plus courts chemins, - arbre couvrant de poids minimum, - voyageur de commerce et cycle/chemin hamiltonien, - coloration des sommets, - flot maximum et coupe minimum. Nous concevrons des algorithmes pour résoudre ces problèmes, qui mettront en œuvre des techniques générales d'algorithmique telles que la programmation dynamique, les algorithmes gloutons et l'approche diviser pour régner.