Exercices corrigés de NSI Première : algorithmique, preuve et coût

La somme vaut $12+7+25+7+19+3+25+14=112$, et le tableau compte $8$ cases, donc la moyenne vaut $112/8=14$ connexions par heure. Le schéma est celui de l'ACCUMULATEUR : une variable initialisée à la valeur neutre de l'opération, ici $0$ pour une addition, mise à jour à chaque case. Vérification rapide : la plus petite valeur vaut $3$ et la plus grande $25$, donc la moyenne doit tomber entre les deux, ce qui est le cas. Une moyenne hors des bornes signale toujours une erreur de somme ou un mauvais diviseur.

Les valeurs strictement supérieures à $13$ sont $25$, $19$, $25$ et $14$, donc la fonction renvoie $4$. C'est le schéma du COMPTEUR, un accumulateur dont la mise à jour est conditionnelle : on part de $0$ et on ajoute $1$ quand le test réussit. Le piège habituel est d'écrire $c = 1$ à l'initialisation, ce qui compte une case qui n'existe pas, ou d'écrire $c = c + v$ au lieu de $c = c + 1$, ce qui répond à une autre question. La valeur $14$ compte, car le test est strict dans le sens attendu ; si l'énoncé avait dit « au moins $13$ », il aurait fallu $>=$.

Le $else$ est DANS la boucle. Au tout premier tour, $v$ vaut $12$ ; le test $v == 7$ échoue, on passe au $else$, et le $return False$ termine la fonction avant même d'avoir regardé la deuxième case. La fonction ne décide donc jamais que sur $t[0]$. Elle répond juste par accident dans deux cas : quand $x$ vaut $12$, où elle renvoie $True$ à raison, et quand $x$ est absent du tableau, où $False$ est la bonne réponse. Elle se trompe sur les cinq autres valeurs présentes, $7$, $25$, $19$, $3$ et $14$. La correction tient en un décalage : le $return False$ doit sortir de la boucle et se placer APRÈS elle, sans $else$. C'est la règle du schéma d'EXISTENCE : on ne peut conclure « non » qu'une fois toutes les cases vues, alors qu'on peut conclure « oui » dès la première qui convient. Une réponse trop tôt vaut zéro à la question, car la fonction rend un résultat faux sans lever la moindre erreur.

On parcourt les INDICES et non les valeurs, puisque c'est un indice qu'on doit rendre : $for\ i\ in\ range(len(t))$, et si $t[i] == x$ alors $return\ i$. Après la boucle, et seulement après, $return\ -1$. La valeur $7$ apparaît aux indices $1$ et $3$ ; le premier $return$ rencontré est celui de l'indice $1$, donc la fonction renvoie $1$. La valeur $25$ apparaît aux indices $2$ et $6$, donc elle renvoie $2$. La valeur $5$ est absente, donc $-1$. Le choix de $-1$ comme code d'absence tient à ce qu'aucun indice valide n'est négatif : rendre $0$ serait ambigu, puisque $0$ est un indice parfaitement légitime.

Les valeurs strictement supérieures à $8$ sont $11$, $15$, $9$ et $11$, donc la fonction renvoie $4$. L'invariant s'écrit : « avant chaque tour, $c$ est égal au nombre d'indices $j$ vérifiant $j < i$ et $t[j] > seuil$, et $i$ reste compris entre $0$ et $len(t)$ ». La deuxième moitié de la phrase n'est pas un ornement : c'est elle qui garantit que l'accès $t[i]$ est légal. Un invariant qui ne dit rien sur les bornes ne prouve rien sur les débordements.

