NSI Première à Montréal • Algorithmique

Fiche de révision : algorithmique, preuve et coût (NSI Première)

Cette fiche de révision accompagne le chapitre d'algorithmique du programme de NSI de première : parcours séquentiel, recherche dichotomique, tris par sélection et par insertion, algorithmes gloutons, coût constant, linéaire et quadratique, preuve de correction par un invariant et preuve de terminaison par un variant.

Elle ne redit pas le cours. Elle dit ce qui coûte des points en évaluation, ce que le correcteur attend exactement, et les contrôles à faire avant de rendre la copie.

Le fil du chapitre

Un algorithme qui tourne sur l'exemple du cours n'a RIEN prouvé. Trois questions se posent à chaque fois, et l'évaluation les pose toutes les trois : est-ce juste, et l'invariant le démontre-t-il ; est-ce que ça s'arrête, et quel variant décroît ; combien ça coûte, compté et non annoncé.

Ce chapitre fait partie de NSI en Première

Avant ce chapitre

Cette fiche suppose ces notions acquises. Si une méthode ci-dessous reste opaque, c'est presque toujours l'une d'elles qui manque, pas la fiche.

Python : types, contrôle, fonctions et tableaux Fiche

Remonter plus loin : la chaîne complète (4 chapitres) ↓

Le chemin de remédiation, du plus ancien au plus proche. Un élève qui reprend ce chapitre de zéro le reprend dans cet ordre.

1Algorithmique et PythonSeconde, Mathématiques
2Python : types, contrôle, fonctions et tableaux
3Algorithmique et ScratchQuatrième, Mathématiques
4Algorithmique et ScratchTroisième, Mathématiques

L'essentiel

Les trois questions, et l'outil de chacune

• EST-CE JUSTE ? L'outil est l'INVARIANT de boucle : une propriété vraie avant chaque tour et encore vraie après. On la vérifie en trois points, et les trois s'écrivent.
• EST-CE QUE ÇA S'ARRÊTE ? L'outil est le VARIANT : un entier positif ou nul qui décroît STRICTEMENT à chaque tour. Un entier positif ne peut pas décroître indéfiniment.
• COMBIEN ÇA COÛTE ? On COMPTE les opérations, on ne les annonce pas. Un coût se donne en fonction de la taille $n$ des données, jamais en secondes.
• Des tests ne répondent à aucune des trois. Ils peuvent RÉFUTER, avec un contre-exemple, jamais DÉMONTRER : une version fausse de la dichotomie peut passer trois essais et boucler sur le quatrième.

L'invariant : la phrase, puis les trois points

• INITIALISATION : l'invariant est vrai avant le premier tour, quand aucune case n'a encore été examinée. C'est là que se logent les erreurs de valeur de départ.
• CONSERVATION : si l'invariant est vrai avant un tour, il l'est encore après. On raisonne sur UN tour quelconque, jamais sur le premier.
• SORTIE : la boucle s'arrête, et l'invariant DIT alors le résultat voulu. C'est ce troisième point que l'on oublie, et c'est lui qui distingue un invariant utile d'un invariant vrai.
• L'invariant sert aussi de diagnostic : quand un programme se trompe, le point qui tombe dit OÙ est la faute. Valeur de départ fausse, c'est l'initialisation ; mise à jour décalée, c'est la conservation ; borne de boucle fausse, c'est la sortie.

En haut, les trois cases définitives portent les trois PLUS PETITS éléments ; en bas, un tableau dont les cinq premières cases sont triées entre elles sans que le tableau le soit.

Les cinq algorithmes du programme et leur coût

