Spécification d’un algorithme

De l’algorithme comme une fonction
mercredi 12 mai 2010
par  Jérôme Germoni

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

Logo de Olivier Cogis
lundi 6 juin 2016 à 23h34, par  Olivier Cogis

La lecture de nombre de manuels de mathématiques de niveau lycée nous a fait ressentir combien la contribution apportée ci-dessus par ce thème de discussion Spécification d’un algorithme est essentielle :

1) le calcul du pgcd de deux entiers peut se calculer de plusieurs façons, la méthode qui porte le nom d’algorithme d’Euclide se différencie des autres méthodes sans que la saisie des données ni la transmission du résultat aient quoi que ce soit à y voir ; dont acte ;

2) la question de la spécification des algorithmes est sans doute une façon de confronter au concept de fonction des élèves qui sont plus à l’aise lors d’une approche « concrète » (si on peut dire, mais peut y contribuer l’aspect boîte noire qu’on peut utiliser pour tester les données — y compris, par exemple, avec des entiers négatifs, ou nul, ou encore des décimaux) ; nous laissons naturellement aux enseignants de terrain le soin de donner in fine leur sentiment sur ce point.

Une remarque encore concernant notre choix du calcul du pgcd.

Si on ne connaît pas l’expression algébrique donnant directement la somme des n premiers entiers positifs en fonction de n, on peut toujours calculer cette somme au moyen d’un algorithme consistant à effectuer la somme de ces entiers. La méthode est sans subtilité, certes, mais elle demande néanmoins la mise en œuvre d’une répétitive, et autorise de se poser les questions de son contrôle et éventuellement de sa preuve.

En revanche, faire de l’unique instruction consistant à affecter une variable la valeur de l’expression n(n+1)/2 un exemple d’algorithme est quand même un cas limite. Pour éviter tout faux débat, disons qu’il s’agit bien d’un algorithme, mais, c’est un peu comme si on choisissait la fonction constante x ↦ 2 pour introduire le concept de fonction. Certes, c’en est une, mais ce n’est pas pour elle qu’on a dégagé le concept de fonction (il peut même paraître incongru aux yeux d’un élève qu’on appelle ça une fonction puisque le résultat n’est justement pas fonction de x, comme il peut paraître incongru qu’on appelle algorithme une simple affectation).

Encore une fois, bravo pour cet article fort réconfortant après la lecture un peu déprimante de manuels qui enseignent « l’algorithme du calcul du milieu d’un segment ».

Brèves

18 octobre 2015 - Questionnaires de la CII Université

L’objectif est de collecter de nouvelles réponses pour mieux mesurer l’impact de la réforme du (...)

27 janvier 2010 - Travailler par compétences et avec le socle commun

Conférence le 10 février au CRDP de Lyon de 9 h à 12 h, avec Jean Michel Zarkhartchouk

13 novembre 2008 - Probabilités en 3e

Texte issu d’une formation aux probabilités pour les professeurs de troisième faite par Y. Ducel (...)