INITIALISATION : avant le premier tour, $i$ vaut $0$ et $c$ vaut $0$ ; il n'existe aucun indice $j < 0$, donc le compte attendu est bien $0$. L'invariant est vrai. CONSERVATION : supposons-le vrai avec la valeur $i$. Le tour examine exactement la case $t[i]$ et ajoute $1$ à $c$ si et seulement si $t[i] > seuil$, puis fait passer $i$ à $i+1$. Le compte des indices $j < i+1$ est donc le compte des indices $j < i$ augmenté de ce même $1$ conditionnel : l'invariant est encore vrai. SORTIE : la boucle s'arrête quand $i$ n'est plus strictement inférieur à $len(t)$, donc quand $i = len(t)$ ; l'invariant dit alors que $c$ compte tous les indices du tableau, ce qui est exactement le résultat demandé. Les trois points doivent être écrits séparément : deux sur trois ne prouvent rien.

Le variant est $len(t) - i$. C'est un entier, il est positif ou nul tant que la boucle tourne puisque $i < len(t)$, et chaque tour fait croître $i$ de $1$, donc il décroît strictement de $1$. Un entier positif qui décroît strictement ne peut pas décroître indéfiniment : la boucle s'arrête, après exactement $7$ tours ici. À la sortie il vaut $0$. Attention à ne pas confondre variant et invariant : le variant DÉCROÎT et prouve l'arrêt, l'invariant NE CHANGE PAS et prouve le résultat.

Premier camarade : l'INITIALISATION tombe. Avant le premier tour, $c$ vaut $1$ alors qu'aucune case n'a été examinée ; les deux autres points restent valables, donc l'erreur se propage telle quelle jusqu'à la sortie et la fonction renvoie $5$ au lieu de $4$. C'est la faute la plus discrète du chapitre, parce que le programme s'exécute sans broncher. Deuxième camarade : la TERMINAISON tombe. Avec $i = i + 1$ dans le $if$, le compteur d'indice n'avance que lorsque la condition est vraie ; ici $t[0] = 4$ n'est pas supérieur à $8$, donc $i$ reste à $0$ et la boucle tourne indéfiniment. Le variant $len(t) - i$ ne décroît plus, et c'est précisément ce que le variant sert à détecter. Troisième camarade : l'invariant garantissait $i \le len(t)$ au moment de l'accès, mais la condition $i <= len(t)$ autorise un tour de trop ; à $i = len(t) = 7$, l'accès $t[7]$ sort du tableau et le programme s'arrête sur une erreur d'indice. Des trois, c'est la moins grave, parce qu'elle se voit tout de suite.

Premier tour, $i = 0$ : le minimum de tout le tableau est $4$, en case $4$ ; on l'échange avec la case $0$, ce qui donne $[4, 8, 41, 15, 23, 16]$. Deuxième tour, $i = 1$ : le minimum du reste est $8$, déjà en case $1$ ; l'échange se fait avec elle-même et le tableau ne bouge pas. Troisième tour, $i = 2$ : le minimum du reste est $15$, en case $3$ ; on obtient $[4, 8, 15, 41, 23, 16]$. Les deux derniers tours amènent $16$ puis laissent $23$ en place, et le tableau final est $[4, 8, 15, 16, 23, 41]$. Vérification : la somme des six valeurs vaut $107$ avant comme après, puisqu'un tri ne fait que déplacer des valeurs. Une somme qui change signale une valeur écrasée, faute classique quand on remplace l'échange par deux affectations.

L'invariant : « après $i$ tours, les $i$ premières cases contiennent les $i$ plus petits éléments du tableau, rangés en ordre croissant, et elles ne seront plus modifiées ». La boucle s'arrête à $n - 1$ parce qu'après $n - 1$ tours l'invariant dit déjà que les $n - 1$ premières cases portent les $n - 1$ plus petits éléments en ordre : la dernière case ne peut donc contenir que le plus grand, et un tour de plus chercherait le minimum d'un reste réduit à une seule case. Écrire $range(n)$ ne change donc pas le résultat, cela ajoute seulement un tour qui échange une case avec elle-même. Ce n'est pas une faute, c'est une ligne pour rien, et le correcteur attend que l'on sache dire pourquoi.

