Du problème à l’algorithme

Résumé

Cette leçon ne contient pas de code, et ce n’est pas un oubli : l’algorithme précède le programme, et qui ne sait pas décrire avec précision ce qu’il faut faire ne saura pas non plus le dire en C++. On apprend d’abord à spécifier un problème, c’est-à-dire à déclarer quelles données il reçoit, quel résultat il doit rendre et quelle relation les unit, et l’on montre qu’un même énoncé admet des spécifications différentes. On définit ensuite l’algorithme comme une procédure finie, précise et générale, et l’on écrit en étapes numérotées celui de la division par soustractions successives. On apprend à suivre un algorithme à la main avec un tableau de suivi, qui sera pendant tout le cours le premier instrument pour comprendre et pour déboguer. On présente les trois façons de combiner des étapes (séquence, décision et répétition), avec lesquelles s’écrit tout algorithme, et l’on apprend à justifier qu’une répétition se termine au moyen d’une quantité qui décroît à chaque itération et ne peut pas descendre indéfiniment.

Objectifs d’apprentissage

Spécifier un problème simple en indiquant ses entrées, ses sorties et les conditions qu’elles doivent remplir.
Décrire un algorithme en étapes numérotées, sans ambiguïté, avec des décisions et des répétitions explicites.
Suivre à la main un algorithme avec un tableau de suivi et déterminer son résultat pour une entrée donnée.
Distinguer, dans une procédure donnée, la séquence, la décision et la répétition, et justifier qu’une répétition se termine.

Qu’est-ce qu’un problème algorithmique

Un problème algorithmique est une relation entre deux sortes de données : celles que l’on reçoit, appelées entrée, et celles que l’on doit rendre, appelées sortie. Le résoudre ne consiste pas à obtenir une réponse pour un cas, mais à disposer d’une méthode qui, pour chaque entrée admissible, produise une sortie qui satisfasse la relation. « Combien font 17 divisé par 5 ? » est une question ; « étant donné deux entiers, obtenir leur quotient et leur reste » est un problème, parce qu’il parle de toutes les paires d’entiers à la fois.

Or le langage courant est imprécis, et le même énoncé peut s’entendre de plusieurs manières. C’est pourquoi, avant de résoudre, on spécifie : on écrit ce qui entre, ce qui sort et quelles conditions chaque chose doit remplir. La spécification a trois parties. L’entrée énumère les données avec leur sorte (entiers, décimaux, mots) et les conditions qu’on leur impose, que l’on appelle précondition : qui utilise la solution s’engage à les respecter. La sortie énumère les résultats. La relation, ou postcondition, dit ce que la sortie doit vérifier par rapport à l’entrée : qui écrit la solution s’engage à la garantir chaque fois que la précondition a été respectée. Il s’ensuit que la spécification est un contrat entre qui pose le problème et qui le résout, et qu’en dehors de la précondition la solution ne promet rien.

ExempleLe maximum de trois nombres

Énoncé courant : « trouver le plus grand de trois nombres ». Spécification :

Entrée : trois nombres $x$ , $y$ , $z$ (entiers ou décimaux, sans autre condition).
Sortie : un nombre $m$ .
Relation : $m$ est l’une des trois données, et aucune d’elles n’est plus grande que $m$ ; c’est-à-dire $m \geq x$ , $m \geq y$ et $m \geq z$ .

La relation ne dit pas « le plus grand des trois », ce qui est justement ce que l’on voulait préciser, mais deux conditions vérifiables. La première exige que $m$ soit l’une des données (sans elle, le nombre 1000 vérifierait la seconde pour presque toute entrée) ; la seconde, qu’aucune ne le dépasse. Et la spécification tranche au passage un doute que l’énoncé laissait ouvert : si deux données sont à égalité pour le maximum, comme dans $(4, 9, 9)$ , la sortie est $9$ , et il n’y a là aucune erreur.

Un même énoncé admet des spécifications différentes, et choisir entre elles est une décision, non un oubli. Le cas le plus instructif est celui de la division entière. Pour des entiers $a \geq 0$ et $b > 0$ , tout le monde est d’accord : le quotient $q$ et le reste $r$ sont les seuls entiers qui vérifient

a = b \cdot q + r, \quad 0 \leq r < b

Ainsi, pour $a = 17$ et $b = 5$ , ce sont $q = 3$ et $r = 2$ , parce que $17 = 5 \cdot 3 + 2$ . Mais l’énoncé « diviser deux entiers » ne dit pas que faire si $a$ est strictement négatif, et la question n’est pas oiseuse : pour $a = -7$ et $b = 2$ , il y a deux réponses raisonnables.

ExempleDeux spécifications de la division à dividende strictement négatif

Première spécification : le reste n’est jamais strictement négatif, $0 \leq r < b$ . Alors $-7 = 2 \cdot (-4) + 1$ , et la sortie est $q = -4$ , $r = 1$ . C’est celle que l’on étudie en mathématiques, dans la leçon « Divisibilité et division euclidienne » du cours Algèbre et géométrie I.