• PARCOURS SÉQUENTIEL : un tour par case, coût LINÉAIRE. Le résultat se rend après la boucle ; seul le test d'existence peut conclure « oui » en cours de route.
• RECHERCHE DICHOTOMIQUE, sur un tableau TRIÉ : au plus $\lfloor\log_{2}n\rfloor+1$ tours, coût LOGARITHMIQUE. Dix comparaisons pour mille cases.
• TRI PAR SÉLECTION : $\dfrac{n(n-1)}{2}$ comparaisons, coût QUADRATIQUE, et ce nombre ne dépend pas du contenu du tableau.
• TRI PAR INSERTION : coût QUADRATIQUE au pire, mais seulement $n-1$ comparaisons sur un tableau déjà rangé. C'est le seul des deux tris dont le coût dépend des données.
• ALGORITHME GLOUTON : un seul parcours, coût LINÉAIRE une fois les valeurs rangées. Rapide, et optimal seulement dans certains cas.

Reconnaître un coût : le test du doublement

• On double $n$ et l'on regarde le RAPPORT de deux temps consécutifs, jamais leur différence.
• Rapport $1$ : coût CONSTANT. Rapport $2$ : coût LINÉAIRE. Rapport $4$ : coût QUADRATIQUE, puisque doubler $n$ multiplie $n^{2}$ par quatre.
• Un temps qui GAGNE UNE CONSTANTE à chaque doublement, au lieu d'être multiplié, est LOGARITHMIQUE : c'est la signature de la dichotomie.
• Une mesure faite à une seule taille ne dit rien : c'est l'ÉVOLUTION du temps qui caractérise l'algorithme, pas sa valeur.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Prouver par des essais

toute la question de justification, souvent 3 à 4 points

Ce qu'il ne faut pas écrire

« Je l'ai testé sur trois exemples, il marche »

Ce qu'il faut écrire

Un invariant pour le résultat, un variant pour l'arrêt

Pourquoi : Des tests ne peuvent que réfuter. La version de la dichotomie qui écrit $g = m$ au lieu de $g = m + 1$ trouve correctement la valeur du milieu et celle des deux tiers du tableau, puis boucle indéfiniment sur la dernière : trois essais bien choisis l'auraient validée. Le correcteur attend une preuve, et il la lit en trois points.

2. Écrire un invariant vrai qui ne conclut pas

la totalité de la preuve, alors que l'énoncé écrit est exact

Ce qu'il ne faut pas écrire

« Après i tours, les i premières cases sont triées entre elles »

Ce qu'il faut écrire

« ... contiennent les i PLUS PETITS éléments, en ordre, et ne bougeront plus »

Pourquoi : Le premier énoncé est parfaitement vrai et ne sert à rien : le tableau $[1, 2, 3, 4, 5, 0]$ le vérifie à la sortie sans être trié. Ce sont les mots « les i plus petits » qui interdisent qu'une valeur plus petite traîne dans le reste. Test à faire systématiquement : l'invariant, appliqué à la sortie, donne-t-il le résultat demandé ?

3. Confondre variant et invariant

1 à 2 points, et la preuve de terminaison ne vaut rien

Ce qu'il ne faut pas écrire

« Le variant est l'indice i, qui avance à chaque tour »

Ce qu'il faut écrire

Le variant DÉCROÎT : c'est $len(t) - i$ , pas $i$

Pourquoi : Une quantité qui croît peut croître indéfiniment, elle ne prouve donc aucun arrêt. C'est un entier POSITIF qui DÉCROÎT strictement qu'il faut exhiber, parce qu'une telle suite ne peut pas continuer sans fin. Moyen mnémotechnique : le variant VARIE et fait finir, l'invariant NE VARIE PAS et fait conclure.

4. Lancer la dichotomie sur un tableau non trié

toute la question, et en situation réelle une panne invisible

Ce qu'il ne faut pas écrire

« Elle sera juste moins efficace »

Ce qu'il faut écrire

Elle rend des réponses FAUSSES, sans la moindre erreur

La comparaison au milieu envoie chercher

18

à gauche, alors qu'il est en case

3

: le tableau n'étant pas trié, la déduction est fausse et rien ne le signale.

Pourquoi : Sur $[31, 3, 55, 18, 70, 11]$ , la dichotomie affirme que $18$ est absent alors qu'il occupe la case $3$ . Aucune exception, aucun message : le tri est une PRÉCONDITION, c'est-à-dire une condition dont la fonction a besoin et qu'elle ne vérifie pas. Elle s'écrit dans la spécification et se contrôle par une assertion.