Avec $m = 0$, la recherche du minimum repart toujours de la case $0$, qui est déjà définitive. Au deuxième tour, $i$ vaut $1$ et $m$ vaut $0$ ; la boucle interne compare $t[j]$ à $t[0] = 4$ pour $j$ allant de $2$ à $5$, et aucune de ces valeurs n'est inférieure à $4$, donc $m$ reste $0$. L'échange final porte alors sur les cases $1$ et $0$ et produit $[8, 4, 41, 15, 23, 16]$ : la case $0$, que l'invariant déclarait définitive, vient d'être modifiée. C'est exactement la clause « elles ne seront plus modifiées » qui tombe, et le tableau final n'est pas trié. L'erreur est fatale et silencieuse, ce qui en fait la plus coûteuse du chapitre : la fonction rend un tableau d'allure plausible.

L'énoncé est VRAI : si les $i$ premières cases contiennent les $i$ plus petits éléments en ordre croissant, alors elles sont bien triées entre elles. Mais il ne permet pas de conclure. À la sortie, avec $i = n - 1 = 5$, il affirme seulement que les cinq premières cases sont ordonnées, sans rien dire de la sixième ni du lien entre les deux parties. Le tableau $[1, 2, 3, 4, 5, 0]$ le vérifie et n'est pourtant pas trié. Tout l'intérêt de l'invariant fort tient dans les trois mots « les $i$ plus petits » : ce sont eux qui interdisent qu'une valeur plus petite traîne dans le reste. La leçon vaut pour tout le chapitre : un invariant peut être vrai et inutile, et le seul test qui compte est de vérifier qu'il DONNE le résultat voulu quand la boucle s'arrête.

Tour $i = 1$ : $v = 4$, on compare $t[0] = 9$ à $4$, le décalage a lieu, $j$ passe à $-1$ et la boucle s'arrête sur la première condition ; on pose $4$ en case $0$, d'où $[4, 9, 7, 2, 6]$, avec $1$ évaluation du test. Tour $i = 2$ : $v = 7$, on décale $9$, puis $t[0] = 4$ n'est pas supérieur à $7$ et l'on s'arrête ; $[4, 7, 9, 2, 6]$, $2$ évaluations. Tour $i = 3$ : $v = 2$, les trois valeurs $9$, $7$ et $4$ sont décalées et $j$ tombe à $-1$ ; $[2, 4, 7, 9, 6]$, $3$ évaluations. Tour $i = 4$ : $v = 6$, on décale $9$ puis $7$, et $4$ arrête la boucle ; $[2, 4, 6, 7, 9]$, $3$ évaluations. Total : $1 + 2 + 3 + 3 = 9$. Contrôle : la somme vaut $28$ avant et après.

La boucle $while$ ne s'arrête qu'APRÈS avoir décrémenté $j$ une fois de trop : soit parce que $j$ est devenu $-1$, soit parce que $t[j]$ n'est plus supérieur à $v$ et que la case $j$ doit rester où elle est. Dans les deux cas, la case libre est celle d'indice $j + 1$, la dernière d'où l'on a décalé une valeur. Écrire $t[j] = v$ pose la valeur une case trop à gauche, et écrase une valeur qui, elle, était bien placée. Au premier tour, $v$ vaut $4$, le décalage donne $[9, 9, 7, 2, 6]$ et $j$ vaut $-1$ ; l'affectation $t[-1] = 4$ ne lève aucune erreur en Python, puisque l'indice $-1$ désigne la DERNIÈRE case : le tableau devient $[9, 9, 7, 2, 4]$. Deux valeurs sont détruites d'un coup, et aucune exception ne prévient. C'est le meilleur argument pour écrire un jeu de tests plutôt que de se fier à l'absence de message d'erreur.