Seconde spécification : le quotient est le résultat de la division avec décimales, dont on écarte la partie décimale, c’est-à-dire arrondi vers zéro ; le reste est ce qui manque, et il a le signe du dividende. Alors $-7 / 2 = -3{,}5$ se tronque en $-3$ , et $-7 = 2 \cdot (-3) + (-1)$ : la sortie est $q = -3$ , $r = -1$ .

Les deux vérifient $a = b \cdot q + r$ ; elles diffèrent par la condition imposée au reste. Aucune n’est une erreur, mais un programme qui utilise l’une en croyant utiliser l’autre donnera des résultats faux avec les nombres strictement négatifs. On peut l’annoncer dès maintenant : C++ adopte la seconde, comme on le verra dans la leçon Arithmétique ; qui attend la première aura une surprise.

Il existe une troisième option, la plus fréquente en pratique : exclure le cas par la précondition. Si la spécification exige $a \geq 0$ , le problème des dividendes strictement négatifs disparaît, non parce qu’on l’a résolu, mais parce que qui utilise la solution s’est engagé à ne pas le poser. Ce que l’on ne peut pas faire, c’est laisser la question sans réponse. Et pour la même raison la spécification exige $b > 0$ : avec $b = 0$ , il n’existe pas de $q$ et de $r$ qui vérifient la relation, et le contrat doit le dire.

Une erreur fréquente consiste à spécifier par un exemple : « la sortie de 17 et 5 est 3 et 2 ». Un exemple illustre, mais ne spécifie pas, parce qu’il ne dit pas ce qui arrive avec les autres entrées ; une infinité de relations différentes coïncident sur un cas. La spécification s’écrit comme une condition générale, et les exemples servent ensuite à la vérifier.

Algorithmes

Une fois le problème spécifié, on cherche une méthode pour le résoudre. Un algorithme est une suite d’instructions qui, appliquée à toute entrée vérifiant la précondition, produit en un nombre fini d’étapes une sortie qui vérifie la postcondition. La définition contient trois exigences.

Finitude. L’algorithme s’écrit avec un nombre fini d’instructions et, pour chaque entrée admissible, il se termine après en avoir exécuté un nombre fini. Une procédure qui, pour une certaine entrée, continue indéfiniment n’est pas un algorithme pour cette entrée.
Précision. Chaque instruction a une seule signification, et qui l’exécute sait à tout moment quoi faire et quelle est l’instruction suivante. Aucune décision n’est laissée à l’appréciation de qui exécute.
Généralité. L’algorithme résout le problème pour toutes les entrées admissibles, pas seulement pour un cas.

Avec une certaine liberté, on appelle aussi algorithme une procédure précise et qui se termine, mais qui pour une certaine entrée admissible ne vérifie pas la postcondition : en toute rigueur, c’est un algorithme pour un autre problème, et l’on dira qu’il est incorrect pour le problème spécifié. C’est ainsi que parleront les problèmes de cette leçon, qui réfutent des algorithmes incorrects par un contre-exemple.

Une recette de cuisine ressemble à un algorithme, et c’est pourquoi elle est la comparaison habituelle ; mais presque aucune n’en est un. « Ajouter une pincée de sel » n’est pas précis, parce qu’une pincée n’est pas une quantité ; « cuire au four jusqu’à ce que ce soit doré » dépend d’un jugement que deux personnes porteraient différemment ; « battre plusieurs fois » ne dit pas combien. Un cuisinier comble ces lacunes par son expérience ; un ordinateur n’en a aucune. Il s’ensuit l’exigence qui gouverne tout le cours : un algorithme doit pouvoir être suivi par qui ne comprend pas le problème, sans rien deviner. Si, pour exécuter une étape, il faut savoir à quoi elle sert, l’étape est mal écrite.

Les algorithmes de ce cours s’écrivent d’abord en étapes numérotées, en français, avec quelques conventions. Les données qui changent pendant l’algorithme se nomment par des lettres ou des mots, comme $q$ ou $r$ , et s’appellent des variables. On écrit « $r$ prend la valeur $r - b$ » pour dire que l’on calcule $r - b$ avec la valeur actuelle de $r$ et que le résultat devient la nouvelle valeur de $r$ ; l’ancienne valeur est perdue. Dans la forme abrégée, que l’on utilise pour prendre des notes, la même instruction s’écrit avec une flèche vers la gauche, qui au clavier est r <- r - b. Les instructions s’exécutent dans l’ordre de leur numéro, sauf si l’une d’elles dit autre chose.

ExempleLa division par soustractions successives

