Avant de commencer

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.

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 la moitié 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 le choix.

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 grand de deux nombres

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

L'étape 2 ne s'exécute pas toujours : cela dépend des valeurs. C'est un choix, la deuxième façon d'enchaîner.

Plusieurs fois : additionner une série de nombres

Additionner tous les nombres de 1 jusqu'à un nombre demandé.

1. Demander jusqu'où il faut aller.
2. Préparer un total, valant zéro au départ.
3. Pour chaque nombre de 1 jusqu'à celui qui a été demandé, 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 nombres. 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 demande allant jusqu'à 4 :

Et 1 + 2 + 3 + 4 font bien 10. Ce contrôle prend trente secondes et attrape la quasi-totalité des erreurs de raisonnement. Le chapitre suivant en fait une méthode, et la plateforme en fait une figure que l'on déroule d'un clic.

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.

Prenons une consigne banale : « calculer la moyenne des notes et dire si c'est reçu ». Elle paraît claire, et trois questions restent sans réponse.

• Combien de notes ? Trois, ou un nombre connu seulement au moment de l'exécution ?
• Reçu à partir de combien ? 10 inclus, ou strictement plus de 10 ? Le cas d'une note exactement à 10 doit être tranché.
• Et s'il n'y a aucune note ? 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.

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. Tourner les pages depuis le début, une par une. 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 tourne les pages : elle tient au raisonnement, et à lui seul.

Exercices type

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.

Exercice 1, Pair ou impair

Écrire un algorithme qui demande un nombre entier et affiche « pair » ou « impair ».

Indication : un nombre est pair lorsque le reste de sa division par 2 vaut zéro.

Exercice 2, Le plus grand de trois nombres

Demander trois nombres et afficher le plus grand.

Indication : commencer par supposer que le premier est le plus grand, puis se corriger.

Exercice 3, Compter les étapes

Reprendre l'algorithme qui additionne les nombres. Si l'on demande d'aller jusqu'à 5, combien de fois l'étape d'addition est-elle exécutée, et que vaut le total à la fin ?

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 notes » est une phrase, pas une étape : elle demande elle-même un algorithme.

Vérification

Et ensuite

Le français numéroté suffit pour trois ou quatre étapes. Il devient lourd dès que l'algorithme grandit, et il reste imprécis sur un point : où commence et où finit un choix ou une répétition.

Le chapitre suivant introduit une écriture faite pour cela, le pseudo-code : plus serrée que le français, plus lisible qu'un langage de programmation, et sans ambiguïté sur les débuts et les fins. Rien n'est à retenir d'avance.

La méthode

1. Écrire le problème en une phrase, avant toute notation. Si la phrase ne vient pas, le problème n'est pas encore compris.
2. Nommer ce qui entre et ce qui sort. Un algorithme part de données et produit un résultat : les deux se listent avant de réfléchir aux étapes.
3. Décomposer en étapes ordonnées, en français, chacune assez simple pour ne laisser aucun choix à celui qui l'exécute.
4. Vérifier sur un exemple concret, à la main, en suivant les étapes une par une sans anticiper.
5. Chercher le cas qui casse tout : la liste vide, le zéro, la valeur négative. C'est là que les étapes approximatives se révèlent.
6. Ne passer à la notation qu'ensuite. Un algorithme juste s'écrit dans n'importe quel langage ; un algorithme faux reste faux dans tous.

Synthèse

• Un algorithme est une suite d'étapes ordonnées, exécutables sans rien deviner, et qui s'arrête.
• Le critère : deux personnes qui la suivent obtiennent le même résultat.
• On y distingue toujours des entrées, un traitement et une sortie.
• Il n'existe que trois façons d'enchaîner des étapes : la séquence, le choix, la répétition.
• L'algorithme est le raisonnement, le langage une façon de l'écrire, le programme le résultat.
• Pour un même problème, plusieurs algorithmes justes existent, et ils ne coûtent pas la même chose.