Le variant est $j + 1$. C'est un entier, il vaut au moins $0$ tant que la boucle tourne puisque la condition impose $j \ge 0$, et chaque tour fait décroître $j$ de $1$, donc le variant décroît strictement. Il ne peut donc pas décroître indéfiniment, et la boucle s'arrête : au pire quand le variant atteint $0$, c'est-à-dire $j = -1$, c'est-à-dire quand la valeur mise de côté est plus petite que toutes les précédentes. On choisit $j + 1$ plutôt que $j$ pour que le variant reste positif ou nul, ce qui est la forme attendue dans une preuve de terminaison.

Sans la mise de côté, la valeur à insérer n'existe plus qu'à un seul endroit : la case $t[i]$ elle-même. Or la toute première itération du $while$ écrit $t[j + 1] = t[j]$ avec $j + 1 = i$ : elle écrase précisément cette case. Au premier tour, $i$ vaut $1$ et $t[1] = 4$ ; le décalage écrit $t[1] = t[0] = 9$, donc $t[i]$ vaut maintenant $9$. La condition $t[j] > t[i]$ devient $9 > 9$, fausse, et la boucle s'arrête ; l'affectation finale $t[j + 1] = t[i]$ recopie $9$ sur lui-même. Le tableau devient $[9, 9, 7, 2, 6]$ et la valeur $4$ a disparu. La ligne $v = t[i]$ n'est donc pas une commodité de lecture : c'est la sauvegarde sans laquelle l'algorithme détruit sa propre donnée. C'est pour la même raison qu'on écrit l'échange du tri par sélection en une seule instruction, plutôt qu'en deux affectations successives.

Programme $A$ : $0{,}8$ puis $0{,}8$ puis $0{,}9$ puis $0{,}8$, donc un rapport voisin de $1$ à chaque doublement. Le temps ne dépend pas de $n$ : coût CONSTANT, et les petits écarts sont du bruit de mesure. Programme $B$ : $3{,}1/1{,}5 \approx 2{,}07$, puis $6{,}2/3{,}1 = 2$, puis $12{,}3/6{,}2 \approx 1{,}98$. Le rapport vaut $2$ : coût LINÉAIRE, le temps est proportionnel à $n$. Programme $C$ : $97/24 \approx 4{,}04$, puis $389/97 \approx 4{,}01$, puis $1\,554/389 \approx 3{,}99$. Le rapport vaut $4$ : coût QUADRATIQUE, car doubler $n$ multiplie $n^{2}$ par $4$. Le rapport est l'outil, pas la différence : une différence de temps ne distingue pas les trois cas.

Pour $B$, chaque doublement multiplie par $2$ : $12{,}3 \times 2 = 24{,}6$ ms à $16\,000$, puis $24{,}6 \times 2 \times 2 = 98{,}4$ ms à $64\,000$, deux doublements plus loin. Pour $C$, chaque doublement multiplie par $4$ : $1\,554 \times 4 = 6\,216$ ms à $16\,000$, puis $6\,216 \times 16 = 99\,456$ ms à $64\,000$, soit environ $99{,}5$ secondes. On passe donc de moins de deux secondes à plus d'une minute et demie pour huit fois plus de données. Le piège est de multiplier par $8$ au lieu de $4 \times 4$ : trois doublements se traduisent par $2^{3}$ pour un linéaire et par $4^{3}$ pour un quadratique, jamais par la même valeur.

De $12{,}0$ à $13{,}4$, puis à $14{,}8$, puis à $16{,}2$ : le temps augmente de $1{,}4$ milliseconde à chaque doublement, et non d'un facteur. Une quantité qui gagne une constante quand $n$ double est proportionnelle au nombre de doublements, c'est-à-dire à $\log_{2} n$ : c'est la signature du coût LOGARITHMIQUE, celui de la recherche dichotomique. De $8\,000$ à $64\,000$ il y a trois doublements, donc $16{,}2 + 3 \times 1{,}4 = 20{,}4$ ms. La leçon est qu'un coût logarithmique est pratiquement insensible à la taille : multiplier les données par huit coûte ici un quart de milliseconde de plus par doublement.