Le problème est celui que l’on a spécifié dans la section précédente : en entrée, deux entiers $a \geq 0$ et $b > 0$ ; en sortie, deux entiers $q$ et $r$ avec $a = b \cdot q + r$ et $0 \leq r < b$ . L’idée est celle du partage : on retire de $a$ des groupes de $b$ tant que c’est possible, on compte les groupes retirés, et ce qui reste est le reste.

$q$ prend la valeur $0$ , et $r$ prend la valeur $a$ .
Tant que $r \geq b$ est vérifiée, répéter les étapes 3 et 4 ; quand elle cesse de l’être, continuer à l’étape 5.
$r$ prend la valeur $r - b$ .
$q$ prend la valeur $q + 1$ ; revenir à l’étape 2.
Rendre $q$ et $r$ , et terminer.

L’étape 2 est une question que l’on pose chaque fois : avant la première itération (ou premier tour) et après chacune. Les étapes 3 et 4 forment le corps de la répétition, ce qui se répète. Rien n’est laissé à l’appréciation de qui exécute : à chaque instant, il n’y a qu’une instruction suivante.

L’algorithme est lent (pour diviser un million par trois, il fait plus de trois cent mille itérations), et la méthode scolaire de la division est beaucoup plus rapide ; mais il est correct, et sa simplicité le rend idéal pour apprendre à raisonner sur les algorithmes. Le cours reviendra sur la différence entre un algorithme correct et un algorithme efficace dans la leçon Le coût d’un algorithme.

Il convient, enfin, de séparer l’algorithme de son écriture. L’algorithme de la division par soustractions est le même, qu’on l’écrive en français, dans un diagramme, en C++ ou dans tout autre langage de programmation : ce qui le définit, c’est la suite des opérations, non les mots. Un programme est l’écriture d’un algorithme dans un langage qu’une machine peut exécuter, et la leçon Programmes, compilateurs et C++ expliquera comment se fait cette exécution. S’il en est ainsi, un programme peut être faux de deux manières très différentes : parce que l’algorithme est incorrect, et alors aucun langage ne le sauve, ou parce que l’algorithme est correct mais a été mal écrit. Distinguer ces deux cas est la moitié du travail de débogage, et c’est pourquoi le cours écrit toujours d’abord l’algorithme.

Suivre un algorithme à la main

Lire un algorithme ne suffit pas pour savoir ce qu’il fait ; il faut l’exécuter. Le suivre à la main, comme le ferait la machine, sans sauter d’étapes ni deviner de résultats, est la compétence la plus utile d’un programmeur : avec elle, on vérifie un algorithme avant de l’écrire, on prédit la sortie d’un programme avant de l’exécuter et l’on trouve l’erreur de celui qui échoue.

L’instrument est le tableau de suivi : une colonne pour le numéro de l’étape exécutée, une colonne par variable et, si c’est utile, une pour les conditions évaluées ; et une ligne par étape exécutée. Dans chaque ligne, on note la nouvelle valeur de la variable qui a changé à cette étape et l’on laisse en blanc ce qui n’a pas changé, de sorte que la valeur actuelle d’une variable est la dernière écrite dans sa colonne. Les conditions se notent avec leur résultat.

ExempleLa trace de la division de 17 par 5

On suit la division par soustractions successives avec $a = 17$ et $b = 5$ . La flèche de la figure indique l’étape qui vient d’être exécutée ; la ligne pointillée rappelle que l’étape 4 revient à l’étape 2.

Démonstration

$(q, r) = (0, 17)$
Étape 1 : on donne les valeurs initiales. L’entrée vérifie la précondition, parce que $17 \geq 0$ et $5 > 0$ .
$(q, r) = (1, 12)$
Première itération. À l’étape 2, on vérifie que $17 \geq 5$ , de sorte que l’on exécute le corps : l’étape 3 retire un groupe de cinq et l’étape 4 le compte.
$(q, r) = (2, 7)$
Deuxième itération : $12 \geq 5$ , et le corps s’exécute de nouveau.
$(q, r) = (3, 2)$
Troisième itération : $7 \geq 5$ , et le corps s’exécute de nouveau.
$17 = 5 \cdot 3 + 2, \quad 0 \leq 2 < 5$
À l’étape 2, la condition échoue, parce que $2 < 5$ : l’algorithme continue à l’étape 5 et rend $q = 3$ et $r = 2$ . La sortie vérifie la postcondition.

Le tableau complet a douze lignes : l’étape 1, trois itérations de trois lignes chacune (étapes 2, 3 et 4), la vérification qui échoue et le rendu du résultat.

Deux observations sur le tableau. La première : le nombre d’itérations est égal au quotient, $3$ , et l’étape 2 a été exécutée une fois de plus que le corps, $4$ fois ; cela arrive toujours dans une répétition de cette forme, parce que la dernière vérification est celle qui échoue. La seconde : la trace enseigne quelque chose que le texte de l’algorithme ne dit pas à première vue ; si $a < b$ , par exemple $a = 3$ et $b = 5$ , la condition échoue dès la première fois, le corps ne s’exécute aucune fois, et la sortie est $q = 0$ , $r = 3$ , ce qui est correct, parce que $3 = 5 \cdot 0 + 3$ . Oublier le cas où la répétition ne s’exécute pas est l’une des erreurs les plus fréquentes dans la conception d’algorithmes, et la trace avec de petites entrées la révèle.

