Intervenants : Victor Chepoi (responsable), Stéphane Grandcolas (responsable), Yann Vaxès,
Début des cours : vendredi 10 septembre 2010
Livre de référence : T. Cormen, C. Leiserson, R. Rivest, Introduction à l'algorithmique, Dunod, Paris.
Les tps sont à rendre à la fin de la dernière séance prévue pour le tp (ou à la rigueur au tout début de la séance suivante).
Dans le continuité du cours Algorithmique 1, l'objectif dans cette unité est d'étudier des algorithmes, des stratégies de résolution et des structures de données, et de les mettre en oeuvre sur des problèmes classiques.
Dans le domaine des graphes nous nous intéressons à diverses approches pour le calcul d'arbres couvrants et le calcul de plus courts chemins, et nous abordons le problème du calcul de flots maximaux. Nous présentons ensuite des structures de données complexes, comme les AVL-arbres, les B-arbres ou les tas binomiaux. Enfin nous explorons diverses stratégies et techniques pour la résolution de problèmes, comme l'approche {\em diviser pour régner}, la programmation dynamique, les algorithmes randomisés, et les méthodes gloutons.
Les supports de cours accessibles sur ce site correspondent aux
cours magistraux. Selon le cas vous trouverez un cours détaillé ou
seulement une copie des transparents (ou les deux). La plupart des
sujets abordés sont des chapitres du livre cité plus haut (dont nous
nous sommes généreusement inspirés d'ailleurs).