Thoughts on a Theory of Algorithms  ||,Réflexions sur la théorie des algorithmes (série : Colloquium Jacques Morgenstern)

In 1973,Jacques Morgenstern published an elegant paper entitled Lower Bound on the Linear Complexity of the fast Fourier Transform. While an optimal bound for computing the Discrete Fourier Transform remains an open problem,Jacques was able to establish an optimal Omega(nlogn) lower bound for a very natural class of algorithms,namely linear arithmetic programs where the scalars all have a bounded modulus. This paper was one of a number of papers that Jacques wrote concerning restricted models of computation. My goal today is to continue this tradition and consider the limitations of ?natural? classes of algorithms with regard to search and optimization problems.  <p>Many algorithm design and analysis courses and texts often organize the material in terms of well known ?algorithmic paradigms?,such as greedy algorithms,backtracking,dynamic programming,local search,primal-dual/local ratio,etc. We seem to be able to intuitively describe what we have in mind when we discuss these classes of algorithms but rarely (if ever) do we (or any of the standard texts) attempt to define precisely what we mean by greedy,dynamic programming,etc.</p>  <p>Based on work with co-authors,I would like to offer some precise definitions for a few of these paradigms; namely,greedy algorithms,(simple) dynamic programming,backtracking,and primal-dual/local ratio algorithms.</p>  <p>What is a good algorithmic model? The model should be able to capture most known algorithms (within the given paradigm),have some mathematical appeal,be amenable to analysis,and (at least eventually) lead to new insights and algorithms. I will leave it to the audience's judgment if we have any chance of being successful in this regard. </p>,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.  <p>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.</p>  <p>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.</p>  <p>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.</p>

Disciplines : ,
Mots-clés : fuscia,conférence,STIC,mathématiques appliquées,transformée de Fourier,algorithme glouton,paradigme de programmation,backtracking,optimisation,ordonnancement,théorie de la complexité
Type de document : image en mouvement
Type de ressource : lecture
Niveau : higher education,doctorat
Publics visés : learner,teacher
Activité induite : s'informer,apprendre
Proposition d'utilisation : Cycle de conférences mensuelles, les Colloquium Jacques Morgenstern peuvent être choisis par les étudiants de l'Ecole Doctorale STIC dans le cadre des heures de formation complémentaire. Les orateurs interviennent en français ou en anglais.
Auteurs ou éditeurs : Allan Borodin,Institut National de Recherche en Informatique et en Automatique,Université de Nice,Ecole Polytechnique Universitaire,Laboratoire I3S