À $n = 64\,000$, le rapport vaut $99\,456/98{,}4 \approx 1\,011$. Il était de $16$ à $n = 1\,000$ : il a été multiplié par plus de soixante en passant d'une taille à l'autre. Une mesure faite à une seule taille ne dit donc RIEN du coût, elle ne donne qu'un point ; c'est la façon dont le temps ÉVOLUE qui caractérise l'algorithme. C'est aussi pourquoi un programme quadratique peut paraître acceptable pendant toute la phase de mise au point, sur des jeux de test réduits, et devenir inutilisable le jour de la mise en service. Le réflexe attendu en évaluation est de toujours chronométrer au moins trois tailles qui doublent.

Recherche de $67$ : premier tour, $g = 0$, $d = 9$, $m = 4$, et $t[4] = 31 < 67$, donc $g = 5$ ; deuxième tour, $g = 5$, $d = 9$, $m = 7$, et $t[7] = 67$, on renvoie $7$. Deux tours. Recherche de $20$ : $m = 4$ et $31 > 20$ donne $d = 3$ ; puis $g = 0$, $d = 3$, $m = 1$ et $11 < 20$ donne $g = 2$ ; puis $m = 2$ et $18 < 20$ donne $g = 3$ ; puis $g = d = 3$, $m = 3$ et $24 > 20$ donne $d = 2$ ; la condition $g \le d$ est alors fausse et l'on renvoie $-1$. Quatre tours. Chaque tour divise par deux le nombre de cases encore possibles, donc le nombre maximal de tours est le nombre de fois où l'on peut diviser $n$ par deux, plus un : pour $n = 10$ cela fait $4$, et pour $n = 1\,000$ cela fait $10$, puisque $2^{9} = 512 < 1\,000 \le 1\,024 = 2^{10}$. Dix comparaisons pour mille cases, contre mille pour un parcours séquentiel.

Avec $while\ g < d$, la boucle s'arrête dès que $g$ et $d$ deviennent égaux, c'est-à-dire quand il ne reste plus qu'une seule case à examiner, et cette case n'est jamais testée. Recherche de $3$ : $m = 4$ et $31 > 3$ donne $d = 3$ ; puis $g = 0$, $d = 3$, $m = 1$ et $11 > 3$ donne $d = 0$ ; alors $g = d = 0$, la condition est fausse, et la fonction renvoie $-1$ alors que $3$ occupe la case $0$. La version manque donc toujours une valeur qui se trouve seule dans le dernier intervalle, ce qui arrive très souvent. L'erreur est particulièrement vicieuse parce que la fonction reste juste pour beaucoup de valeurs, celles trouvées avant le rétrécissement final : un test sur deux ou trois exemples bien choisis ne la révèle pas.

Avec $g = m$, l'intervalle ne rétrécit plus toujours. Recherche de $88$ : $m = 4$ et $31 < 88$ donne $g = 4$ ; $m = (4+9)//2 = 6$ et $55 < 88$ donne $g = 6$ ; $m = 7$ et $67 < 88$ donne $g = 7$ ; $m = 8$ et $70 < 88$ donne $g = 8$ ; $m = (8+9)//2 = 8$ à nouveau, et $g$ reste $8$. À partir de là, $g$, $d$ et $m$ ne bougent plus et la boucle tourne indéfiniment. La question sans réponse est celle de la TERMINAISON : le variant $d - g$ ne décroît plus, parce que la division entière fait retomber $m$ sur $g$ dès que $d = g + 1$. Le $+1$ n'est donc pas un ajustement cosmétique : il exclut la case déjà examinée et garantit la décroissance stricte. Noter que cette version donne le bon résultat pour $31$ et pour $67$ : elle passe les premiers tests et se bloque sur le dernier élément.