La trace d’un cas ne démontre pas que l’algorithme est correct : elle vérifie un cas. Mais une trace bien choisie (un cas courant, un cas limite, le cas où la répétition ne s’exécute pas) révèle la plupart des erreurs, et celle qui échoue dit où elles sont. La leçon Concevoir des boucles correctes apprendra à passer des cas à une démonstration.

Séquence, décision et répétition

Vus de près, les algorithmes se construisent avec très peu de pièces. Il y a des instructions élémentaires (donner une valeur à une variable, rendre un résultat) et trois manières de les combiner.

Séquence : une instruction après une autre, dans l’ordre. Les étapes 3 et 4 de la division sont une séquence : d’abord on soustrait, ensuite on compte.
Décision : selon qu’une condition est vérifiée ou non, on exécute une partie ou une autre (ou une partie ou rien). « Si $y > m$ , $m$ prend la valeur $y$ » est une décision.
Répétition : tant qu’une condition est vérifiée, on exécute une partie encore et encore. L’étape 2 de la division, avec son corps, est une répétition.

Chaque forme a une seule entrée et une seule sortie, et son intérieur peut être à son tour n’importe laquelle des trois : le corps d’une répétition peut contenir des décisions, une branche d’une décision peut contenir une répétition, et ainsi de suite. S’il en est ainsi, avec les trois formes on construit des algorithmes de n’importe quelle complexité, comme avec quelques pièces qui s’emboîtent on construit n’importe quel édifice. Qu’elles suffisent à exprimer tout algorithme est un résultat connu de la théorie de la programmation (Corrado Böhm et Giuseppe Jacopini l’ont démontré en 1966) ; on ne le démontre pas ici, mais tout le cours le confirme : les programmes que l’on y écrira, aussi longs soient-ils, n’utiliseront rien d’autre que ces trois formes, écrites en C++ comme if pour la décision et while ou for pour la répétition, dans les leçons Décisions et Boucles.

Une notation utile pour voir la forme d’un algorithme est l’organigramme : chaque instruction est un rectangle, chaque condition un losange à deux sorties (vérifiée, que la figure étiquette $1$ , et non vérifiée, $0$ ), et les flèches disent quelle est l’étape suivante. C’est une notation, non une fin : elle sert à embrasser d’un coup d’œil un petit algorithme, mais elle ne passe pas à l’échelle, et personne n’écrit un grand programme en le dessinant.

ExempleTrois formes et leur composition

La figure dessine les trois formes avec des instructions génériques $A$ et $B$ et une condition $c$ , puis les compose dans le diagramme de la division par soustractions successives.

Démonstration

$A ; B$
Séquence : on exécute $A$ puis $B$ ; il y a une seule entrée et une seule sortie.
$c = 1 \Rightarrow A, \quad c = 0 \Rightarrow B$
Décision : si $c$ est vérifiée, on exécute $A$ ; sinon, $B$ . Les deux branches se rejoignent en une seule sortie.
$c, A, c, A, \ldots, c$
Répétition : on évalue $c$ ; si elle est vérifiée, on exécute $A$ et l’on évalue de nouveau $c$ ; sinon, on sort. La condition est évaluée une fois de plus que le corps.
$a = b \cdot q + r, \quad 0 \leq r < b$
Composition : la division par soustractions successives est une séquence (les valeurs initiales, la répétition, le rendu du résultat) dont la répétition a pour corps une autre séquence (soustraire, compter).

Distinguer les trois formes dans une procédure écrite en langage courant est le premier pas pour la traduire. Le signe d’une décision est un « si », un « au cas où » ou un « selon » ; celui d’une répétition, un « tant que », un « jusqu’à ce que », un « pour chaque » ou un « autant de fois que ». Une procédure sans aucun de ces mots est une séquence, et si elle doit traiter des entrées de taille variable (une liste de nombres, un texte), il lui manque une répétition.

L’algorithme se termine-t-il ?

La finitude fait partie de la définition de l’algorithme, et une répétition est le seul endroit où elle peut se perdre : une séquence de cinq étapes exécute cinq étapes, et une décision exécute l’une de ses branches ; mais une répétition exécute son corps autant de fois que la condition est vérifiée, et rien ne garantit d’avance qu’elle cesse de l’être.

