L’informatique existe en tant que discipline dans le tronc commun des CPGE scientifiques depuis 2013 et cela fait également plusieurs années que des éléments d’algorithmique ont été introduits dans les programmes de mathématiques de lycée. Je me réjouis qu’on fasse étudier quelques algorithmes aux lycéens (il était temps !), même si je préférerais que soient dédiés à cet enseignement des heures spécifiques et des professeurs spécialistes. Mais la présentation qui est faite des algorithmes n’est pas très heureuse : elle donne naissance à de mauvaises pratiques, est source de confusions dans le supérieur et doit être désapprise par les étudiants.

Voyons quels sont les problèmes et voyons comment on pourrait les éviter afin de parvenir à une présentation des algorithmes qui, tout en restant dans le cadre des programmes de lycée, puisse servir de base à une étude plus avancée dans l’enseignement supérieur. Pour cela, considérons l’extrait suivant du sujet de mathématiques de la session 2016 du baccalauréat.

Algorithmes et fonctions

Lorsqu’on écrit un algorithme, on souhaite pouvoir l’utiliser dans différents contextes : ainsi, un algorithme qui détermine le PGCD de deux entiers sera utilisé dans de nombreux autres programmes arithmétiques ; il est hors de question de le réécrire à chaque fois.

Inversement, une méthode essentielle pour écrire des algorithmes de façon efficace est de décomposer les problèmes : il est quasiment impossible de résoudre un problème complexe en affrontant immédiatement les petits détails, et quand on y arrive, c’est avec un programme illisible. On va plutôt discerner un certain nombre de grosses étapes, écrire un algorithme de haut niveau qui décrit comment ces étapes s’enchainent, puis écrire un algorithme pour chacune des étapes, successivement.

Cette méthode est en fait utilisée dans l’exemple : la question de savoir si une fraction est un entier a été laissée de côté. Un jour, il faudra écrire un algorithme auxiliaire qui répond à cette question, et il sera utilisé trois fois, avec des paramètres différents, dans l’algorithme principal ci-dessus.

La mathématicienne aura reconnu la méthode employée pour démontrer un théorème difficile : on discerne des lemmes, on démontre le théorème sous réserve des lemmes, puis on démontre chaque lemme indépendamment. Les langages de programmation expriment cette faculté de décomposition puis composition à l’aide de la notion de fonction, ce qui n’a rien de surprenant dans notre analogie mathématique pourvu qu’on veuille bien considérer qu’un théorème (ou un lemme) est une fonction qui à son hypothèse associe sa conclusion.

Il est donc important, même si la notion de fonction informatique n’est pas au programme du lycée, que l’introduction qui est faite ne soit pas incompatible avec cette notion.

Problème posé par l’affichage

Tous les langages de programmation comportent des procédures d’affichage (à l’écran ou sur une autre sortie). Mais il n’est pas usuel d’en parler lorsqu’on fait de l’algorithmique générale : l’affichage est une contingence matérielle qu’on peut ignorer tant qu’on n’implante pas les algorithmes en des programmes informatiques. Les seules occasions qu’on a de parler d’affichage en algorithmique se présentent lorsqu’on traite, précisément, des algorithmes qui permettent d’obtenir un affichage adéquat (centré, par exemple).

L’affichage n’est en effet pas un problème trivial en informatique : il faut communiquer avec un périphérique, etc. En application des principes évoqués plus haut, on voudra donc disposer d’une procédure générique d’affichage, et, dans tous les autres algorithmes, ne pas se soucier à nouveau de cette question.

Il faut donc, dans l’algorithme pris en exemple, ne pas pas parler d’affichage mais de valeur de retour. L’algorithme effectue un calcul puis renvoie le résultat ; dans certains contextes, on voudra afficher ce résultat, dans d’autres, on voudra s’en servir pour mener d’autres calculs. Avec la présentation qui est retenue, il est seulement possible d’afficher immédiatement le résultat. Remplaçons donc \(\text{Afficher}\) par \(\text{Renvoyer la valeur de}\).

Songez à l’inutilité d’un algorithme de PGCD qui afficherait son résultat au lieu de le renvoyer : chaque fois qu’on ferait appel à cet algorithme dans un autre, un affichage intempestif se produirait, et, pire, on ne pourrait pas écrire des choses comme \[d \text{ prend la valeur de } \mathit{pgcd}(a, b)\]

Modifié comme ci-dessus, notre algorithme peut être utilisé au sein d’un autre, à un détail près : comme il n’a pas de nom, on ne peut pas y faire référence. Comme l’énoncé demande d’analyser ce que fait cet algorithme, on ne lui donnera pas un nom qui donne trop de renseignements sur ce point (au contraire de ce qu’il faudrait faire en temps normal) : appelons-le \(\mathit{algoMystere}\).