5. Annoncer un coût au lieu de le compter

2 points, et la justification attendue est justement le compte

Ce qu'il ne faut pas écrire

« Il y a deux boucles imbriquées, donc c'est quadratique »

Ce qu'il faut écrire

Compter les tours de la boucle interne, qui dépendent souvent de i

Le rapport de deux temps consécutifs, quand la taille double, vaut un, deux ou quatre.

Pourquoi : Deux boucles imbriquées ne donnent pas toujours $n^{2}$ : dans le tri par sélection, la boucle interne fait $n-1-i$ tours et non $n$ , et le total vaut $\dfrac{n(n-1)}{2}$ , c'est-à-dire la moitié. Le résultat reste quadratique, mais c'est le compte qui le démontre, et c'est lui qui est demandé.

6. Écrire une taille en dur

toute la question, et un résultat faux qui ne lève aucune erreur

Ce qu'il ne faut pas écrire

$return\ s / 10$

Ce qu'il faut écrire

$return\ s / len(notes)$

Pourquoi : La constante était vraie le jour où le programme a été écrit. Le jour où une donnée manque, la fonction divise neuf valeurs par dix et affiche $10{,}7$ au lieu de $11{,}89$ , sans rien signaler. Une dimension de données se lit toujours sur les données elles-mêmes.

7. Placer le return False dans la boucle

toute la fonction, qui ne décide plus que sur la première case

Ce qu'il ne faut pas écrire

$if\ v == x:\ return\ True\ else:\ return\ False$

Ce qu'il faut écrire

Le $return\ False$ va APRÈS la boucle, sans $else$

Pourquoi : On peut conclure « oui, la valeur est là » dès la première case qui convient, mais on ne peut conclure « non, elle n'y est pas » qu'après les avoir TOUTES vues. Avec le $else$ , la boucle ne fait jamais deux tours et la fonction répond juste par accident, quand la valeur cherchée est la première ou qu'elle est absente.

8. Affirmer qu'un glouton est optimal

1 à 3 points, la question portant justement sur la limite

Ce qu'il ne faut pas écrire

« Le rendu de monnaie glouton donne toujours le minimum de pièces »

Ce qu'il faut écrire

Optimal sur certains systèmes seulement, et un contre-exemple suffit

Pourquoi : Avec des jetons de $10$ , $7$ et $1$ , le glouton rend $14$ en cinq jetons, $10+1+1+1+1$ , quand $7+7$ en donne deux. Le tri décroissant des valeurs est nécessaire au principe, il ne suffit pas à l'optimalité. On utilise le glouton pour son COÛT, un seul parcours, là où examiner toutes les combinaisons de soixante objets demanderait $2^{60}$ essais.

Quelle méthode choisir

Quel algorithme de recherche, selon le tableau

Un tableau de n valeurs, une valeur à trouver

Si Le tableau est trié, et il le reste → Dichotomie, au plus $\lfloor\log_{2}n\rfloor+1$ comparaisons

Exemple : $40\,000$ références rangées : $16$ comparaisons par recherche
Si Le tableau n'est pas trié et l'on cherche une seule fois → Parcours séquentiel, $n$ comparaisons au pire

Exemple : Trier coûterait bien plus cher que la recherche elle-même
Si Le tableau n'est pas trié mais on cherchera très souvent → Trier une fois, puis dichotomie à chaque recherche

Exemple : Le tri se paie une fois, le gain se répète à chaque recherche
Si On ne sait pas si le tableau est trié → Vérifier UNE FOIS au chargement, coût linéaire, puis dichotomie

Exemple : $39\,999 + 3\,000\times 16 = 87\,999$ comparaisons pour la journée

La quatrième branche est celle qu'on oublie. Vérifier avant CHAQUE recherche coûterait ici $3\,000\times 39\,999$ comparaisons, soit plus de mille fois le prix d'une seule vérification au chargement : une garantie se place là où la donnée CHANGE, pas là où on la consulte.

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Rédiger une preuve de correction par invariant

