16 décembre 2004
En 1973, J. Morgenstern a publié un article fort élégant intitulé “Lower Bounds on the Linear Complexity of the Fast Fourier Transform”. Alors que la complexité du calcul de la transformée de Fourier discrète est encore un problème ouvert, J. Morgenstern a pu établir une borne inférieure optimale en Omega(n log n) pour toute une classe d’algorithmes et, en particulier, pour les programmes d’arithmétique linéaire où les valeurs scalaires sont de module borné. Cet article fait partie d’une série de publications de J. Morgenstern sur les modèles restreints de calcul. Dans mon exposé, je m’attacherai à poursuivre cette tradition en considérant la limitation des classes “naturelles” d’algorithmes pour résoudre des problèmes d’optimisation ou de recherche.
La conception de nouveaux algorithmes ainsi que les cours et les ouvrages sont organisés en termes de “paradigmes de programmation” tels que les algorithmes gloutons, le backtracking, la programmation dynamique, la recherche locale, les rapports primal/dual, etc. Si nous pensons être en mesure de décrire intuitivement ce que nous avons à l’esprit en évoquant ces classes d’algorithmes, nous ne réussissons que rarement (sinon jamais) à définir précisément ce que nous entendons par algorithme glouton, programmation dynamique, etc.
En m’appuyant sur des travaux menés avec des co-auteurs, je voudrais proposer quelques définitions précises pour certains de ces paradigmes de la programmation comme les algorithmes gloutons, la programmation dynamique (simple), le backtracking et les algorithmes fondés sur des méthodes de dualité locale.
Je terminerai par la question : qu’est-ce qu’un bon modèle algorithmique? Il doit capturer la plupart des algorithmes connus (au sein d’un paradigme donné), avoir un certain attrait mathématique, être susceptible d’être analysé et (au moins par la suite) conduire vers de nouveaux concepts et algorithmes. Je laisserai à l’auditoire le soin de juger la pertinence de notre propos.
Allan Borodin (University of Toronto)
Vidéo indisponible