On peut donc maintenant écrire, dans un autre algorithme, \[(x_0, y_0) \text{ prend la valeur de } \mathit{algoMystere}(M, N, P, Q)\]

Enfin presque.

Gestion de l’absence de solution

L’algorithme étudié ici n’est pas trivial, notamment parce qu’il vise à renvoyer quelque chose qui n’existe pas toujours : si \(N\) n’est pas un multiple de \(Q\), aucun couple ne convient. Ces fonctions sont difficiles à bien programmer, et pour tout dire je ne comprends pas très bien pourquoi on s’est échiné à traiter ce cas. Il aurait été bien plus simple d’imposer dans les hypothèses faites sur les paramètres que \(N\) soit un multiple de \(Q\), de la même façon qu’on a mis des contraintes sur les PGCD.

Avec cette restriction, la boucle trouve nécessairement une solution pour les paramètres valides : si une personne fait l’appel \(\mathit{algoMystere}(3, 4, 2, 3)\), l’exécution de la boucle se poursuivra indéfiniment, mais elle ne pourra s’en prendre qu’à elle-même car elle n’aura pas respecté les conditions requises sur les paramètres. Ceci est bien sûr analogue à l’utilisation frauduleuse d’un théorème dans un cas où ses hypothèses ne sont pas vérifiées.

Si toutefois on tient à ce que notre algorithme gère le cas où \(N\) n’est pas un multiple de \(Q\), il ne faut pas procéder comme dans le sujet du bac 2016. Remplacer, comme précédemment, \(\text{Afficher}\) par \(\text{Renvoyer la valeur de}\) ne suffit pas : si on procède ainsi, notre algorithme renverra tantôt un couple d’entiers (cas où une solution existe), tantôt le texte « Pas de solution ». Si on utilise cet algorithme dans un autre en effectuant \[(x_0, y_0) \text{ prend la valeur de } \mathit{algoMystere}(M, N, P, Q),\] il se produira une erreur car la valeur renvoyée par \(\mathit{algoMystere}\) n’est pas toujours un couple et ne peut donc être affectée à un couple. Une solution serait de faire \[v \text{ prend la valeur de } \mathit{algoMystere}(M, N, P, Q)\] puis de distinguer deux cas : \(v\) est un texte ; \(v\) est un couple. Rédiger correctement une telle distinction est très pénible et très lourd, et obscur : quelle sorte de valeur est donc \(v\) ? Personne ne rédigerait une démonstration mathématique en définissant \(x\) comme étant ou bien un réel ou bien un espace vectoriel.

La bonne façon de traiter cette situation exceptionnelle où la solution qu’on veut calculer est d’utiliser… une exception. Le mécanisme des exceptions en informatique n’est pas simple et on préférera légitimement ne pas en parler et écrire simplement
\[\text{Signaler l’}\unicode{0xe9}\text{chec de l’algorithme}\]

Et pour finir, l’entrée

Le problème traité précédemment pour la sortie par affichage se pose de façon symétrique pour l’entrée : en rédigeant comme proposé dans le sujet du bac, on empêche la composition des algorithmes. En effet, la procédure de lecture des paramètres va interrompre l’exécution du programme et obliger une saisie manuelle des valeurs pour lesquelles on souhaite utiliser l’algorithme. Il est impossible d’écrire un programme qui calcule des valeurs pertinentes pour \(M\) et les autres paramètres et applique automatiquement \(\mathit{algoMystere}\) à ces valeurs.

Encore une fois, le problème de la saisie des paramètres initiaux du problème (qui peut être plus compliqué que le seul calcul effectué par \(\mathit{algoMystere}\)) est indépendant de cet algorithme. Il vaut donc mieux se borner à dire que notre algorithme est décrit pour certains entiers \(M\), \(N\), \(P\) et \(Q\) dont la provenance est sans importance pourvu qu’ils respectent les conditions de PGCD et de divisibilité imposées.

La présentation du début de l’algorithme soulève un autre problème : elle ne fait aucune distinction entre \(M\), \(N\), \(P\) et \(Q\), qui sont des paramètres, et \(X\), qui est une variable temporaire interne à l’algorithme (c’est-à-dire une variable locale). Cette mention en tête de l’algorithme de la variable locale, probablement inspirée de ce qui se faisait en Pascal, n’est pas nécessaire dans la plupart des langages de programmation. En effet, un certain nombre de mots est prédéfini comme étant des mots-clés (if, while, etc., mais on pourrait aussi imaginer Si, TantQue), et tous les mots qui apparaissent dans un programme et qui ne sont pas dans cette liste sont automatiquement considérés comme des variables locales. Quant à l’intérêt de réfléchir dès le début aux variables locales dont on va avoir besoin, les avis divergent, mais j’incline à penser que cela n’est pas utile (d’ailleurs la mention faite ici au sujet de \(X\) ne donne aucune information sur le rôle de cette variable) et qu’il vaut mieux introduire les variables locales au moment où on en a besoin.