$dicho(u, 55)$ renvoie $2$, parce que $u[2]$ vaut justement $55$ et que la toute première comparaison tombe dessus : la réponse est juste par hasard, pas par raisonnement. $dicho(u, 18)$, lui, compare $55$ à $18$, conclut qu'il faut chercher à gauche, ramène $d$ à $1$, compare $u[0] = 31$ à $18$, ramène $d$ à $-1$ et renvoie $-1$, alors que $18$ occupe la case $3$. Ce cas est plus dangereux que les deux précédents parce que le code est CORRECT : c'est sa PRÉCONDITION qui est violée, et rien dans le langage ne la vérifie. Il n'y a ni exception, ni boucle infinie, ni message : seulement une réponse fausse, rendue vite et avec aplomb. C'est la raison d'être de la spécification, et l'exercice $10$ chiffre ce que coûte de la vérifier.

Le glouton prend d'abord $10$, il reste $4$ ; il essaie $7$, qui ne tient pas ; il prend quatre fois $1$. Total : $10 + 1 + 1 + 1 + 1$, soit CINQ jetons. La meilleure solution est $7 + 7$, soit DEUX jetons. Le glouton donne donc une solution valide, la somme est exacte, mais pas la meilleure : en prenant le plus gros jeton il s'est interdit la combinaison qui tombait juste. C'est le contre-exemple à connaître, et il suffit d'un seul pour réfuter « le glouton est toujours optimal ». Remarquer que l'algorithme ne se trompe pas au sens où il rendrait une mauvaise somme : il rend $14$, il le rend mal.

Dans l'ordre croissant, la boucle $while$ épuise d'abord les jetons de $1$ : elle en prend quatorze, le reste tombe à $0$, et les valeurs $7$ et $10$ ne servent jamais. QUATORZE jetons. Le tri décroissant est donc indispensable au principe même du glouton, qui est de prendre le plus gros choix disponible : sans lui, l'algorithme n'est plus glouton, il est simplement mauvais. Mais il ne suffit pas, et la question a le prouve : la liste $[10, 7, 1]$ était bien triée, et le résultat n'était pas optimal. Ordre décroissant et optimalité sont deux choses différentes, et les confondre est l'erreur la plus fréquente sur ce chapitre.

Le glouton prend $50$, il reste $37$ ; puis $20$, il reste $17$ ; puis $10$, il reste $7$ ; puis $5$, il reste $2$ ; puis $2$, il reste $0$. Cinq pièces : $50 + 20 + 10 + 5 + 2 = 87$. Ici aucune combinaison ne fait mieux. Ce qui distingue ce système, c'est que chaque valeur vaut au moins le double de la précédente, si bien qu'on ne peut jamais remplacer une grosse pièce par un petit nombre de plus petites : on dit que le système est canonique. Le système $[10, 7, 1]$ ne l'est pas, puisque deux jetons de $7$ dépassent un jeton de $10$. Retenir la formulation honnête : le glouton du rendu de monnaie est optimal SUR CERTAINS systèmes, et l'énoncé doit dire lequel avant qu'on affirme quoi que ce soit.

Le plus petit d'abord : $8$, puis $13$, puis $21$, puis $34$, ce qui fait $76$ mégaoctets ; le suivant, $40$, porterait le total à $116$ et ne tient pas. Résultat : QUATRE fichiers, $76$ mégaoctets. Le plus grand d'abord : $55$, puis $40$, ce qui fait $95$ ; aucun des quatre restants ne tient dans les cinq mégaoctets libres. Résultat : DEUX fichiers, $95$ mégaoctets. Chacun est optimal pour le critère qui l'a inspiré, le premier pour le NOMBRE de fichiers, le second pour l'ESPACE occupé, et aucun des deux n'atteint le meilleur remplissage, $97$ mégaoctets, que donne la combinaison $55 + 21 + 13 + 8$. La conclusion du chapitre tient en deux phrases. Un glouton se juge toujours par rapport à un critère annoncé, jamais dans l'absolu. Et on l'utilise malgré ses échecs parce qu'il coûte un seul parcours, là où examiner toutes les combinaisons coûterait $2^{6} = 64$ essais ici, et $2^{60}$, soit plus d'un milliard de milliards, pour soixante fichiers.