Cours : Yves Robert

TD : Marc De Visme & Laureline Pinault

Ce cours propose une introduction approfondie aux concepts et techniques pour concevoir des algorithmes efficaces.

Cette introduction fait suite à la formation de base dispensée dans l’option Informatique des classes préparatoires et dans les L1 et L2 d’informatique. Ce module suppose donc une familiarité élémentaire avec les concepts de base: notion d’algorithme, de complexité, de correction; structures de données de base (tableaux, listes, arbres, etc.); algorithmes classiques de recherche et de tri, etc. Il s’agit d’une formation résolument orientée vers les concepts fondamentaux et non pas vers l’applications de techniques toutes faites.

Le cours est indépendant du cours de Théorie de la Programmation et du Projet Programmation. Les travaux dirigés font l’objet d’exercices « papier & crayon », et il n’y a aucune implémentation sur machine. On peut donc le suivre en le considérant comme un cours de mathématiques discrètes … mais ce serait dommage ! Les paradigmes algorithmiques prennent tout leur sens quand on les met en oeuvre. Nous conseillons donc vivement de suivre en parallèle le Projet Programmation où seront implémentées les techniques vues en cours d’Algorithmique.

Plan

Quelques sujets abordés dans ce module:

  • Paradigmes: diviser-pour-régner, programmation dynamique, algorithmes gloutons;
  • Complexité: coûts en temps et en espace, complexité pire cas, complexité en moyenne, analyse amortie;
  • NP-complétude: les problèmes NP-complets, les réductions, les méthodes de résolution heuristiques;
  • Grands thèmes: algorithmes de recherche & de tri, calcul matriciel (eh oui, des surprises!), systèmes cryptographiques, géométrie algorithmique, reconnaissance de motifs, etc…

Le cours se prolonge au second semestre par le cours Algorithmique Avancée.

Organisation

Le cours est organisé selon le schéma hebdomadaire suivant:

  • 2h de cours;
  • 2h de travaux dirigés.

La note de contrôle continu est obtenue à partir de plusieurs devoirs à la maison et d’un partiel organisé en milieu de semestre. Un examen final est organisé en fin de semestre.

Bibliographie

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, The MIT Press, 1990. Version française: Introduction à l’Algorithmique, 2e édition, Dunod, 2004.
  2. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation: Combinatorial optimization problems and their approximability properties, Springer Verlag, ISBN 3-540-65431-3.
  3. Voir aussi la liste des problèmes d’optimisation NP tenue à jour par Pierluigi Crescenzi et Viggo Kann
  4. Herbert S. Wilf,Algorithms and Complexity , A K Peters Ltd, ISBN: 9781568811789. La première édition est accessible en ligne.
  5. La page wikipedia est claire et concise : http://fr.wikipedia.org/wiki/Théorème_de_Cook
  6. Jon Kleinberg & Éva Tardos, Algorithm Design, Addison-Wesley, ISBN-10: 0321295358
  7. M. R. Garey & D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN-10: 0716710455
  8. D. Knuth, The Art of Computer Programming, Volumes 1-3, Addison-Wesley, ISBN-10: 0201485419
  9. Polycopié du cours des années précédentes (largement repris dans le plan du cours de cette année).