Qu'est-ce qu'un algorithme

Expliquer à quelqu'un comment faire

Voici une consigne que tout le monde comprend : « faire un thé ».

Un être humain s'en sort. Il sait qu'il faut de l'eau, qu'elle doit chauffer, qu'un sachet s'infuse quelques minutes. Rien de tout cela n'est écrit dans la consigne : il le complète tout seul.

Maintenant, la même consigne pour quelqu'un qui ne complète rien, qui exécute exactement ce qui est écrit et rien de plus.

1. Faire chauffer de l'eau.
2. Mettre le sachet dans la tasse.
3. Verser l'eau.
4. Attendre.
5. Retirer le sachet.

C'est mieux, et ce n'est toujours pas suffisant. Combien d'eau ? Chauffer jusqu'à quelle température, ou pendant combien de temps ? Attendre combien de minutes ? Chacune de ces questions sans réponse est un endroit où l'exécutant devra deviner, et deux personnes obtiendront deux thés différents.

Le critère, et il n'y en a qu'un. Une suite d'étapes est utilisable lorsque deux personnes qui la suivent obtiennent le même résultat, sans se concerter et sans rien ajouter de leur cru.
Tant que ce n'est pas le cas, il reste une étape à préciser. Chercher où, c'est déjà faire de l'algorithmique.

Ce qu'est un algorithme

Un algorithme est une suite d'étapes qui décrit comment obtenir un résultat, à trois conditions.

• Les étapes sont dans un ordre défini.
• Chaque étape est exécutable sans rien deviner.
• L'ensemble s'arrête au bout d'un nombre limité d'étapes.

La troisième condition paraît évidente et ne l'est pas : « remuer jusqu'à ce que ce soit bon » ne s'arrête pas nécessairement, faute de dire ce qu'est « bon ».

On distingue toujours trois parties dans un algorithme.

Repérer ces trois parties avant d'écrire quoi que ce soit évite bien des difficultés. Un algorithme dont on ne sait pas dire ce qui entre et ce qui sort n'est pas encore prêt à être écrit.

Trois exemples, et les trois seules façons d'enchaîner

À ce stade, un algorithme s'écrit en français, numéroté. C'est déjà un algorithme, à condition qu'aucune étape ne laisse de place à l'interprétation.

Les trois exemples qui suivent introduisent, l'un après l'autre, les trois seules façons d'enchaîner des étapes. Il n'y en a pas de quatrième, et tout ce qui sera écrit par la suite se ramènera à ces trois-là.

Les unes après les autres : le prix à payer

Un article coûte 200 euros. Il bénéficie d'une remise de 10 %, et la taxe de 20 % s'ajoute ensuite.

1. Demander le prix de l'article.
2. Retirer la remise de 10 %.
3. Ajouter la taxe de 20 %.
4. Afficher le prix à payer.

Quatre étapes, exécutées dans l'ordre, chacune une seule fois. C'est une séquence, la première façon d'enchaîner.

Selon le cas : le plus élevé de deux relevés

Deux capteurs relèvent la température d'un même local, et seule la plus élevée intéresse.

1. Demander les deux relevés, les appeler a et b.
2. Si a est supérieur ou égal à b, alors le relevé le plus élevé est a.
3. Sinon, le relevé le plus élevé est b.
4. Afficher le relevé le plus élevé.

L'étape 2 pose une question, et sa réponse décide de la suite : une seule des deux conclusions s'applique, celle de l'étape 2 ou celle de l'étape 3. C'est un choix, la deuxième façon d'enchaîner. Ce choix n'est pas laissé à l'exécutant : ce sont les valeurs de a et b qui le tranchent.

Plusieurs fois : additionner les consommations d'une période

Un compteur électrique est relevé chaque jour, et il faut la consommation totale de la période.

1. Demander combien de jours compte la période.
2. Préparer un total, valant zéro au départ.
3. Pour chaque jour de la période, demander la consommation relevée et l'ajouter au total.
4. Afficher le total.

L'étape 3 ne s'exécute pas une fois, mais autant de fois qu'il y a de jours. C'est une répétition, la troisième et dernière façon d'enchaîner.

Ce que devient le total, tour après tour