Pour justifier qu’une répétition se termine, on cherche une quantité, calculée à partir des variables, qui remplisse deux conditions : c’est un entier naturel (un entier positif ou nul) tant que la répétition continue, et elle décroît strictement à chaque itération. S’il en est ainsi, la répétition se termine : une suite d’entiers naturels strictement décroissante ne peut pas être infinie, parce que chaque itération la fait baisser d’au moins un et qu’à partir d’un entier naturel $n$ il n’y a pas plus de $n$ marches jusqu’à zéro. Cette quantité s’appelle un variant ou une fonction de borne, et la leçon Concevoir des boucles correctes l’utilisera de manière systématique.

ExempleLe variant de la division par soustractions

Dans la division par soustractions successives, le variant est $r$ . Tant que la répétition continue, $r \geq b > 0$ , de sorte que $r$ est un entier naturel. À chaque itération, $r$ prend la valeur $r - b$ , et comme $b > 0$ (précondition), la nouvelle valeur est strictement plus petite. Par conséquent, la répétition se termine, et elle le fait au plus après $a$ itérations (en fait, exactement après $q$ itérations, le quotient).

On remarquera où l’on a utilisé la précondition $b > 0$ . Si l’on exécute l’algorithme avec $b = 0$ , l’étape 3 laisse $r$ inchangé, la condition $r \geq 0$ est toujours vérifiée et la répétition ne se termine jamais : l’algorithme n’est pas faux, on lui a donné une entrée que le contrat excluait. Et si $b$ était strictement négatif, $r$ croîtrait à chaque itération. La précondition n’est pas un ornement : c’est exactement ce qu’il faut pour que le raisonnement fonctionne.

Les deux conditions du variant sont nécessaires, et il est facile de se tromper sur l’une ou l’autre. Soit cette procédure, qui prétend décider si un entier naturel $n$ est pair : « tant que $n \neq 0$ , $n$ prend la valeur $n - 2$ ; si l’on arrive à zéro, $n$ était pair ». La quantité $n$ décroît à chaque itération, et pourtant la procédure ne se termine pas si $n$ est impair : avec $n = 5$ , elle passe par $3$ , $1$ , $-1$ , $-3$ , et la condition $n \neq 0$ n’échoue jamais. Ce qui n’est pas rempli, c’est l’autre condition : $n$ cesse d’être un entier naturel, parce que la condition de la répétition ne l’empêche pas de descendre sous zéro. La correction consiste à répéter tant que $n \geq 2$ et à décider à la fin selon la valeur qui reste, $0$ ou $1$ ; maintenant $n$ est un entier naturel à chaque itération, parce qu’on ne soustrait que lorsque $n \geq 2$ , et il décroît : la procédure se termine.

Décider si une répétition se termine n’est pas toujours facile. Un exemple célèbre : en partant d’un entier naturel $n \geq 1$ , tant que $n \neq 1$ , si $n$ est pair on le divise par deux, et s’il est impair on le remplace par $3n + 1$ . Avec $n = 6$ , la suite est $6, 3, 10, 5, 16, 8, 4, 2, 1$ , et elle se termine. Personne n’a trouvé de $n$ pour lequel elle ne se termine pas, et on l’a vérifié par ordinateur pour des quantités énormes de valeurs ; mais personne n’a réussi à démontrer qu’elle se termine toujours : c’est la conjecture de Collatz, un problème ouvert des mathématiques. Aucune quantité connue ne décroît à chaque itération. La morale, pour qui programme, est modeste et ferme : un algorithme dont on ne sait pas justifier la terminaison n’est pas terminé.

Erreurs fréquentes

Étapes ambiguës. « Répéter plusieurs fois », « jusqu’à ce que ce soit bien », « prendre un nombre adéquat ». Chaque étape doit pouvoir s’exécuter sans comprendre le problème ; sinon, elle est mal écrite.
Oublier le cas où la répétition ne s’exécute pas. Toute répétition dont la condition est au début peut exécuter son corps zéro fois. Il faut toujours se demander ce que rend l’algorithme dans ce cas, et la trace avec une entrée minimale y répond.
Spécifier par un exemple. « Pour 17 et 5, cela donne 3 et 2 » n’est pas une spécification ; la relation s’écrit comme une condition générale, et l’exemple l’illustre.
Confondre l’algorithme avec son programme. Un programme qui échoue peut avoir un algorithme faux ou une écriture fausse. Qui n’a pas écrit l’algorithme avant ne sait pas laquelle des deux choses chercher.
Tenir la terminaison pour acquise. Qu’une quantité décroisse ne suffit pas : elle doit en outre être un entier naturel tant que l’on répète.

Problèmes résolus

Problème résolu 1Le plus grand de trois nombres, avec égalités

Écrire un algorithme qui vérifie la spécification du maximum de trois nombres donnée au début de la leçon, et le suivre à la main pour les entrées $(7, 2, 5)$ et $(4, 9, 9)$ .

Solution

