Spécification d’un algorithme
par
Cet article est la suite d’une conversation avec Nicolas Saby, directeur de l’IREM de Montpellier, à propos d"une formation en algorithmique à laquelle il a participé récemment. Le travail mené à Montpellier avec les informaticiens a mis en évidence une possible différence de conception mathématiques/informatique à côté de laquelle nous sommes passés à Lyon qu’il me paraît utile de présenter.
La conception que « nous autres matheux » nous faisons d’un algorithme n’est sans doute pas la même qu’un informaticien. Voici un exemple simple qui illustre la différence.
Problème : calculer la somme des n premiers entiers, où n désigne un entier.
Mauvaise pratique
Demander la valeur de n,
Calculer n(n+1)/2,
Afficher le résultat,
Sortir du programme.
L’algorithme dans la version « de l’informaticien »
Algorithme : somme_entiers
Donnée : n entier
Résultat : la somme des n premiers entiers
Début
- Affecter n(n+1)/2 à s,
- Renvoyer s
Fin du programme
Les différences que j’essaie de souligner ici sont les suivantes :
dans la version dite « du matheux », les données sont entrées manuellement à l’exécution : il n’est donc pas possible d’utiliser ce programme sans intervention humaine ;
dans la version dite « du matheux », le résultat est affiché : il n’est donc plus disponible dès que le programme est terminé ; en particulier, on ne peut pas l’utiliser dans un autre programme.
Les informaticiens (de Montpellier en l’espèce) défendent l’idée qu’un algorithme est une fonction qui prend des données en argument, les manipule et renvoie un résultat. On peut éventuellement afficher ce résultat, ce n’est pas une obligation. Ce n’est parfois pas souhaitable, d’ailleurs, s’il est trop volumineux : imaginons une liste de 25000.
Intérêts du point de vue :
les algorithmes peuvent se composer, s’utiliser les uns dans les autres ; chaque algorithme est une brique élémentaire dans une construction complexe ;
la description dite « de l’informaticien » est plus conceptuelle et elle ne dépend pas d’un environnement informatique particulier ;
au demeurant, un programme récursif n’a en général pas d’autre choix que de renvoyer un résultat : l’afficher ne suffirait pas.
Bonnes pratiques
Pour décrire un algorithme, il faut écrire une spécification :
nom de l’algorithme,
description des données : quelles variables, (quels types de variables,)
description du résultat
Le corps de l’algorithme est présenté ensuite.
Remarquons qu’il y a peu de chose à modifier pour passer de la description initiale à ces bonnes pratiques.
Notons pour finir que ces bonnes pratiques sont faciles à mettre en place dans un environnement comme Xcas, mais impossibles (au moins pour l’instant) avec Algobox, qui interdit l’usage d’un programme dans un programme : en voulant simplifier la syntaxe, on a perdu un aspect essentiel de l’idée d’algorithme.
Commentaires