Le meilleur moyen de s'assurer d'une répétition est de la dérouler à la main, sans en sauter un seul tour. Pour une période de quatre jours, dont les relevés sont 12, 9, 15 et 11 kilowattheures :

Et 12 + 9 + 15 + 11 font bien 47. Ce contrôle prend trente secondes et attrape une bonne part des erreurs de raisonnement, pourvu que ce cas ne soit pas le seul essayé. Le chapitre suivant en fait une méthode, et la plateforme en fait une figure que l'on déroule d'un clic.

Trois façons d'enchaîner, et pas une de plus.

La séquence : les étapes à la file.
Le choix : une étape qui ne s'exécute que dans certains cas.
La répétition : une étape qui s'exécute plusieurs fois.
Un algorithme de trois lignes et un logiciel de trois millions sont faits de ces trois-là, emboîtées les unes dans les autres.

Algorithme, programme, langage

Trois mots reviennent constamment et désignent trois choses différentes.

• Un algorithme est un raisonnement : la suite d'étapes, indépendamment de la façon de l'écrire. Les trois exemples ci-dessus en sont.
• Un langage de programmation est une façon d'écrire ce raisonnement pour qu'une machine puisse l'exécuter. Python, C et JavaScript en sont.
• Un programme est le résultat : le même raisonnement, écrit dans un de ces langages.

Un même algorithme donne donc plusieurs programmes, selon le langage choisi. C'est la raison pour laquelle on l'écrit d'abord seul : le raisonnement, une fois juste, se traduit ensuite dans le langage que l'on veut.

Pourquoi ne pas écrire le programme tout de suite

Maintenant que les trois mots sont distingués, la question se pose vraiment.

Voici une consigne banale : « calculer la moyenne des mesures d'un lot et dire s'il est conforme ». Elle paraît claire, et trois questions restent sans réponse.

• Combien de mesures ? Cinq, ou un nombre connu seulement au moment de l'exécution ?
• Conforme à quelle condition ? La moyenne doit-elle atteindre un seuil, ou le dépasser strictement ? Le cas d'une moyenne exactement égale au seuil doit être tranché.
• Et s'il n'y a aucune mesure ? Diviser par zéro n'a pas de résultat.

Ce sont exactement les endroits où l'exécutant devrait deviner, comme pour le thé. Les régler prend deux minutes sur une feuille. Les découvrir une fois le programme écrit coûte bien davantage, parce qu'il faut d'abord comprendre pourquoi le programme fait ce qu'il fait.

Un algorithme faux ne devient pas juste une fois tapé. La machine exécute fidèlement le raisonnement qu'on lui donne, y compris quand il est mauvais. Elle ne corrige rien et ne signale rien.

Deux méthodes pour le même problème

Un dernier point, qui donne sa raison d'être à tout le parcours : pour un même problème, plusieurs algorithmes justes existent, et ils ne se valent pas.

Chercher un mot dans un dictionnaire papier de soixante mille mots.

Première méthode. Lire les mots depuis le début, un par un, jusqu'à tomber sur le bon. Elle marche à tous les coups, et demande au pire soixante mille comparaisons.

Seconde méthode. Ouvrir au milieu, regarder si le mot cherché vient avant ou après, et écarter d'un coup la moitié qui ne peut pas le contenir. Recommencer sur celle qui reste. C'est ce que tout le monde fait sans y penser.

Les deux méthodes donnent la même réponse. La différence ne tient ni à la machine, ni au langage, ni à la vitesse de celui qui cherche : elle tient au raisonnement, et à lui seul.

Les pièges du début

• Les consignes qui se complètent toutes seules. « Faire comme d'habitude » ne s'exécute pas : il faut écrire ce qu'est l'habitude.
• Les cas oubliés. Le zéro, le nombre négatif, l'égalité, l'absence de donnée. Ce sont eux qui font échouer un algorithme par ailleurs juste.
• Les étapes qui en cachent plusieurs. « Trier les relevés » est une phrase, pas une étape : elle demande elle-même un algorithme.

Mettre en pratique

Les exemples du chapitre, sur d'autres nombres : un ordre qui change le prix, un total qu'on déroule, des essais qu'on compte.

Chercher avant de regarder la solution : c'est en cherchant qu'on apprend. Les réponses s'écrivent en français numéroté, comme les exemples du chapitre. Aucune notation particulière n'est attendue ici.