$m = x$
Idée : on parcourt l’entrée en gardant le plus grand vu jusqu’ici dans une variable $m$ . Première étape : $m$ prend la valeur $x$ . Après elle, $m$ est le maximum des données vues, qui se réduisent à $x$ .
$m = \max(x, y, z)$
Deuxième étape : si $y > m$ , $m$ prend la valeur $y$ . Troisième étape : si $z > m$ , $m$ prend la valeur $z$ . Quatrième étape : rendre $m$ . Ce sont trois instructions en séquence, dont deux sont des décisions sans branche alternative.
$(x, y, z) = (7, 2, 5) \Rightarrow m = 7$
Trace pour $(7, 2, 5)$ : après la première étape, $m = 7$ ; à la deuxième, $2 > 7$ est faux et $m$ ne change pas ; à la troisième, $5 > 7$ est faux et $m$ ne change pas. On rend $7$ .
$(x, y, z) = (4, 9, 9) \Rightarrow m = 9$
Trace pour $(4, 9, 9)$ : après la première étape, $m = 4$ ; à la deuxième, $9 > 4$ et $m$ passe à $9$ ; à la troisième, $9 > 9$ est faux et $m$ ne change pas. On rend $9$ , ce qui est correct : l’égalité n’exige aucun traitement particulier.
$m \geq x, \quad m \geq y, \quad m \geq z$
Justification : après chaque étape, $m$ est l’une des données vues et aucune d’elles ne le dépasse. C’est vrai après la première, et chaque décision le conserve : si la nouvelle donnée est plus grande, elle devient $m$ ; sinon, elle ne dépasse pas $m$ . À la fin, on a vu les trois, et $m$ vérifie la postcondition.
$(x, y, z) = (4, 9, 9) \Rightarrow p \in \{2, 3\}$
Si l’on avait écrit $y \geq m$ au lieu de $y > m$ , le résultat serait le même, parce qu’en cas d’égalité on affecte une valeur égale. Le choix entre $>$ et $\geq$ importerait si l’on demandait aussi la position du maximum : avec $>$ , on rend la première des positions à égalité, et avec $\geq$ la dernière ; la formule appelle cette position $p$ .

Problème résolu 2L’année bissextile, corrigée par un contre-exemple

Dans le calendrier grégorien, une année est bissextile si elle est divisible par $4$ , sauf celles divisibles par $100$ , qui ne le sont que si elles sont en outre divisibles par $400$ . Un étudiant propose l’algorithme « si l’année est divisible par $4$ , rendre oui ; sinon, rendre non ». Trouver une année pour laquelle il échoue et écrire un algorithme correct, avec sa spécification.

Solution

$(4 \mid n \wedge \neg (100 \mid n)) \vee 400 \mid n$
Spécification. Entrée : un entier $n \geq 1583$ (le calendrier grégorien est en vigueur depuis octobre 1582). Sortie : oui ou non. Relation : la sortie est oui exactement quand $n$ est divisible par $4$ et non par $100$ , ou est divisible par $400$ .
$1900 = 4 \cdot 475, \quad 1900 = 400 \cdot 4 + 300$
L’algorithme proposé est juste pour la plupart des années, et c’est pourquoi il paraît correct. Pour le réfuter, il suffit d’une année divisible par $100$ et non par $400$ : $1900$ est divisible par $4$ , et l’algorithme dit oui ; mais $1900$ n’a pas été bissextile.
$400 \mid n, \quad 100 \mid n, \quad 4 \mid n$
Algorithme corrigé, en trois décisions enchaînées. Étape 1 : si $n$ est divisible par $400$ , rendre oui et terminer. Étape 2 : si $n$ est divisible par $100$ , rendre non et terminer. Étape 3 : si $n$ est divisible par $4$ , rendre oui ; sinon, rendre non.
$2000, \quad 1900, \quad 2024, \quad 2023$
L’ordre des questions est essentiel : elles vont de la règle la plus particulière à la plus générale. Si l’on posait d’abord la question du $4$ , l’année $1900$ recevrait oui avant d’arriver à l’exception. Trace pour quatre années, une par cas : $2000$ (étape 1 : oui), $1900$ (étape 2 : non), $2024$ (étape 3 : oui), $2023$ (étape 3 : non).
$4 \mid 1900 \wedge \neg (400 \mid 1900)$
L’enseignement ne concerne pas seulement les calendriers : un algorithme se réfute par un seul contre-exemple, et les contre-exemples se cherchent aux frontières des règles, non dans les cas courants. Essayer $2024$ , $2020$ et $2016$ n’aurait rien révélé.

Problème résolu 3Combien d’itérations fait la division par soustractions

Suivre à la main la division par soustractions successives avec $a = 20$ et $b = 5$ , et avec $a = 0$ et $b = 7$ . Ensuite, justifier que pour toute entrée admissible l’algorithme se termine après exactement $q$ itérations et que sa sortie vérifie la postcondition.

Solution

