Algorithmes et Complexité

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é? ( correction 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  donccapables:


<ol>


<li> d'analyser un probl&egrave;me - mod&eacute;lisation, reformulation, complexit&eacute;, r&eacute;duction. </li>


 

<li> de concevoir une solution algorithmique appropri&eacute;e, exacte ou approch&eacute;e,  en particulier en utilisant &agrave; bon escient les  structures et paradigmes classiques- programmation dynamique, algorithme glouton, recherche exhaustive,  heuristique, ...- </li>


<li>  d'analyser  cette solution -correction, complexit&eacute;, efficacit&eacute;, ... . </li>

 

</ol>

Contenu

  1. Paradigmes classiques de conception d'algorithmes (programmation dynamique, diviser et régner, algorithmes gloutons, backtracking, ...).
  2. Complexité de problèmes, Classes P, NP et EXPTime, Réductions polynomiales, NP-dureté.
  3. 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, ...)
  4. Le cours pourra être complété par une ou deux séances : décidabilité, éthique des algorithmes, ...