Éducation Nationale Française · Seconde
Algorithmique : décrire et tracer
I
Ce qu'est un algorithme
On suit des algorithmes depuis des années sans les nommer. La division posée en est un : celui qui l'applique obtient le même quotient, sans rien décider. Une recette, un itinéraire, la règle du jour de la semaine sont de la même famille. Ce qu'ils ont en commun est une liste finie d'étapes, chacune assez claire pour qu'aucun jugement ne soit nécessaire, qui transforme ce qui est donné au départ en ce qui est voulu à la fin. Cet objet est l'algorithme lui-même. Il existe avant toute machine, et la machine n'est pas nécessaire pour l'étudier : un algorithme se décrit, s'exécute à la main, se vérifie, et s'écrit ensuite seulement comme programme.
Définition — Algorithme
Un algorithme est une suite finie d'instructions, chacune non ambiguë, qui transforme ce qui est donné au départ en ce qui est voulu à la fin. Non ambiguë signifie que deux personnes qui appliquent l'instruction font la même chose. Finie signifie que la suite se termine, et se termine pour toute entrée que l'algorithme accepte : après un nombre d'étapes connu ou non à l'avance, il ne reste plus rien à faire. Définition — Entrées et sortie
Les entrées sont les valeurs que l'algorithme reçoit au départ : il fonctionne pour toutes, pas pour une seule. La sortie est ce qu'il produit à la fin, affiché ou rendu. Les entrées parcourent un domaine que l'énoncé fixe : des entiers, des nombres positifs, un texte. Nommer les entrées, leur domaine et la sortie est la première chose à faire, avant toute étape ; un algorithme peut n'avoir aucune entrée, comme celui qui affiche toujours la même chose, mais cela se dit aussi. Méthode — Décrire un algorithme
- Nommer les entrées : que reçoit l'algorithme ? Donner un nom à chacune.
- Nommer la sortie : qu'est-ce qui est voulu à la fin, et sous quelle forme, affichée ou rendue ?
- Écrire les étapes dans l'ordre, une instruction par ligne, chacune applicable sans rien décider.
- Vérifier qu'il se termine : compter les étapes, ou dire ce qui fait venir la dernière.
Exemple
Appliquer les quatre étapes à ce but : afficher le prix d'un billet, qui vaut \(5\) euros pour un enfant de moins de douze ans et \(8\) euros sinon.
Entrées : un nombre, l'âge, entier et supérieur ou égal à \(0\). Sortie : le prix, affiché. Étapes :
- Lire l'âge, l'appeler
a. - Si
aest inférieur à12, appeler le prix5; sinon l'appeler8. - Afficher le prix.
a < 12 et recevrait le prix de \(5\) euros — ce qui n'a aucun sens ; c'est pourquoi l'énoncé l'exclut du domaine. Et la frontière est dite en toutes lettres, moins de douze, pour qu'un enfant de douze ans exactement paie \(8\) euros ; l'omettre ferait écrire deux algorithmes différents à deux lecteurs, ce qui est l'ambiguïté dont parle l'exemple suivant. Exemple
Laquelle des deux instructions ci-dessous peut figurer dans un algorithme ? - Saler à son goût.
- Ajouter \(5\) grammes de sel.
La seconde. À son goût demande au cuisinier de décider, et deux cuisiniers décident différemment : l'instruction est ambiguë, donc la recette n'est pas un algorithme telle quelle. \(5\) grammes ne laisse rien à décider. Une recette n'est pas disqualifiée parce que c'est une recette, mais à cause des instructions qu'elle laisse ouvertes ; remplacer chacune par une instruction mesurable en fait un algorithme.
Définition — Les trois registres
Le même algorithme s'écrit de trois façons. En langue naturelle, en phrases numérotées : la forme dans laquelle il s'invente et s'explique. En pseudo-code, une écriture fixée et brève dont l'affectation est une flèche : la forme dans laquelle il s'étudie, indépendante de tout langage. En Python, la forme dans laquelle il s'exécute et se teste. Passer de l'une à l'autre ne change rien à l'algorithme, seulement à son écriture. Le pseudo-code s'écrit dans la langue du lecteur, mots-clés compris ; les textes qu'un algorithme affiche restent en anglais dans les deux registres, comme toute ligne Python, pour qu'une trace et un programme s'accordent lettre pour lettre. Exemple
Voici un même algorithme dans les trois registres. Il reçoit les deux longueurs des côtés d'un rectangle et affiche son périmètre. Langue naturelle. - Lire la longueur, l'appeler
length, et la largeur, l'appelerwidth. - Calculer \(2\) fois la somme des deux, appeler le résultat
p. - Afficher
p.
Lire length
Lire width
p ← 2 × (length + width)
Afficher plength = int(input())
width = int(input())
p = 2 * (length + width)
print(p)
Les trois colonnes disent la même chose. La langue naturelle nomme les opérations, le pseudo-code les écrit en quatre lignes, le Python ajoute ce dont une machine a besoin et rien de plus :
input donne un texte, int en fait un nombre, et print affiche. Le seul signe dont le sens diffère est l'affectation : \(\leftarrow\) en pseudo-code, = en Python, et les deux veulent dire ranger dans, jamais est égal à. Méthode — Traduire d'un registre à l'autre
Chaque construction du pseudo-code a une écriture Python standard. Traduire, c'est remplacer ligne à ligne, en gardant l'ordre et l'indentation. | Pseudo-code | Python |
Lire n | n = int(input()) |
Afficher x | print(x) |
x \(\leftarrow\) 3 | x = 3 |
Si c alors …Sinon …Fin Si | if c: …else: … |
Sinon si c alors | elif c: |
a = b a \(\neq\) b | a == b a != b |
a \(\leqslant\) b a \(\geqslant\) b | a <= b a >= b |
et ou non | and or not |
a \(\times\) b a \(\div\) b | a * b a / b |
quotient de a par b | a // b |
reste de a par b | a \pourcent{} b |
Pour k allant de 1 à n …Fin Pour | for k in range(1, n + 1): … |
Tant que c …Fin Tant que | while c: … |
Fonction f(a) …Renvoyer r | def f(a): …return r |
Lire est écrit par Python avec deux fonctions à la fois, et suppose ici que la valeur lue est un entier. La boucle bornée n'écrit pas ses bornes de la même façon. Et les Fin Si, Fin Pour et Fin Tant que n'ont aucune écriture Python : ce qui dit à Python où s'arrête un bloc est l'indentation. Le signe = est le piège du tableau : en Python il affecte, là où le pseudo-code écrit \(\leftarrow\) ; et pour comparer, le pseudo-code écrit = là où Python écrit ==. Le signe \(\div\) est l'autre : c'est la division qui garde les décimales, et la division entière qui les laisse s'écrit quotient de a par b, jamais avec le même signe.
Un algorithme n'est pas un programme
Le programme est une écriture de l'algorithme, dans un langage, pour une machine. L'algorithme est ce qui survit à un changement de langage : la même suite d'étapes, écrite en Python, dans un autre langage ou sur le papier, reste le même algorithme. C'est pourquoi il peut s'étudier sans être exécuté, et pourquoi deux programmes d'aspect différent peuvent être le même algorithme.
Se terminer fait partie de la définition
Une suite d'instructions qui n'atteint jamais sa dernière étape n'est pas un algorithme, si claire que soit chacune de ses instructions. La question pourquoi se termine-t-il ? a donc une réponse pour tout algorithme, et elle sera posée à chaque boucle. Quand le nombre d'étapes est connu à l'avance, la réponse est un compte ; quand il ne l'est pas, la réponse dit ce qui rapproche la fin à chaque étape.
D'où vient le mot
Le mot vient du nom d'Al-Khwarizmi, mathématicien de Bagdad du neuvième siècle, dont le livre sur le calcul avec les dix chiffres fut traduit en latin sous le titre Algoritmi de numero indorum. Les objets sont plus anciens que le mot : l'algorithme qui calcule le plus grand diviseur commun de deux nombres est chez Euclide, il y a vingt-trois siècles, et c'est encore celui qu'on emploie aujourd'hui.
Compétences à pratiquer
- Prédire
- Décrire
- Les trois registres
II
Variables et choix
Un algorithme a besoin de retenir. Une variable est l'endroit où une valeur attend d'être utilisée ou remplacée, et la flèche est ce qui l'y met. Dès deux ou trois lignes de cette sorte, une question se pose qu'aucune lecture ne tranche d'un coup d'œil : que vaut la variable à la fin ? La réponse s'obtient en exécutant l'algorithme à la main, une ligne à la fois, en notant ce qui change. L'exécution à la main est la technique centrale, et son outil est le tableau d'états.
Définition — Variable et affectation
Une variable est un nom qui retient une valeur à la fois. L'affectation x \(\leftarrow\) e est l'instruction qui calcule la valeur de l'expression e avec les valeurs retenues à cet instant, puis range le résultat dans x, en remplaçant ce qui s'y trouvait. Rien d'autre ne change : les variables qui ne sont pas nommées à gauche gardent leur valeur. Python écrit cette instruction x = e. Définition — Le tableau d'états
Le tableau d'états est l'écriture d'une exécution à la main. Il porte une ligne par instruction exécutée, dans l'ordre où elles le sont, et une colonne par variable, plus une colonne pour ce qui est affiché. Quand le corps d'une boucle tient sur une seule instruction, une ligne par tour dit la même chose plus brièvement, et c'est la forme employée pour les boucles. Chaque ligne porte la valeur de toutes les variables après cette instruction, et pas seulement de celle qui a changé : une ligne est une photographie de toute la mémoire. Une variable qui ne retient encore rien laisse sa case vide. Méthode — Exécuter un algorithme à la main
- Tracer le tableau : une colonne par variable de l'algorithme, une colonne Affichage, et une première colonne pour l'instruction.
- Prendre les instructions une à une, dans l'ordre, jamais deux à la fois.
- Calculer d'abord le membre de droite, avec les valeurs de la ligne précédente, puis écrire la nouvelle ligne.
- Recopier les valeurs inchangées sur la nouvelle ligne, pour que chaque ligne puisse se lire seule.
- Lire la réponse dans la dernière ligne, ou dans la colonne Affichage si la question porte sur ce qui est montré.
Exemple
Exécuter à la main l'algorithme suivant et donner ce qu'il affiche. a ← 3
b ← a + 2
a ← b × 2
Afficher a| Instruction | \(a\) | \(b\) | Affichage |
| \(a \leftarrow 3\) | \(3\) | ||
| \(b \leftarrow a + 2\) | \(3\) | \(5\) | |
| \(a \leftarrow b \times 2\) | \(10\) | \(5\) | |
| Afficher \(a\) | \(10\) | \(5\) | \(10\) |
10. La troisième ligne est celle qu'il ne faut pas précipiter : le membre de droite \(b \times 2\) est calculé avec la valeur retenue alors par b, c'est-à-dire \(5\), et le résultat remplace le \(3\) que retenait a. Lire l'algorithme comme un système d'équations donnerait \(a = 3\) et \(a = 2b\) en même temps, ce qui est impossible ; le tableau montre que les deux lignes sont deux moments, non deux conditions. Exemple
L'algorithme ci-dessous est censé échanger les valeurs de x et y. L'exécuter à la main et dire s'il le fait. x ← 4
y ← 9
x ← y
y ← x
Afficher x
Afficher y| Instruction | \(x\) | \(y\) | Affichage |
| \(x \leftarrow 4\) | \(4\) | ||
| \(y \leftarrow 9\) | \(4\) | \(9\) | |
| \(x \leftarrow y\) | \(9\) | \(9\) | |
| \(y \leftarrow x\) | \(9\) | \(9\) | |
| Afficher \(x\) | \(9\) | \(9\) | \(9\) |
| Afficher \(y\) | \(9\) | \(9\) | \(9\) |
y. L'échange demande une troisième variable pour garder la valeur sur le point d'être écrasée : \(t \leftarrow x\), puis \(x \leftarrow y\), puis \(y \leftarrow t\). Le tableau est ce qui rend la perte visible, à la ligne exacte où elle se produit.
Une affectation n'est pas une égalité
En mathématiques, \(x = x + 1\) n'a pas de solution. Comme instruction,
x \(\leftarrow\) x + 1 se lit de droite à gauche et n'a rien d'étrange : prendre la valeur retenue par x, ajouter un, ranger le résultat dans x. La flèche dit le sens, et c'est pourquoi le pseudo-code l'emploie. Python écrit = et garde == pour la question ces deux-là sont-ils égaux ?, différence sur laquelle l'algorithmique et la programmation insistent l'une et l'autre.
Définition — L'instruction conditionnelle
L'instruction conditionnelle choisit entre deux suites d'instructions selon une condition. Écrite Si c alors …Sinon …Fin Si, elle évalue la condition c, qui est vraie ou fausse, puis exécute les instructions d'une seule branche. La partie Sinon peut être absente : rien n'est alors fait quand la condition est fausse. Plusieurs conditionnelles peuvent se suivre, ou s'emboîter l'une dans l'autre, pour traiter plus de deux cas. Définition — Conditions composées
Une condition se construit à partir de comparaisons, a = b, a < b, a \(\leqslant\) b et leurs semblables, jointes par et, ou, et niées par non. Une condition c et d est vraie quand les deux le sont ; c ou d est vraie dès que l'une l'est ; non c est vraie exactement quand c est fausse. La négation de a < b est a \(\geqslant\) b, et non a > b : oublier le cas d'égalité est l'erreur la plus fréquente sur les conditions. Exemple
Exécuter à la main l'algorithme ci-dessous pour a égal à \(10\), en montrant comment la condition composée est évaluée. Si a ≥ 0 et a ≤ 10 alors
Afficher "in range"
Sinon
Afficher "out of range"
Fin Si| Instruction | \(a\) | \(a \geqslant 0\) | \(a \leqslant 10\) | et | Affichage |
| départ | \(10\) | ||||
| Si | \(10\) | vrai | vrai | vrai | |
| Afficher | \(10\) | in range |
in range. Une condition composée s'évalue une comparaison à la fois, et les colonnes le montrent : chaque moitié reçoit sa réponse à part, puis et répond vrai parce que les deux le sont. La valeur \(10\) est une limite du problème, et elle est acceptée parce que les deux signes sont larges ; avec a < 10 le même algorithme la refuserait. Pour \(11\) la première moitié serait encore vraie et la seconde fausse, donc et serait faux et l'autre branche s'exécuterait : une moitié fausse suffit à rendre un et faux, là où une moitié vraie suffirait à rendre un ou vrai. Méthode — Exécuter une conditionnelle à la main
- Ajouter une colonne condition au tableau d'états, portant vrai ou faux pour la ligne où la condition est évaluée.
- Évaluer la condition avec les valeurs de la ligne précédente, et écrire le résultat : c'est une réponse, non un calcul à refaire plus tard.
- Ne suivre qu'une branche, et écrire ses instructions comme des lignes ; les instructions de l'autre branche ne produisent aucune ligne.
- Continuer après le
Fin Si, quelle que soit la branche prise.
Exemple
L'algorithme ci-dessous reçoit deux nombres, a et b, qui sont ses entrées, et affiche le plus grand. L'exécuter à la main pour a égal à \(7\) et b égal à \(12\). Si a > b alors
m ← a
Sinon
m ← b
Fin Si
Afficher m| Instruction | \(a\) | \(b\) | \(m\) | \(a > b\) | Affichage |
| départ | \(7\) | \(12\) | |||
| Si \(a > b\) | \(7\) | \(12\) | faux | ||
| \(m \leftarrow b\) | \(7\) | \(12\) | \(12\) | ||
| Afficher \(m\) | \(7\) | \(12\) | \(12\) | \(12\) |
12. La condition est fausse, donc la branche Sinon s'exécute et la branche alors ne produit aucune ligne : m \(\leftarrow\) a n'est jamais exécutée, et l'écrire dans le tableau serait une faute. Quand a et b sont égaux la condition est fausse aussi, et l'algorithme affiche b, ce qui est la bonne réponse puisque les deux sont le même nombre. Exemple
Un billet coûte \(5\) euros, ou \(4\) euros à partir de dix billets, ou \(3\) euros à partir de vingt. Qu'affiche le programme suivant ? n = 12
if n < 10:
price = 5
elif n < 20:
price = 4
else:
price = 3
print("Total:", price * n)Total: 48n >= 10 : il n'est atteint que si le premier était faux, donc cette partie est déjà connue. C'est l'enchaînement que le pseudo-code écrit comme une conditionnelle dans le Sinon de la précédente, et que Python écrit avec elif. L'ordre des cas est ce qui le fait fonctionner : placer le cas n < 20 en premier et toute commande de moins de dix billets serait facturée \(4\) euros au lieu de \(5\).
Une branche non prise ne laisse pas de trace
Dans un tableau d'états, seules les instructions réellement exécutées ont une ligne. La tentation est d'écrire les deux branches, puisque les deux figurent dans l'algorithme ; mais le tableau est l'histoire d'une exécution, non une copie du texte. Deux entrées différentes donnent deux tableaux différents pour un même algorithme, et les comparer est souvent ce qui explique un comportement.
Compétences à pratiquer
- Prédire
- Tracer une suite d'instructions
- Les choix
III
Répéter
Écrire vingt fois la même instruction donne un algorithme, mais un mauvais : il dit vingt là où la réponse voulue est autant qu'il le faut, et personne ne peut l'écrire quand le nombre de répétitions n'est pas connu avant de commencer. Répéter est donc une construction à part entière, et elle vient en deux sortes : celle qui sait d'avance combien de tours elle fera, et celle qui tourne tant que quelque chose reste vrai. La seconde pose une question que la première ne pose pas : qu'est-ce qui garantit qu'elle s'arrête ? Cette question est posée ici, et répondue en mots, bien avant toute démonstration.
Définition — La boucle bornée
La boucle bornée Pour k allant de a à b répète les instructions qu'elle contient, en donnant à k la valeur a, puis a + 1, et ainsi de suite jusqu'à b inclus. La variable k est le compteur : elle est gérée par la boucle elle-même, jamais affectée à l'intérieur. Le nombre de tours est connu avant de commencer, et vaut \(b - a + 1\) quand \(a \leqslant b\) ; quand \(a > b\) la boucle ne fait aucun tour. Définition — L'accumulateur
Un accumulateur est une variable créée avant la boucle et lue après elle, que les tours construisent peu à peu. Sa valeur de départ est la réponse pour zéro tour : 0 pour une somme, 1 pour un produit. Quand zéro tour n'a pas de réponse, comme pour le plus grand de plusieurs nombres (le plus grand d'aucun nombre n'est pas un nombre), l'accumulateur part de la première valeur lue, et la boucle traite celles qui restent. Oublier de le créer avant la boucle, ou le lire à l'intérieur de la boucle au lieu de l'après, sont les deux erreurs à éviter. Méthode — Exécuter une boucle à la main
- Écrire les lignes d'avant la boucle comme d'habitude : l'accumulateur y reçoit sa valeur de départ.
- Écrire une ligne par tour, repérée par la valeur du compteur, et non une ligne par instruction du corps quand celui-ci tient sur une ligne.
- Calculer avec les valeurs de la ligne précédente, tour après tour, sans jamais sauter en avant.
- Compter les tours et vérifier ce compte sur les bornes avant de lire la réponse.
- Écrire les lignes d'après la boucle : l'accumulateur y est lu, avec la valeur du dernier tour.
Exemple
Exécuter à la main l'algorithme suivant et donner ce qu'il affiche. s ← 0
Pour k allant de 1 à 4
s ← s + k
Fin Pour
Afficher s| Instruction | \(s\) | \(k\) | Affichage |
| \(s \leftarrow 0\) | \(0\) | ||
| tour \(k = 1\) | \(1\) | \(1\) | |
| tour \(k = 2\) | \(3\) | \(2\) | |
| tour \(k = 3\) | \(6\) | \(3\) | |
| tour \(k = 4\) | \(10\) | \(4\) | |
| Afficher \(s\) | \(10\) | \(4\) | \(10\) |
10, la somme \(1 + 2 + 3 + 4\). Quatre tours, comme l'annoncent les bornes \(1\) et \(4\). Après le tour \(k\), s retient la somme des entiers de \(1\) à \(k\) : la colonne \(s\) le dit à chaque ligne, et c'est pourquoi la valeur lue après la boucle est la somme des quatre. L'accumulateur part de 0 parce que c'est la somme d'aucun nombre, et il est lu après la boucle, quand les quatre tours sont faits. Le faire partir de \(1\) ajouterait un de trop ; le lire dans la boucle afficherait quatre nombres au lieu d'un. Exemple
Qu'affiche le programme suivant, et que calcule-t-il ? L'écrire aussi en pseudo-code. total = 0
for k in range(1, 6):
total = total + k * k
print(total)55total ← 0
Pour k allant de 1 à 5
total ← total + k × k
Fin Pour
Afficher totalrange(1, 6), dont la seconde borne est la première valeur non prise, là où le pseudo-code écrit la dernière valeur prise. Le même algorithme, deux écritures des mêmes bornes.
Les deux bornes ne s'écrivent pas de la même façon
Pour k allant de 1 à n prend la valeur n ; range(1, n) s'arrête juste avant. L'écriture Python de la même boucle est donc range(1, n + 1), et ce décalage est l'erreur la plus fréquente du passage d'un registre à l'autre. La vérification sûre est de compter les tours sur un petit cas : allant de 1 à 3 fait trois tours, et range(1, 4) donne 1, 2, 3, trois valeurs.
Définition — La boucle non bornée
La boucle non bornée Tant que c répète les instructions qu'elle contient aussi longtemps que la condition c est vraie. La condition est testée avant chaque tour, y compris le premier : si elle est fausse au départ, la boucle ne fait aucun tour. Le nombre de tours n'est pas connu à l'avance ; il dépend de ce que les instructions du corps font aux valeurs que regarde la condition. Définition — Pourquoi une boucle se termine
Une boucle bornée se termine parce que son nombre de tours est fixé avant qu'elle ne commence. Une boucle non bornée ne se termine que si quelque chose, dans son corps, finit par rendre la condition fausse. Pour justifier qu'elle s'arrête, nommer un nombre entier que le corps déplace strictement dans un sens à chaque tour, pendant que la condition le maintient d'un côté d'une borne tant que la boucle tourne : un nombre entier ne peut pas se déplacer indéfiniment d'au moins un du côté borné, donc la condition tombe après un certain nombre de tours. Une quantité qui se rapproche seulement d'une borne sans jamais l'atteindre ne prouve rien, et une décroissance qui manque la valeur que teste la condition non plus. Et une boucle dont le corps ne touche pas à ce que regarde la condition ne s'arrête jamais, une fois qu'elle a commencé à tourner. Méthode — Justifier qu'une boucle se termine
- Nommer la quantité que le corps modifie à chaque tour, parmi celles dont dépend la condition.
- Dire que c'est un nombre entier et dans quel sens il varie, strictement, à chaque tour : une telle quantité s'appelle un variant de la boucle.
- Dire quelle borne la condition l'empêche de franchir, tant que la boucle tourne.
- Conclure, et désigner la colonne du tableau d'états où cette quantité se lit, tour après tour.
Méthode — Exécuter une boucle non bornée à la main
- Ajouter une colonne condition au tableau d'états : sur une ligne de tour, elle porte le test qui a autorisé ce tour, évalué sur l'état de la ligne précédente.
- Écrire une ligne par tour comme pour une boucle bornée, une fois la condition trouvée vraie.
- Écrire une dernière ligne nommée fin, sans instruction, où la condition est fausse : cette ligne est ce qui termine la trace, et l'oublier revient à oublier pourquoi la boucle s'est arrêtée.
- Lire le nombre de tours comme le nombre de lignes nommées tour.
Exemple
L'algorithme ci-dessous cherche la première puissance de deux au-dessus de \(100\). L'exécuter à la main et donner ce qu'il affiche. p ← 1
n ← 0
Tant que p ≤ 100
p ← p × 2
n ← n + 1
Fin Tant que
Afficher n| Instruction | \(p\) | \(n\) | \(p \leqslant 100\) | Affichage |
| départ | \(1\) | \(0\) | ||
| tour 1 | \(2\) | \(1\) | vrai | |
| tour 2 | \(4\) | \(2\) | vrai | |
| tour 3 | \(8\) | \(3\) | vrai | |
| tour 4 | \(16\) | \(4\) | vrai | |
| tour 5 | \(32\) | \(5\) | vrai | |
| tour 6 | \(64\) | \(6\) | vrai | |
| tour 7 | \(128\) | \(7\) | vrai | |
| fin | \(128\) | \(7\) | faux | |
| Afficher \(n\) | \(128\) | \(7\) | \(7\) |
7, puisque \(2^7 = 128\) est la première puissance de deux au-dessus de \(100\). La boucle s'arrête pour la raison que la Méthode demande de nommer : le variant est le nombre entier p, qui se lit dans sa propre colonne ; il double au moins à chaque tour, donc il croît d'au moins un à chaque fois, et la condition le maintient à au plus \(100\) tant que la boucle tourne. Un nombre entier ne peut pas croître indéfiniment en dessous de \(100\), donc la condition tombe. La dernière ligne, fin, est là où elle tombe, et l'oublier revient à oublier pourquoi la boucle s'est arrêtée. Exemple
Deux textes diffèrent d'un signe. Lequel des deux est un algorithme ? n ← 7
Tant que n ≠ 0
n ← n - 2
Fin Tant quen ← 7
Tant que n > 0
n ← n - 2
Fin Tant que
Le second seulement. Le premier texte n'atteint jamais sa dernière étape, donc ce n'est pas un algorithme, si claire que soit chacune de ses instructions.
Dans les deux,
| Instruction | \(n\) | \(n \neq 0\) |
| départ | \(7\) | |
| tour 1 | \(5\) | vrai |
| tour 2 | \(3\) | vrai |
| tour 3 | \(1\) | vrai |
| tour 4 | \(-1\) | vrai |
| tour 5 | \(-3\) | vrai |
| … | … | vrai |
| Instruction | \(n\) | \(n > 0\) |
| départ | \(7\) | |
| tour 1 | \(5\) | vrai |
| tour 2 | \(3\) | vrai |
| tour 3 | \(1\) | vrai |
| tour 4 | \(-1\) | vrai |
| fin | \(-1\) | faux |
n décroît de deux à chaque tour : \(7\), \(5\), \(3\), \(1\), puis \(-1\). C'est là qu'elles se séparent — à droite la condition est désormais fausse et la trace a sa ligne fin, tandis qu'à gauche elle reste vraie et n continue : \(-3\), \(-5\), et ainsi de suite. Ce qui diffère est la borne dont la condition la tient du bon côté. À droite, n > 0 maintient n à au moins \(1\) tant que la boucle tourne, et un nombre entier ne peut pas décroître indéfiniment au-dessus de \(1\) : la trace a une ligne fin. À gauche, n \(\neq\) 0 ne borne n d'aucun côté, et la colonne reste vraie pour toujours : la décroissance ne tombe jamais sur la valeur que teste la condition, parce que n est partie d'un nombre impair et perd deux à chaque fois.
La condition dit quand continuer
Tant que p \(\leqslant\) 100 ne veut pas dire que la boucle s'arrête à \(100\) : cela veut dire qu'elle tourne aussi longtemps que p vaut au plus \(100\), et qu'elle s'arrête la première fois que c'est faux. La condition écrite est la condition pour continuer ; la condition d'arrêt en est la négation. La lire à l'envers est ce qui produit une trace avec un tour de trop ou de moins.
Ce que la boucle laisse derrière elle
Après la boucle, les variables gardent les valeurs du dernier tour, et celle qui a rendu la condition fausse garde la valeur qui l'a rendue fausse. Dans la recherche d'une puissance de deux,
p vaut \(128\) à la fin, et non \(64\) : l'algorithme affiche n, mais la valeur p a bien dépassé la borne. Savoir ce que vaut chaque variable après la boucle est ce qui permet de continuer un algorithme au lieu de le recommencer.
Compétences à pratiquer
- Prédire
- La boucle bornée
- La boucle non bornée
IV
Fonctions et vérification
Un algorithme qui vaut la peine d'être écrit vaut la peine d'être nommé, pour être employé dans un autre sans être recopié. C'est ce qu'est une fonction : un morceau d'algorithme à entrées nommées et à résultat unique. Et une fois un algorithme écrit, une question demeure : comment sait-on qu'il est juste ? L'essayer est la première réponse, et elle ne suffit pas ; reste à dire ce que vaut un essai bien choisi, et ce qu'il ne peut pas dire.
Définition — Fonction
Une fonction est un algorithme muni d'un nom et d'entrées nommées, appelées ses paramètres, qui se termine en rendant un résultat. Écrite Fonction f(a, b) …Renvoyer r …Fin Fonction, elle ne s'exécute pas d'elle-même : elle s'exécute quand elle est appelée, et chaque appel donne à ses paramètres les valeurs écrites dans l'appel, qui en sont les arguments. L'instruction Renvoyer termine la fonction aussitôt et remet la valeur à qui a appelé. Définition — Afficher et renvoyer
Afficher montre une valeur à qui regarde ; renvoyer la remet à l'algorithme qui l'a demandée. Une fonction qui affiche son résultat et ne rend rien ne peut pas servir dans un calcul : il ne reste rien d'elle une fois l'écran lu. Une fonction qui rend et n'affiche rien ne montre rien, et c'est normal : c'est l'appelant qui décide de l'afficher. Dans le tableau d'états d'un appel, la valeur rendue s'écrit dans une colonne à part, Rendu, puisqu'elle n'est retenue par aucune variable. Méthode — Lire une fonction
- Lire l'en-tête : comment s'appellent les paramètres, et combien y en a-t-il ?
- Repérer chaque
Renvoyer: chacun est une sortie, et la valeur qu'il rend est le résultat de cette sortie. - Dire en une phrase ce que fait la fonction à partir de ses entrées, sans décrire ses lignes.
- Tracer un appel à la main, avec une valeur pour chaque paramètre, pour vérifier cette phrase.
Exemple
La fonction ci-dessous est l'algorithme qui garde le plus grand de deux nombres, muni d'un nom. Que rend l'appel max_of_two(7, 12) ? Fonction max_of_two(a, b)
Si a > b alors
Renvoyer a
Sinon
Renvoyer b
Fin Si
Fin Fonction| Instruction | \(a\) | \(b\) | \(a > b\) | Rendu |
appel max_of_two(7, 12) | \(7\) | \(12\) | ||
| Si \(a > b\) | \(7\) | \(12\) | faux | |
| Renvoyer \(b\) | \(7\) | \(12\) | \(12\) |
12. La trace d'un appel commence par une ligne qui donne aux paramètres leurs valeurs, ce que fait l'appel, et elle se termine au Renvoyer atteint : rien de ce qui le suit n'est exécuté, ni dans cette branche ni dans une autre. Le nom de la fonction n'est pas une variable et ne figure dans aucune colonne ; l'appelant est libre d'afficher la valeur, de la ranger dans une variable, ou de s'en servir dans un calcul. Exemple
Qu'affiche le programme suivant ? def max_of_two(a, b):
if a > b:
return a
else:
return b
print(max_of_two(7, 12))
print(max_of_two(max_of_two(3, 8), 5))12
8def pour l'en-tête et return pour la sortie. Le second appel montre à quoi sert le fait de rendre : la valeur 8 qui sort de l'appel intérieur devient le premier paramètre de l'appel extérieur, sans jamais être affichée ni rangée. Une fonction qui aurait affiché son résultat au lieu de le rendre ne pourrait pas être emboîtée dans un autre appel. Définition — Jeu d'essai
Un jeu d'essai est un choix de valeurs pour les entrées, accompagné du résultat attendu avant toute exécution. Vérifier un algorithme sur un jeu d'essai, c'est l'exécuter à la main sur ces valeurs et comparer ce qui sort à ce qui était attendu. Le résultat attendu doit être établi ailleurs que par l'algorithme lui-même, sinon la vérification ne dit rien. Définition — Cas limite
Un cas limite est un jeu d'essai choisi à une frontière du problème : zéro, une seule valeur, aucune valeur à traiter, deux valeurs égales, une valeur négative, la plus petite et la plus grande autorisées. Les cas ordinaires montrent que l'algorithme fonctionne quand rien n'est particulier ; les cas limites sont là où une faute se cache le plus souvent, et on les choisit pour cette raison, on ne les rencontre pas par hasard. Quelles valeurs sont des limites dépend du domaine que fixe l'énoncé. Méthode — Vérifier un algorithme
- Écrire d'abord le résultat attendu, pour chaque jeu d'essai, avant toute exécution ; dans le tableau, une colonne Attendu le porte à côté de la valeur que produit l'algorithme.
- Prendre un cas ordinaire et l'exécuter à la main sur ce cas.
- Prendre les cas limites : que se passe-t-il pour zéro, pour une seule valeur, pour des valeurs égales, pour une valeur négative ?
- Comparer, ligne à ligne, ce que donne le tableau et ce qui était attendu, et s'arrêter à la première ligne où ils diffèrent.
- Conclure prudemment : un cas qui échoue prouve que l'algorithme est faux ; des cas qui passent ne prouvent rien sur ceux qui n'ont pas été essayés.
Exemple
L'algorithme ci-dessous est censé afficher le plus grand de quatre nombres lus l'un après l'autre. Il a été essayé sur \(3\), \(9\), \(4\), \(1\) et a affiché \(9\), ce qui est juste. Donner un jeu d'essai sur lequel il est faux. m ← 0
Pour k allant de 1 à 4
Lire x
Si x > m alors
m ← x
Fin Si
Fin Pour
Afficher m
Quatre nombres négatifs, par exemple \(-3\), \(-9\), \(-4\), \(-1\). Le résultat attendu est \(-1\) ; l'algorithme affiche \(0\).
La valeur de départ \(0\) est la faute : elle n'est pas l'un des nombres lus, et elle l'emporte sur tous. La correction sûre est de faire partir l'accumulateur d'une valeur réellement présente parmi les nombres lus, c'est-à-dire du premier nombre lu ; la boucle compare ensuite les trois qui restent. Une valeur de départ inférieure à tous les nombres qu'autorise l'énoncé marcherait aussi, mais elle dépend d'une promesse que l'énoncé doit alors faire. Le cas ordinaire cachait l'erreur parce que \(0\) se trouvait être plus petit que tous les nombres essayés.
| Instruction | \(m\) | \(x\) | \(x > m\) | Affichage |
| \(m \leftarrow 0\) | \(0\) | |||
| tour \(1\) | \(0\) | \(-3\) | faux | |
| tour \(2\) | \(0\) | \(-9\) | faux | |
| tour \(3\) | \(0\) | \(-4\) | faux | |
| tour \(4\) | \(0\) | \(-1\) | faux | |
| Afficher \(m\) | \(0\) | \(-1\) | \(0\) |
Un exemple ne prouve pas
Un jeu d'essai qui passe montre que l'algorithme est juste sur ce cas, et ne dit rien des autres. Le maximum de l'exemple précédent avait passé un essai et était faux tout de même. Essayer reste le moyen le moins coûteux de trouver une faute : un seul cas qui échoue suffit à prouver que l'algorithme est faux, et il la désigne. Prouver qu'un algorithme est juste pour toutes ses entrées est une autre affaire, qui demande une phrase vraie à chaque tour de sa boucle (un invariant).
Méthode — Trouver la ligne fautive
- Chercher un cas qui échoue, et écrire le résultat attendu sur ce cas.
- Exécuter à la main et, à chaque ligne, se demander ce que la valeur devrait être à cet endroit, sur un cas assez petit pour être suivi sans l'algorithme.
- S'arrêter à la première ligne où le tableau et l'attente se séparent : la faute est dans l'instruction de cette ligne, pas avant.
- Dire ce que fait cette instruction et ce qu'elle aurait dû faire, puis la corriger et rejouer tous les jeux d'essai, y compris ceux qui passaient.
Exemple
La fonction ci-dessous doit rendre le nombre de ses trois arguments qui sont strictement positifs. L'appel count_positive(2, 3, 4) rend \(1\) au lieu de \(3\). Quelle ligne est fautive ? Fonction count_positive(a, b, c)
n ← 0
Si a > 0 alors
n ← n + 1
Fin Si
Si b > 0 alors
n ← n + 1
Fin Si
Si c > 0 alors
n ← 1
Fin Si
Renvoyer n
Fin Fonction
La ligne
Les deux premières conditionnelles portent le compteur à \(2\), exactement comme attendu ; la quatrième ligne est la première où le tableau et l'attente se séparent, et la faute est l'instruction de cette ligne. Affecter \(1\) jette tout ce qui a été compté avant, au lieu de lui ajouter un. L'erreur est invisible sur un appel où seul le troisième argument est positif, ce pourquoi le cas choisi doit en avoir plusieurs.
n \(\leftarrow\) 1 de la troisième conditionnelle, qui devrait être n \(\leftarrow\) n + 1. | Instruction | \(n\) | Attendu |
| \(n \leftarrow 0\) | \(0\) | \(0\) |
| premier argument compté | \(1\) | \(1\) |
| deuxième argument compté | \(2\) | \(2\) |
| \(n \leftarrow 1\) | \(1\) | \(3\) |
| Renvoyer \(n\) | \(1\) | \(3\) |
Choisir les cas
Un bon ensemble de jeux d'essai est petit et varié : un cas ordinaire, les limites du problème, et un cas construit exprès pour attraper l'erreur que l'on soupçonne. Essayer dix cas semblables apprend moins qu'en essayer trois choisis. Et quand une faute a été corrigée, tous les cas sont rejoués : une correction qui répare un cas et en casse un autre est un accident fréquent, que seule la reprise des essais attrape.
Compétences à pratiquer
- Prédire
- Les fonctions
- Vérifier
V
Pour aller plus loin
Compétences à pratiquer
- Problèmes
- Quiz
Aller à la section