$20 = 5 \cdot 4 + 0$
Trace avec $a = 20$ , $b = 5$ : $r$ passe par $20$ , $15$ , $10$ , $5$ , $0$ , et $q$ par $0$ , $1$ , $2$ , $3$ , $4$ . La cinquième vérification, $0 \geq 5$ , échoue. Sortie : $q = 4$ , $r = 0$ . Ici, le cas limite est la division exacte : la quatrième itération a lieu parce que $5 \geq 5$ , et c’est pourquoi la condition doit être $\geq$ et non $>$ .
$0 = 7 \cdot 0 + 0$
Trace avec $a = 0$ , $b = 7$ : la première vérification, $0 \geq 7$ , échoue ; le corps ne s’exécute aucune fois. Sortie : $q = 0$ , $r = 0$ , ce qui est correct.
$\dato{conserva}{b \cdot (q + 1) + (r - b) = b \cdot q + r = a}$
Une relation qui se conserve. Avant la première itération, $b \cdot q + r = b \cdot 0 + a = a$ . À chaque itération, $r$ diminue de $b$ et $q$ augmente de $1$ , de sorte que $b \cdot q + r$ ne change pas. Par conséquent, l’égalité est vraie après chaque itération.
$r_0 > r_1 > r_2 > \cdots \geq 0$
Terminaison. Tant que l’on répète, $r \geq b > 0$ , et $r$ est un entier naturel ; à chaque itération, il diminue de $b \geq 1$ . Une suite strictement décroissante d’entiers naturels est finie : la répétition se termine.
$a = b \cdot q + r, \quad 0 \leq r < b$
À la fin, la condition a échoué : $r < b$ . De plus $r \geq 0$ , parce qu’on ne soustrait $b$ que lorsque $r \geq b$ . Avec la relation qui se conserve, la sortie vérifie la postcondition ; et comme $q$ compte les itérations, le nombre d’itérations est le quotient.

Exercices en ligne

Exercice 1Compter les itérations

Suivre à la main l’algorithme suivant et écrire dans la case la valeur qu’il rend, seulement le nombre.

$n$ prend la valeur $29$ , et $k$ prend la valeur $0$ .
Tant que $n > 1$ est vérifiée, répéter les étapes 3 et 4 ; quand elle cesse de l’être, continuer à l’étape 5.
Si $n$ est pair, $n$ prend la valeur $n / 2$ ; s’il est impair, $n$ prend la valeur $n + 1$ .
$k$ prend la valeur $k + 1$ ; revenir à l’étape 2.
Rendre $k$ .

Le navigateur vérifie ta réponse instantanément, sans la noter.

Écris ta réponse ici

Indice

Faites le tableau : $n$ passe de $29$ à $30$ à la première itération. Comptez une itération pour chaque changement de $n$ , jusqu’à ce que $n$ vaille $1$ .

Exercice 2La condition qui manque

L’algorithme suivant, écrit sous la forme abrégée, doit calculer le quotient et le reste de la division par soustractions successives, mais il lui manque la condition de la répétition. Remplacer la ligne de tirets bas par la condition correcte, sans changer le reste.

Le navigateur vérifie ta réponse instantanément, sans la noter.

Écris ta réponse ici

Indice

Suivez à la main l’algorithme avec $a = 10$ et $b = 5$ : la deuxième itération doit avoir lieu même si le reste vaut exactement $5$ .

Problèmes proposés

Chaque problème a une indication, qu’il vaut mieux n’ouvrir qu’après avoir cherché, et une réponse, qui apparaît après l’ouverture de l’indication.

Problème proposé 1Spécifier l’ordre de trois nombres

Écrire la spécification du problème « ordonner trois nombres » (entrée, sortie et relation) et signaler quelles décisions elle oblige à prendre que l’énoncé ne prenait pas. Ensuite, vérifier que la spécification écarte ces deux sorties pour l’entrée $(5, 2, 5)$ : $(2, 5, 6)$ et $(2, 5, 5, 5)$ , et qu’elle admet $(2, 5, 5)$ .

Indice

Une sortie « ordonnée » peut n’avoir rien à voir avec l’entrée. Quelle condition lie les nombres de la sortie à ceux de l’entrée, répétitions comprises ? Croissant ou décroissant ? Strict ou non ?

Réponse

Entrée : trois nombres $x$ , $y$ , $z$ . Sortie : trois nombres $u$ , $v$ , $w$ . Relation : $u \leq v \leq w$ , et $(u, v, w)$ est un réarrangement de $(x, y, z)$ , c’est-à-dire qu’il contient les mêmes valeurs avec les mêmes répétitions. Décisions que l’énoncé ne prenait pas : le sens (ici, du plus petit au plus grand) ; que l’ordre n’est pas strict ( $\leq$ et non $<$ , parce qu’avec des valeurs répétées l’ordre strict est impossible) ; et que la sortie doit être un réarrangement. $(2, 5, 6)$ est ordonné mais contient un $6$ qui n’y était pas ; $(2, 5, 5, 5)$ a quatre valeurs ; $(2, 5, 5)$ remplit les deux conditions. Sans la condition de réarrangement, $(0, 0, 0)$ serait une sortie correcte pour n’importe quelle entrée.