Quand l'utiliser : Chaque fois qu'un énoncé demande de justifier qu'un algorithme est correct

1 Écrire l'invariant en UNE phrase, qui relie la variable de résultat à la variable de boucle.
2 Vérifier l'INITIALISATION : donner les valeurs avant le premier tour et dire pourquoi la phrase est vraie.
3 Vérifier la CONSERVATION : supposer la phrase vraie avant un tour quelconque, dire ce que le tour fait, conclure qu'elle l'est encore.
4 Vérifier la SORTIE : dire pour quelle valeur la boucle s'arrête, puis ce que l'invariant affirme alors.
5 Conclure explicitement que c'est le résultat demandé.
6 Ajouter le VARIANT et sa décroissance, sans quoi la preuve ne vaut que pour une boucle dont on ignore si elle finit.

Phrase de conclusion

« Invariant : avant chaque tour, $c$ est le nombre d'indices $j < i$ tels que $t[j] > seuil$ . Avant le premier tour, $i = 0$ et $c = 0$ : aucun indice ne convient, la phrase est vraie. Si elle est vraie avant un tour, ce tour examine la seule case $t[i]$ et ajoute $1$ à $c$ exactement quand $t[i] > seuil$ , puis fait passer $i$ à $i+1$ : elle est encore vraie. La boucle s'arrête quand $i = len(t)$ , et l'invariant dit alors que $c$ compte tous les indices du tableau, ce qui est le résultat voulu. Variant : $len(t)-i$ , entier positif qui décroît de $1$ par tour, donc la boucle s'arrête. »

Le piège : Raisonner sur le premier tour plutôt que sur un tour quelconque. La conservation se démontre une fois pour toutes, en supposant l'invariant vrai avant un tour dont on ne dit rien de plus.

Barème : 1 point pour l'invariant écrit en une phrase exploitable, 1 point pour l'initialisation, 2 points pour la conservation, 1 point pour la sortie et la conclusion explicite, 1 point pour le variant et sa décroissance stricte. Une preuve à deux points sur trois ne démontre rien et plafonne à la moitié.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

L'invariant, appliqué à la sortie, donne-t-il le résultat ?

On remplace la variable de boucle par sa valeur de sortie et l'on lit ce que la phrase affirme. Si elle n'affirme pas exactement ce que la fonction doit rendre, l'invariant est trop faible.

« Les $i$ premières cases sont triées entre elles » donne, pour $i = n-1$ , une phrase que $[1, 2, 3, 4, 5, 0]$ vérifie sans être trié : invariant trop faible.
Le variant décroît-il STRICTEMENT ?

On écrit sa valeur avant et après un tour. S'il peut rester égal, même dans un seul cas, la boucle peut tourner indéfiniment.

Avec $g = m$ , dès que $d = g+1$ la division entière fait retomber $m$ sur $g$ : le variant $d-g$ ne bouge plus.
La somme du tableau est-elle conservée après un tri ?

Un tri déplace des valeurs, il n'en crée ni n'en détruit. Une somme qui change signale une valeur écrasée, faute classique quand un échange est écrit en deux affectations.

$[23, 8, 41, 15, 4, 16]$ et $[4, 8, 15, 16, 23, 41]$ ont la même somme, $107$ .
Le rapport de deux temps, et non leur différence

Sur un tableau de mesures, on divise chaque temps par le précédent après doublement de $n$ . Une différence ne distingue pas les trois coûts, un rapport les sépare immédiatement.

$97/24 \approx 4{,}04$ puis $389/97 \approx 4{,}01$ : coût quadratique, sans hésitation possible.

L'exercice type décortiqué

Une preuve complète, sur le tri par sélection

On considère le tri par sélection appliqué à $t = [23, 8, 41, 15, 4, 16]$ . Démontrez qu'il range le tableau en ordre croissant, qu'il s'arrête, et donnez son nombre de comparaisons.

Tour par tour, la partie gauche définitive grandit d'une case. Les tours

2

5

ne changent rien au tableau, le minimum du reste s'y trouvant déjà en tête : l'invariant reste vrai, et c'est ce qui compte.

