Synthèse et défis : structures de contrôle

L’acquis de l’unité

L’unité s’était proposé d’apprendre à gouverner l’ordre d’exécution par des décisions et des boucles, et à raisonner sur leur correction : que chaque cas soit traité, que chaque boucle fasse ce qu’elle doit et qu’elle se termine. Ce but a été atteint en s’appuyant uniquement sur ce que l’introduction a déclaré tenir pour acquis : les conditions de l’unité 3, les types de l’unité 2, et la trace et le variant de la leçon 1.1. Le programme qui calculait le plus grand commun diviseur en trois étapes fixes, et qui, selon les données, répondait faux ou divisait par zéro, a été remplacé par une boucle de trois lignes, et l’on peut maintenant démontrer que cette boucle est correcte pour toutes les données positives ou nulles.

Décisions

La leçon Décisions a enseigné l’instruction if, toujours avec des accolades. Elle a montré que, dans une chaîne de else if, on exécute la première branche dont la condition est vraie, de sorte que le cas réel de chaque branche est sa condition jointe à la négation de toutes les précédentes ; d’où l’importance de l’ordre, et le fait qu’une branche puisse devenir inaccessible sans avertissement. Elle a établi le critère de correction de toute décision : ses cas doivent être disjoints (ils le sont par la forme de la chaîne) et exhaustifs (ils le sont si elle se termine par else), et ils doivent coïncider avec ceux de la spécification, ce que l’on teste à l’intérieur de chaque cas et de chaque côté de chaque frontière. Elle a présenté l’opérateur conditionnel, pour choisir entre deux valeurs brèves sans une décision entière. Elle s’est achevée sur enum class et switch, dont le compilateur signale le cas oublié.

Boucles

La leçon Boucles a présenté while, do et for comme trois formes d’un même mécanisme : le while évalue sa condition avant chaque itération et peut n’en faire aucune ; le do en fait au moins une ; le for réunit dans son en-tête l’initialisation, la condition et l’incrément, et sa variable de contrôle ne vit que dans la boucle. Elle a enseigné leurs équivalences, le tableau de suivi, avec $k + 1$ évaluations de la condition pour $k$ itérations d’un while qui se termine par sa condition (et $k$ évaluations dans un do), et le décompte des itérations à partir de l’en-tête, qui prévient l’erreur de décalage d’une unité. Elle a ajouté break, continue et les boucles imbriquées, dont le corps intérieur s’exécute un nombre de fois égal à une somme : $m \cdot p$ avec des bornes fixes, $n(n + 1)/2$ avec le triangle.

Concevoir des boucles correctes

La leçon Concevoir des boucles correctes a fait de la boucle un objet de conception. Elle a réuni les schémas (compteur, accumulateur, maximum et minimum, sentinelle et drapeau), chacun défini par ce que sa variable signifie après chaque itération. Elle a défini l’invariant, une affirmation qui est vraie chaque fois que l’on évalue la condition, avec ses trois obligations : initialisation, conservation et conclusion, qui, jointe à la condition fausse, donne la postcondition ; et elle l’a reconnu comme une récurrence sur le nombre d’itérations. Elle a appris à concevoir à rebours, de la postcondition à l’invariant et de l’invariant au corps. Elle a justifié la terminaison par le variant, et a montré trois boucles dans lesquelles l’arithmétique de C++ l’invalide : celle sur des réels qui saute 1.0, le compteur non signé qui fait le tour et le compteur signé qui déborde. Elle a donné, enfin, un premier contact avec le débogueur.

Algorithmes numériques

La leçon Algorithmes numériques a appliqué ce qui précède à quatre algorithmes classiques, écrits dans main et démontrés. La primalité par divisions successives par essai, avec la proposition selon laquelle il suffit d’aller jusqu’à $\sqrt{n}$ et avec la condition d <= n / d, qui ne déborde pas là où d * d <= n déborde. L’algorithme d’Euclide, avec l’invariant $\operatorname{pgcd}(a, b) = \operatorname{pgcd}(a_0, b_0)$ et le variant $b$, et ses deux dangers en C++ : le résultat strictement négatif et la division par zéro si la condition est évaluée après le corps. Le changement de base par divisions successives et le schéma de Horner, qui évalue un polynôme avec une multiplication par coefficient. Et la dichotomie, garantie par le théorème des valeurs intermédiaires et gouvernée par un compteur entier dont le nombre d’itérations se calcule à l’avance.