Problème proposé 2Les chiffres d’un nombre, de droite à gauche

Écrire un algorithme en étapes numérotées qui reçoive un entier naturel $n$ et rende ses chiffres du dernier au premier (pour $4072$ , il rend $2$ , $7$ , $0$ , $4$ ), en n’utilisant que le quotient et le reste de la division par $10$ . Le suivre à la main pour $4072$ et pour $0$ , et justifier qu’il se termine pour tout $n$ .

Indice

Le reste de la division par $10$ est le dernier chiffre, et le quotient est le nombre sans lui. Décidez si la condition se pose avant ou après avoir rendu un chiffre, et regardez ce qui arrive avec $n = 0$ , qui a un chiffre.

Réponse

Un algorithme correct : (1) rendre le reste de la division de $n$ par $10$ ; (2) $n$ prend la valeur du quotient de la division de $n$ par $10$ ; (3) si $n > 0$ , revenir à l’étape 1 ; sinon, terminer. La question vient après le corps, de sorte que le corps s’exécute au moins une fois : pour $n = 0$ , il rend $0$ , qui est son unique chiffre. Si l’on posait la question au début (« tant que $n > 0$ »), pour $n = 0$ on ne rendrait rien ; c’est l’erreur qui consiste à oublier le cas où la répétition ne s’exécute pas. Trace pour $4072$ : on rend $2$ , $7$ , $0$ , $4$ , et $n$ passe par $407$ , $40$ , $4$ , $0$ . Terminaison : le variant est $n$ , un entier naturel ; si l’on revient à l’étape 1, c’est parce que $n > 0$ , et pour $n \geq 1$ le quotient par $10$ est strictement plus petit que $n$ , de sorte que $n$ décroît strictement à chaque itération.

Problème proposé 3Rendre la monnaie en pièces

On dispose de pièces de $50$ , $10$ et $1$ unités, en quantité illimitée. Spécification : en entrée, un entier naturel $m$ ; en sortie, trois entiers naturels $c_{50}$ , $c_{10}$ , $c_1$ avec $50 c_{50} + 10 c_{10} + c_1 = m$ et le plus petit nombre possible de pièces, $c_{50} + c_{10} + c_1$ . Quelqu’un propose l’algorithme suivant. Trouver une entrée pour laquelle il échoue, expliquer chaque défaut et le corriger.

$c_{50}$ , $c_{10}$ et $c_1$ prennent la valeur $0$ .
Si $m \geq 50$ , $c_{50}$ prend la valeur $c_{50} + 1$ et $m$ prend la valeur $m - 50$ .
Tant que $m > 10$ : $c_{10}$ prend la valeur $c_{10} + 1$ et $m$ prend la valeur $m - 10$ .
Tant que $m > 0$ : $c_1$ prend la valeur $c_1 + 1$ et $m$ prend la valeur $m - 1$ .
Rendre $c_{50}$ , $c_{10}$ et $c_1$ .

Indice

La somme des pièces vaut toujours $m$ ; ce qui peut échouer, c’est leur nombre. Essayez un multiple exact de $10$ et un montant de plus de $100$ , et demandez-vous quelle façon de combiner des étapes utilise l’étape 2 et laquelle elle devrait utiliser.

Réponse

Il y a deux défauts. Premièrement, l’étape 3 utilise $m > 10$ : avec $m = 10$ , elle ne rend aucune pièce de $10$ et rend dix pièces de $1$ , au lieu d’une. Deuxièmement, l’étape 2 est une décision là où il faut une répétition : avec $m = 120$ , l’algorithme tel qu’il est écrit rend une pièce de $50$ , six de $10$ et dix de $1$ (dix-sept pièces), et même avec l’étape 3 déjà corrigée il rendrait une pièce de $50$ et sept de $10$ (huit), au lieu de deux de $50$ et deux de $10$ (quatre). L’entrée $m = 100$ montre les deux défauts : l’algorithme rend une pièce de $50$ , quatre de $10$ et dix de $1$ , quinze pièces, au lieu de deux. Correction : étape 2, « tant que $m \geq 50$ , … » ; étape 3, « tant que $m \geq 10$ , … ». Ainsi corrigé, l’algorithme prend toujours la plus grande pièce qui tient, et avec ces trois pièces cela donne le plus petit nombre : le chiffre des unités de $m$ ne peut se payer qu’avec des pièces de $1$ , et de ce qui reste il convient de payer le plus possible avec des pièces de $50$ , parce que cinq de $10$ valent autant qu’une de $50$ . Avec d’autres pièces, par exemple de $1$ , $3$ et $4$ pour $m = 6$ , prendre toujours la plus grande ne donne plus le minimum ( $4 + 1 + 1$ contre $3 + 3$ ).