Étape 1

Invariant : « après $i$ tours de la boucle externe, 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 ».

Pourquoi

Les trois clauses sont nécessaires. « Les $i$ plus petits » interdit qu'une valeur plus petite reste dans le reste du tableau ; « en ordre croissant » range la partie gauche ; « ne seront plus modifiées » garantit que le travail déjà fait ne sera pas défait.

Étape 2

Initialisation : avant le premier tour, $i = 0$ , et l'affirmation porte sur zéro case. Elle est vraie.

Pourquoi

Un invariant portant sur un ensemble vide est toujours vrai, et c'est une initialisation parfaitement recevable. L'erreur serait de vouloir vérifier quelque chose sur $t[0]$ , qui n'est pas encore fixée.

Étape 3

Conservation : supposons l'invariant vrai après $i$ tours. Le tour suivant cherche le minimum de $t[i], \ldots, t[n-1]$ et l'échange avec $t[i]$ . Sur notre tableau, au tour $i = 2$ , le reste est $41$ , $15$ , $23$ , $16$ , dont le minimum est $15$ : on obtient $[4, 8, 15, 41, 23, 16]$ .

Pourquoi

Ce minimum est plus grand que chacun des $i$ éléments déjà placés, puisque ceux-ci sont les $i$ plus petits du tableau entier. Les $i+1$ premières cases contiennent donc les $i+1$ plus petits éléments, en ordre, et l'échange ne touche que les cases d'indice au moins $i$ : les précédentes ne bougent pas.

Étape 4

Sortie : la boucle s'arrête après $n-1 = 5$ tours. L'invariant affirme alors que les cinq premières cases contiennent les cinq plus petits éléments, en ordre croissant.

Pourquoi

La sixième case ne peut donc contenir que le plus grand élément restant, c'est-à-dire le maximum : le tableau entier est rangé. C'est ici que l'invariant FORT paie, car la version faible n'aurait rien dit de cette dernière case.

Étape 5

Terminaison : la boucle externe est un $for$ sur $range(n-1)$ , donc elle fait exactement $5$ tours ; la boucle interne est un $for$ sur $range(i+1, n)$ , donc $n-1-i$ tours.

Pourquoi

Une boucle $for$ sur un intervalle fini s'arrête par construction : il n'y a pas de variant à exhiber, contrairement à un $while$ . C'est un point de méthode, et l'oublier fait écrire des preuves inutiles.

Étape 6

Coût : la boucle interne fait $n-1-i$ comparaisons au tour $i$ , soit au total $5+4+3+2+1 = 15$ comparaisons pour $n = 6$ , c'est-à-dire $\dfrac{n(n-1)}{2}$ .

Pourquoi

Ce nombre ne dépend pas du contenu du tableau : la boucle interne parcourt tout le reste, que le minimum soit trouvé au premier essai ou au dernier. Le coût est donc quadratique dans tous les cas, au mieux comme au pire, ce qui distingue ce tri de celui par insertion.

Conclusion rédigée

L'algorithme est correct, il s'arrête par construction, et il coûte $\dfrac{n(n-1)}{2}$ comparaisons quel que soit le tableau, soit $15$ ici.

L'erreur classique sur cet exercice : Écrire l'invariant faible, « les $i$ premières cases sont triées entre elles ». Il est vrai, il se démontre aussi facilement, et il ne permet pas de conclure à l'étape de sortie : la preuve s'arrête net alors que tout le reste était juste.

À savoir par cœur

• Trois questions : est-ce juste, est-ce que ça s'arrête, combien ça coûte.
• Invariant : vrai avant chaque tour, vérifié en trois points.
• Variant : entier positif qui DÉCROÎT strictement.
• Une boucle $for$ sur un intervalle fini n'a pas besoin de variant.
• Des tests réfutent, ils ne démontrent jamais.
• Dichotomie : tableau TRIÉ, au plus $\lfloor\log_{2}n\rfloor+1$ tours.
• Sélection : $\dfrac{n(n-1)}{2}$ comparaisons, quel que soit le contenu.
• Insertion : $n-1$ comparaisons si le tableau est déjà rangé.
• Doublement : rapport $1$ , $2$ ou $4$ pour constant, linéaire, quadratique.
• Un gain constant par doublement, c'est un coût logarithmique.
• Glouton : un seul parcours, optimal seulement parfois.
• Une précondition s'écrit dans la spécification et se teste par une assertion.

