Algorithmes et complexité

Chargé de TD et TP au semestre 1 (Master 1)

Objectifs

Le but de l’algorithmique peut être résumé par: trouver un « bon » algorithme pour un problème donné. Cela soulève de nombreuses questions:

  1. Existe-t-il un algorithme pour résoudre le problème? ( calculabilité, indécidabilité).
  2. Le problème est-il un « classique »? (modélisation, reformulation, connaissances).
  3. Comment concevoir un algorithme? (algorithmes corrects par construction, paradigmes)
  4. L’algorithme apporte-t-il bien la réponse au problème donné? ( orrection des algorithmes)
  5. Que dire des ressources utilisées par l’algorithme? (analyse d’algorithmes)
  6. L’algorithme est-il « raisonnablement » efficace? Pourrait-on faire mieux? Que dire des ressources minima nécessaires pour résoudre le problème? (complexité des problèmes)
  7. Peut-on espérer avoir un algorithme « rapide » exact? Le problème est-il « dur »? (NP-dureté)
  8. Que faire face à un problème dur?

L’objectif du cours est de préparer les étudiants à répondre à ces questions difficiles, de les entraîner au « computational thinking« . A l’issue de ce module, les étudiants doivent être donc capables:

  1. d’analyser un problème – modélisation, reformulation, complexité, réduction.
  2. de concevoir une solution algorithmique appropriée, exacte ou approchée, en particulier en utilisant à bon escient les structures et paradigmes classiques- programmation dynamique, algorithme glouton, recherche exhaustive, heuristique, …-
  3. d’analyser cette solution -correction, complexité, efficacité, … .

Contenu

  1. Rappels sur les notions de complexité et correction d’algorithmes.
  2. Paradigmes classiques de conception d’algorithmes (programmation dynamique, diviser et régner, algorithmes gloutons, backtracking, …).
  3. Complexité de problèmes, Classes P, NP et EXPTime, Réductions polynomiales, NP-dureté.
  4. Quelques méthodes « avancées » pour résoudre de manière exacte ou approchée des problèmes NP-durs (Branch-and-Bound, algorithmes probabilistes, heuristiques, méta-heuristiques, …)

Bibliographie

Il y a de nombreuses ressources en ligne sur le domaine. Il y a également de nombreux livres excellents sur l’algorithmique et la complexité, par exemple:

  1. Introduction à l’algorithmique, par Thomas H. Cormen, Charles Leiserson, Ronald Rivest, (Editions Dunod, disponible à la BU), livre référence en algorithmique
  2. Algorithms, par Robert Sedgewick et Kevin Wayne, qui se présente comme essential information that every serious programmer needs to know about algorithms and data structures avec un site associé à la quatrième édition
  3. Algorithm Design Manual, avec beaucoup d’applications concrètes, par Steven Skiena dont le site contient de nombreuses ressources en ligne
  4. Algorithm Design, par John Kleinberg et Eva Tardos (Editions Addison Wesley 2005) qui est aussi tourné vers les applications (voir le site associé )
  5. A guide to Algorithm Design, par Anne Benoit, Yves Robert et Frédéric Vivien, (Editions CRC Press) avec de nombreux exercices corrigés
  6. Sur l’aspect « algorithmic pattern », par Bruno R. Preiss, Data Structures and Algorithms with object-oriented design patterns in Java, disponible sur le Web.