Algorithme
Un algorithme est une suite d’instructions dont l’exécution permet d’apporter à coup sûr une réponse à un problème particulier. Cet algorithme est applicable à la résolution de tous les problèmes partageant la même particularité.
À titre d’exemple, les maîtres des écoles apprennent à leurs élèves de CM1 comment résoudre une multiplication de deux grands nombres en leur enseignant une méthode pas-à-pas éprouvée. Sans le savoir, ces écoliers mettent en pratique un algorithme arithmétique. Il apprendront progressivement, grâce à ce même algorithme, à faire des retenues et à gérer la virgule décimale. Quelques années plus tard, certains d’entre eux l’appliqueront aussi pour réaliser des multiplications dans un système de numération autre que le système décimal.
Étymologie :
Le mot est dérivé du nom d’Al Khwârizmî (en arabe : الخوارزمي), un mathématicien Perse du 9e siècle.
Jusqu’aux années 1940, le mot était réservé aux méthodes de résolution de problèmes arithmétiques.
Les travaux conjoints du Britannique Alan Turing et de l’américain Alonzo Church pour définir un calculateur universel (la « Machine-U » ou « Machine de Turing ») identifient la table organisée des actions qui mènent à un résultat attendu comme étant un des éléments clés de leur modélisation. Ils la désignent d’abord « méthode effective de calcul », mais les Cybernéticiens adopteront plutôt le terme d’algorithme pour désigner la méthode de résolution d’un calcul que réalise un Programme.
Application à l’Informatique :
Turing et Church ont précisé[1] les 4 caractéristiques que tout algorithme proposé à la Machine-U se doit de remplir. Le texte qui suit simplifie et adapte les bonnes pratiques initiales retenues par ces auteurs:
- Le nombre d’étapes amenant à la solution doit être fini: le protocole à suivre pour parvenir à la solution doit toujours aboutir, quelle que soit sa durée d’exécution.
- Chaque étape ou règle doit être clairement définie et non ambiguë.
- Un algorithme doit être général pour pouvoir résoudre non pas seulement un problème particulier, mais aussi des problèmes apparentés. Pour illustration, un algorithme chargé de trier une liste alphabétique doit pouvoir trier n’importe quelle liste en entrée (par exemple quelle que soit la taille de la liste, avec des mots comprenant des caractères spéciaux, etc.), voire exécuter des tris ascendants ou descendants, quand cette caractéristique fonctionnelle est précisée par le cahier des charges.
- Le processus aboutissant à la solution doit être optimisé. Pour exemple, il doit comprendre le moins d’étapes que possible (formulation initiale de Turing) ainsi que contenir ses exigences en termes de ressources techniques nécessaires à son exécution, et réduire autant que possible le temps d’exécution.
Encore aujourd’hui, dans sa pratique en entreprise, un programmeur s’attache implicitement à tenir ces quatre exigences, dans le respect des contraintes de délai et de coût fixées par le cahier des charges qui lui est soumis.
Notes :
- Au-delà de son appropriation par l’informatique, la référence au terme algorithme s’étend à tous les domaines où il désigne une méthode structurée et détaillée pour résoudre un problème particulier : un manuel de montage d’un meuble livré en kit, une recette élaborée de pâtisserie ou une méthode pour résoudre les grilles de sudokus diaboliques, tous peuvent s’assimiler à un algorithme.
- Selon le contexte, le terme d’Algorithmique prend deux sens :
– la science des règles et des bonnes pratiques qui régissent la conception des algorithmes ;
– l’activité structurée de celui qui, par un algorithme, modélise le Processus systématique de résolution du problème étudié. - Dans le processus de développement d’un Programme Informatique, la conception de l’algorithme est l’étape conceptuelle importante qui précède et guide l’écriture même de ce programme dans un Langage de programmation interprétable par l’Ordinateur.
Retenons ici cette définition de Gérard Berry [2] qui fait de l’algorithmique un exercice abstrait de pensée avant celui plus concret de la programmation :
«Il faut comprendre la différence entre penser et calculer. Penser est la noblesse de l’esprit et reste difficilement explicable. Calculer est bien plus simple et systématique, et pour tout dire mécanisable. Il s’agit de résoudre un problème précis en suivant une mode d’emploi précis en vue d’une application données, par exemple pour trier une liste d’objets, multiplier deux nombres ou extraire une racine carrée. L’algorithmique est la science de l’organisation des opérations à effectuer. Elle travaille sur des opérations abstraites, comme additionner deux nombres. Pour passer aux opérations concrètes, il faut écrire tout de façon bien plus précise, sous la forme d’un programme écrit dans un langage de programmation. Le but final de l’informatique est d’évacuer la pensée du calcul, afin de le rendre exécutable par un ordinateur, qui est une machine fabuleusement rapide et exacte, mais fabuleusement dénuée de pensée».
_____________________
Notes et commentaires en références dans le texte :
[1] Dans la thèse de Church-Turing, cité dans le livre « Turing », Collection Génies des Mathématiques, mai 2018.↩
[2] Citation de Gérard Berry extraite de sa leçon inaugurale de la Chaire d’Innovation technologique Liliane Bettencourt, « Pourquoi le monde devient numérique », présentée au Collège de France le 17 janvier 2008.↩