Questions fréquentes

Quelle est la différence entre un invariant et un variant ?

L'invariant est une propriété qui ne change pas : elle est vraie avant chaque tour de boucle et encore vraie après, et c'est elle qui démontre que l'algorithme rend le bon résultat. Le variant, lui, est une quantité entière positive qui diminue strictement à chaque tour, et c'est elle qui démontre que la boucle finit par s'arrêter, puisqu'un entier positif ne peut pas diminuer indéfiniment. Les deux sont demandés séparément en évaluation, et l'un ne remplace jamais l'autre.

Pourquoi tester un programme ne suffit-il pas à le prouver ?

Parce qu'un test ne renseigne que sur les données qu'on lui a soumises. Un programme faux peut donner la bonne réponse sur tous les exemples auxquels on pense, et se tromper sur celui auquel on ne pense pas, typiquement le tableau vide, le tableau à un seul élément, ou la valeur située tout au bord. Les tests servent donc à trouver des erreurs, ce qu'ils font très bien, mais seule une preuve par invariant établit qu'il n'en reste aucune.

Qu'appelle-t-on une précondition ?

C'est une condition dont une fonction a besoin pour donner un résultat juste, et qu'elle ne vérifie pas elle-même. La recherche dichotomique en offre l'exemple parfait : elle exige un tableau rangé par ordre croissant, et si on lui en donne un autre, elle répond quand même, vite et faux, sans signaler la moindre erreur. Une précondition s'écrit donc dans la spécification de la fonction, et l'on place une assertion pour la contrôler à l'endroit où la donnée est produite, pas à chaque appel.

Comment reconnaître le coût d'un algorithme à partir de mesures ?

On double la taille des données plusieurs fois de suite et l'on regarde le rapport entre chaque temps et le précédent. Un rapport proche de un signale un coût constant, un rapport de deux un coût proportionnel à la taille, un rapport de quatre un coût proportionnel au carré de la taille. Si le temps augmente d'une même petite durée à chaque doublement au lieu d'être multiplié, le coût est logarithmique. Une mesure prise à une seule taille ne permet aucune conclusion.

Pourquoi utiliser un algorithme glouton s'il n'est pas toujours optimal ?

Pour son coût. Un glouton examine les possibilités une seule fois, dans l'ordre, et ne revient jamais en arrière : son temps de calcul est proportionnel au nombre de possibilités. Chercher la meilleure solution en examinant toutes les combinaisons demanderait, pour soixante objets, plus d'un milliard de milliards d'essais, ce qu'aucune machine ne fait. On accepte donc une solution qui est souvent la meilleure et parfois seulement bonne, en sachant dire dans quels cas elle est garantie.

Passer à la pratique

Exercices corrigés : Algorithmique : preuve, terminaison et coût

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

10 exercices corrigés
100 points
180 minutes

Faire les exercices

Fiche précédente Représentation des données : réels et texte Fiche suivante Traitement de données en tables et types construits

Ce chapitre resservira dans

Les chapitres qui le réclament en amont, plus tard dans l'année ou dans les années suivantes.

Algorithmique : recherche, tris, récursivité et complexitéTerminale

Voir aussi

Toutes les fiches Tous les exercices Exercices corrigés du chapitre Fiche : les bases de Python Fiche : les données en tables Tous les chapitres de NSI Première Tutorat NSI

Vous cherchez un tuteur en NSI à Montréal ?

Contactez-moi pour une première séance. Bachelier en informatique de McGill et maîtrise en informatique appliquée de Concordia, je travaille l'algorithmique sur la preuve et le coût, pas seulement sur le code qui tourne.

Me contacter WhatsApp

Site par Studio Squalli