Dans tous les cas, il conviendrait de préciser que \(M\), \(N\), \(P\) et \(Q\) sont des paramètres (ou des entrées, si l’on y tient), et surtout supprimer l’étape de saisie des valeurs.

Que faire ?

Voici comment je propose de rédiger cet algorithme, dans le contexte de ce sujet du bac 2016.

\[\small\begin{array}{ll}\mathbf{Nom} & \text{algoMystere} \\\mathbf{Parametres} & M, N, P, Q \text{ : entiers relatifs non nuls}\\\mathbf{Precondition} & \mathit{pgcd}(M,N)=\mathit{pgcd}(P,Q)=1\text{ et } Q\text{ divise } N\\\mathbf{Variables\ locales}&X \text{ : entier naturel}\\\mathbf{Traitement} &\\& X \text{ prend la valeur } 0\\&\text{Tant que }\left(\frac MN\, X+\frac PQ \text{ n’est pas entier}\right)\text{ et } \left(-\frac MN\, X+\frac PQ \text{ n’est pas entier}\right)\text{ faire}\\&\qquad X\text{ prend la valeur } X+1\\&\text{Fin tant que}\\&\text{Si } \frac MN\, X+\frac PQ \text{ est entier alors}\\&\qquad \text{Renvoyer la valeur de} \left(X, \frac MN\, X+\frac PQ\right)\\&\text{Sinon}\\&\qquad\text{Renvoyer la valeur de} \left(-X, -\frac MN\, X+\frac PQ\right)\\&\text{Fin si}\end{array}\]

Si l’on tient à ce que l’algorithme traite le cas où la droite n’a pas de point de coordonnées entières, on peut l’écrire comme suit.

\[\small\begin{array}{ll}\mathbf{Nom} & \text{algoMystere} \\\mathbf{Parametres} & M, N, P, Q \text{ : entiers relatifs non nuls}\\\mathbf{Precondition} & \mathit{pgcd}(M,N)=\mathit{pgcd}(P,Q)=1\\\mathbf{Variables\ locales}&X \text{ : entier naturel}\\\mathbf{Traitement} &\\& \text{Si } Q \text{ divise } N \text{ alors}\\&\qquad X \text{ prend la valeur } 0\\&\qquad\text{Tant que }\left(\frac MN\, X+\frac PQ \text{ n’est pas entier}\right)\text{ et } \left(-\frac MN\, X+\frac PQ \text{ n’est pas entier}\right)\text{ faire}\\&\qquad\qquad X\text{ prend la valeur } X+1\\&\qquad\text{Fin tant que}\\&\qquad\text{Si } \frac MN\, X+\frac PQ \text{ est entier alors}\\&\qquad\qquad \text{Renvoyer la valeur de} \left(X, \frac MN\, X+\frac PQ\right)\\&\qquad\text{Sinon}\\&\qquad\qquad\text{Renvoyer la valeur de} \left(-X, -\frac MN\, X+\frac PQ\right)\\&\qquad\text{Fin si}\\&\text{Sinon}\\&\qquad\text{Signaler l’}\unicode{0xe9}\text{chec de l’algorithme}\\&\text{Fin si}\end{array}\]

On constate que c’est très peu différent de la présentation initiale, mais cette fois ci, aucune confusion n’est créée qui soit préjudiciable à l’apprentissage ultérieur d’une algorithmique plus avancée.

D’ailleurs, cet algorithme se traduit presque immédiatement en un programme Python, le langage en usage dans les CPGE ainsi que dans un nombre croissant de L1 de sciences. Le seul point délicat est la détermination du caractère entier des fractions : on ne peut pas calculer la valeur « dans \(\mathbb R\) » puis regarder si c’est entier parce qu’informatiquement, ce qui tient lieu de réels (les flottants) ne sont jamais des entiers. Une façon correcte de procéder est de réduire la fraction au même dénominateur et de regarder le reste du numérateur divisé par le dénominateur à l’aide de l’opérateur % de Python. Cet opérateur permet ainsi de tester la divisibilité. L’opérateur // réalise quant à lui la division euclidienne.

def algoMystere(M, N, P, Q) :
    """Paramètres : M, N, P, Q entiers relatifs non nuls
    Précondition : pgcd(M, N) = pgcd(P, Q) = 1"""
    if N % Q == 0 :
        X = 0
        while (M*X*Q+P*N) % (Q*N) != 0 and (-M*X*Q+P*N) % (Q*N) != 0 :
            X = X + 1
        if (M*X*Q+P*N) % (Q*N) == 0 :
            return (X, (M*X*Q+P*N) // (Q*N))
        else :
            return (-X, -(M*X*Q+P*N) // (Q*N))
    else :
        raise ValueError("Pas de solution")