NSI Terminale • Programme français, lycées de Montréal

Fiche de révision : récursivité, objet et preuve de programme en NSI

Le chapitre des langages est celui où le code juste ne suffit pas. Les questions demandent de justifier qu'une récursion s'arrête, de compter des appels, d'énoncer ce qu'une classe garantit, d'exhiber un invariant. Ce sont des rédactions, pas des programmes, et c'est là que le barème se joue.

Cette fiche liste les neuf erreurs qui reviennent dans les copies, avec la phrase exacte à écrire à la place et ce que chacune coûte au barème. L'héritage et le polymorphisme, que le programme de Terminale n'aborde pas, sont présentés à part, pour aller plus loin.

Mis à jour le 18 octobre 2026

Marque ici la fiche comme lue ou mets-la en favori : un compte gratuit, sans mot de passe, retient tes fiches lues et tes favoris d'une visite à l'autre, te dit quel chapitre attaquer ensuite et te permet de demander la méthode ou l'exercice qui te manque. Crée ton espace, un courriel suffit.

Le fil du chapitre

Ce chapitre ne demande pas d'écrire du code qui marche, mais de PROUVER ce qu'il fait : terminaison, correction, coût. Un programme juste sans preuve n'y vaut que la moitié des points.

Ce chapitre fait partie de NSI en Terminale

Pour s'entraîner Les exercices corrigés de ce chapitre, 15 exercices

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.

Révision : l'algorithmique de Première, récursivité et Horspool Exercices

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.

1 Algorithmique et Python Seconde, Mathématiques
2 Python : types, contrôle, fonctions et tableaux Première
3 Algorithmique : preuve, terminaison et coût Première
4 Révision : l'algorithmique de Première, récursivité et Horspool

L'essentiel

La pile d'appels : ce qui se passe vraiment

• Chaque appel récursif empile un CADRE, avec ses propres variables locales. Rien n'est calculé à la descente.
• Tout se calcule à la REMONTÉE, quand chaque cadre reçoit la valeur renvoyée par celui du dessus.
• Sans cas de base atteignable, la pile déborde : Python lève RecursionError, ce n'est pas une boucle infinie.
• La profondeur maximale est de l'ordre de mille appels : une récursion sur un tableau de dix mille éléments ne passe pas.

Les mêmes trois cadres, lus deux fois : à la descente aucune multiplication n'est faite, à la remontée chacune s'effectue avec la valeur reçue du cadre supérieur.

Une question « quelle est la valeur renvoyée » se traite en dessinant la pile : trois cadres suffisent presque toujours à voir la structure.

Le coût d'une récursivité

• Le nombre d'appels se lit sur l'ARBRE des appels : chaque noeud est un appel, et les sous-arbres identiques sont des calculs refaits.
• Pour la suite de Fibonacci naïve, le nombre d'appels vaut $2F(n+1) - 1$ : quinze appels pour $n = 5$ , deux millions six cent quatre-vingt-douze mille cinq cent trente-sept pour $n = 30$ .
• La mémoïsation range chaque valeur calculée dans un dictionnaire, consulté à l'entrée de chaque appel : les $n + 1$ valeurs, 31 pour $n = 30$ , ne sont calculées qu'une fois, et le nombre d'appels tombe à $2n - 1$ , soit 59.
• Une récursion terminale, où l'appel récursif est la DERNIÈRE opération, se transforme mécaniquement en boucle.

Objet : ce que le jury attend qu'on nomme

• La classe décrit, l'instance existe. Une classe s'écrit une fois, les instances se comptent.
• self désigne l'instance : $c.methode(x)$ est en réalité $Classe.methode(c, x)$ , ce qui explique pourquoi self est le premier paramètre.
• L'encapsulation est un CONTRAT, pas une barrière : le tiret bas signale qu'un attribut est interne, il n'en interdit pas l'accès en Python.
• Le vocabulaire exigible : classe, attribut, méthode, objet. Une méthode s'APPELLE, avec ses parenthèses : $r.aire()$ renvoie un nombre, $r.aire$ désigne la méthode elle-même.

Une seule classe, écrite une fois, et deux instances qui existent chacune avec ses propres valeurs d'attributs : c1 et c2 ne partagent que les méthodes.

Le constructeur __init__ est le seul endroit où l'on crée les attributs : c'est là que se garantit ce que la classe promet, par exemple une largeur strictement positive.

Invariant, variant, correction

• INVARIANT : une propriété vraie à chaque tour, qui porte sur le travail DÉJÀ FAIT. Elle sert à la correction.
• VARIANT : un entier positif qui décroît STRICTEMENT à chaque tour. Il sert à la terminaison, et à elle seule.
• Correction partielle : si l'algorithme s'arrête, son résultat est juste. Correction TOTALE : correction partielle plus terminaison.
• Une preuve complète comporte donc trois pièces : l'invariant, sa conservation, et le variant.

L'invariant décrit la zone bleue, déjà parcourue : m en contient le maximum. Le variant compte les cases qui restent,

n - i = 4

, et diminue de 1 à chaque tour.

Décidabilité

• Le problème de l'arrêt est INDÉCIDABLE : aucun programme ne peut décider, pour tout couple programme-entrée, si l'exécution s'arrête.
• La démonstration est par l'absurde : on construit un programme qui fait le contraire de ce que la méthode prédit sur lui-même.
• Cela n'interdit nullement de prouver la terminaison d'un programme PARTICULIER : c'est la méthode UNIVERSELLE qui n'existe pas.
• Conséquence pratique : aucun outil ne détectera toutes les boucles infinies, ce qui n'empêche aucun outil d'en détecter beaucoup.

diagonale fait le contraire de ce qu'annonce arrete ; appliquée à elle-même, elle s'arrête exactement quand arrete dit qu'elle ne s'arrête pas : arrete ne peut pas exister.

Pour aller plus loin, hors programme : héritage et polymorphisme

• Le programme de Terminale le dit en toutes lettres : « on n'aborde pas » le polymorphisme et l'héritage. Une copie n'en a jamais besoin ; un sujet qui les montre les explique.
• L'héritage traduit « EST UN » : un carré est un rectangle. « A UN » se traduit par un attribut, c'est la composition : une voiture a un attribut de type Moteur.
• Test de substitution : la sous-classe doit pouvoir remplacer la classe parente PARTOUT sans surprendre l'appelant. Une voiture ne peut pas remplacer un moteur.
• Polymorphisme : l'appel $self.aire()$ est résolu à l'exécution, selon la classe réelle de l'objet.

Deux relations, deux schémas : la flèche montante de l'héritage exige un « est un », tandis qu'un « a un » se dessine comme un attribut, jamais comme une flèche d'héritage.

En cas de doute, composer : un attribut qui contient un objet est du vocabulaire du programme, l'héritage n'en est pas.

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. Écrire l'appel récursif avant le cas de base

1 point sur la question de diagnostic, et le vocabulaire est noté

Ce qu'il ne faut pas écrire

« La fonction boucle à l'infini parce que j'ai oublié la condition d'arrêt. »

Ce qu'il faut écrire

« Sans cas de base, la pile déborde et Python lève RecursionError après environ mille appels. Ce n'est pas une boucle infinie, c'est un débordement de pile. »

La récursion sans cas de base empile un cadre par appel : la mémoire monte jusqu'à la limite, puis RecursionError. Une boucle infinie tourne sans fin à mémoire constante.

Pourquoi : Une boucle infinie consomme du temps sans mémoire ; une récursion sans fin consomme de la mémoire et s'arrête d'elle-même sur une erreur. Le sujet distingue toujours les deux.

2. Croire qu'une récursion double coûte comme une boucle

2 points sur la question de coût, celle qui est vraiment notée

Ce qu'il ne faut pas écrire

« La fonction de Fibonacci récursive fait $n$ appels, comme la version itérative fait $n$ tours. »

Ce qu'il faut écrire

« Chaque appel en déclenche deux : l'arbre des appels compte $2F(n+1) - 1$ noeuds, soit 15 pour $n = 5$ et $2\,692\,537$ pour $n = 30$ . La mémoïsation ramène ce nombre à $2n - 1$ , soit 59 appels pour 31 valeurs calculées. »

L'arbre des appels de fib(5) : le sous-arbre de fib(3) apparaît deux fois, celui de fib(2) trois fois ; en rouge, les 9 appels qui refont un calcul déjà fait.

Pourquoi : Ce n'est pas la récursivité qui coûte, c'est la REDONDANCE : les mêmes sous-appels sont refaits un nombre exponentiel de fois. C'est exactement ce que la mémoïsation supprime.

3. Oublier self, ou croire qu'il est passé à l'appel

1 point, et une erreur d'exécution qui bloque la question

Ce qu'il ne faut pas écrire

« $c.aire(2)$ passe un seul argument, donc la méthode s'écrit def aire(x). »

Ce qu'il faut écrire

« $c.aire(2)$ est traduit en $Classe.aire(c, 2)$ : la méthode reçoit deux arguments et s'écrit def aire(self, x). »

Pourquoi : L'instance est passée implicitement en premier argument. Comprendre cette traduction supprime d'un coup toutes les erreurs de nombre d'arguments du chapitre.

4. Croire que le tiret bas empêche l'accès

1 point sur la question de vocabulaire, souvent posée en début de sujet

Ce qu'il ne faut pas écrire

« L'attribut s'appelle _solde, donc il est privé et personne ne peut le modifier de l'extérieur. »

Ce qu'il faut écrire

« Le tiret bas est une CONVENTION : il signale que l'attribut est interne, et Python n'interdit rien. L'encapsulation est un contrat que l'appelant s'engage à respecter. »

Pourquoi : Confondre convention et contrainte fait croire qu'un programme est protégé alors qu'il ne l'est que par discipline. La question du bac porte précisément sur ce statut.

5. Appeler une méthode sans ses parenthèses

1 point, et toute question qui réutilise la valeur

Ce qu'il ne faut pas écrire

« print(r.aire) affiche l'aire du rectangle r. »

Ce qu'il faut écrire

« r.aire désigne la méthode elle-même, et print affiche seulement qu'il s'agit d'une méthode liée à r. C'est r.aire() qui l'appelle et renvoie $6\times 4=24$ . »

Pourquoi : Aucune erreur n'est levée : Python affiche un objet méthode au lieu d'un nombre. La même confusion dans un calcul, r.aire + 1, lève une TypeError loin de sa cause.

6. Donner un variant à la place d'un invariant

2 points, et la preuve de correction devient impossible à conclure

Ce qu'il ne faut pas écrire

« L'invariant est que $i$ augmente à chaque tour. »

Ce qu'il faut écrire

« Ça, c'est le variant, sous la forme $n - i$ qui décroît. L'invariant porte sur le travail déjà fait : « après $k$ tours, m contient le maximum des $k$ premiers éléments ». »

Pourquoi : Les deux objets prouvent des choses différentes : l'invariant sert à la correction, le variant à la terminaison. Les échanger donne une preuve qui ne démontre rien.

7. Conclure à la correction totale sans parler de terminaison

1 point, systématiquement retiré au bac

Ce qu'il ne faut pas écrire

« L'invariant est conservé et donne le bon résultat en fin de boucle : l'algorithme est correct. »

Ce qu'il faut écrire

« L'invariant établit la correction PARTIELLE. Pour la correction totale, j'ajoute le variant $n - i$ , entier positif qui décroît strictement, donc la boucle s'arrête. »

Pourquoi : Un algorithme qui ne s'arrête jamais vérifie n'importe quel invariant. La terminaison est donc une pièce indépendante de la preuve, et le sujet la demande explicitement.

8. Déduire de l'indécidabilité qu'aucune terminaison n'est démontrable

2 points sur la question de recul, où le contresens est fatal

Ce qu'il ne faut pas écrire

« Le problème de l'arrêt est indécidable, donc on ne peut pas prouver qu'un programme s'arrête. »

Ce qu'il faut écrire

« Aucune méthode UNIVERSELLE n'existe. Pour un programme donné, un variant suffit à prouver la terminaison, et c'est ce qu'on fait à chaque question de ce sujet. »

Pourquoi : L'indécidabilité porte sur l'existence d'un algorithme qui répondrait pour TOUS les cas. Elle ne dit rien de chaque cas particulier, où une preuve à la main reste possible.

9. Ne tester que le cas nominal

1 point sur la question de jeu de tests, qui demande toujours de justifier les cas choisis

Ce qu'il ne faut pas écrire

« La fonction renvoie la bonne valeur sur mon exemple, elle est donc correcte. »

Ce qu'il faut écrire

« Je teste aussi les bords : liste vide, un seul élément, valeurs égales, et la plus grande entrée acceptable. C'est là que se trouvent les erreurs. »

Pourquoi : Un jeu de tests se justifie par ce qu'il COUVRE : chaque cas doit correspondre à une branche du code ou à une frontière de la spécification. Trois cas justifiés valent mieux que dix pris au hasard.

Quelle méthode choisir

Récursif ou itératif, et faut-il mémoïser

La forme des appels : combien d'appels récursifs par exécution, et se recoupent-ils.

Un appel par exécution donne une chaîne ; deux appels sur des moitiés disjointes, un arbre sans répétition ; deux appels qui se recoupent, des sous-arbres répétés, en rouge : il faut mémoïser.

Si un seul appel récursif, en dernière opération → récursion terminale, transformable en boucle

Exemple : la somme des éléments d'une liste
Si un seul appel, mais un calcul après → récursion simple, coût linéaire, la pile grandit

Exemple : la factorielle
Si deux appels sur des sous-problèmes DISJOINTS → diviser pour régner, coût en $n \log_{2} n$

Exemple : le tri fusion
Si deux appels sur des sous-problèmes QUI SE RECOUPENT → mémoïsation obligatoire, sinon coût exponentiel

Exemple : Fibonacci, $2\,692\,537$ appels contre 59

c'est le critère qui sépare le raisonnable de l'impraticable

Si la profondeur peut dépasser le millier, la version itérative est obligatoire, quelle que soit l'élégance de la récursion.

Quel paradigme choisir

La nature du traitement : une suite d'actions sur des variables, une transformation de données, un état à protéger, ou une structure qui se contient elle-même.

Si une suite d'actions qui modifie des variables, pas à pas → impératif : affectations et boucles

Exemple : cumuler les $n$ premiers carrés dans une variable, $n$ tours de boucle
Si transformer une liste en une autre, sans rien modifier d'autre → fonctionnel : fonction sans effet de bord, compréhension

Exemple : les carrés des pairs de [3, 4, 7, 6] donnent [16, 36]

sans effet de bord, la fonction se teste sur une entrée et une sortie, rien d'autre
Si des données qui doivent rester cohérentes entre elles → objet : une classe, dont le constructeur établit ce que l'objet garantit

Exemple : une fraction toujours simplifiée, $\frac{6}{-8}$ rangée comme $\frac{-3}{4}$
Si une structure qui contient des structures du même type → fonction récursive, un appel par sous-structure

Exemple : la somme de [1, [2, 3], [4, [5]]] vaut 15

Un même langage sert plusieurs paradigmes, et un même programme peut les mêler : Python a des boucles, des compréhensions et des classes. Le programme demande de DISTINGUER les trois et de JUSTIFIER un choix, pas d'en préférer un.

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.

Prouver qu'une boucle est correcte et qu'elle s'arrête

Quand l'utiliser : L'énoncé demande de justifier qu'un algorithme itératif est correct, ou parle d'invariant.

1 Énoncer l'invariant en une phrase qui porte sur le travail déjà fait, en faisant apparaître le compteur : « après $k$ tours, ... ».
2 Montrer l'initialisation : l'invariant est vrai avant le premier tour, souvent trivialement.
3 Montrer la conservation : s'il est vrai avant un tour, il l'est encore après, en suivant les instructions du corps.
4 Conclure la correction partielle : à la sortie de boucle, l'invariant plus la condition d'arrêt donnent exactement le résultat attendu.
5 Donner le variant : un entier positif qui décroît strictement, donc la boucle s'arrête, ce qui achève la correction totale.

Phrase de conclusion

« Invariant : après $k$ tours, m contient le maximum des $k$ premiers éléments. Il est vrai avant le premier tour, il est conservé car chaque tour compare m au nouvel élément, et à la sortie $k = n$ donne le maximum du tableau entier. Le variant $n - i$ est un entier positif strictement décroissant, donc la boucle s'arrête : l'algorithme est totalement correct. »

Le piège : Écrire un invariant qui ne mentionne pas le compteur : il devient invérifiable et la conservation ne se démontre plus.

Barème : 1 point pour l'énoncé de l'invariant, 1 pour l'initialisation, 1 pour la conservation, 1 pour le variant.

Justifier un jeu de tests

Quand l'utiliser : L'énoncé demande de proposer des tests, ou de dire si un jeu de tests est suffisant.

1 Rappeler la spécification en une phrase : ce que la fonction reçoit, ce qu'elle renvoie, à quelles conditions.
2 Prendre un cas nominal, et dire ce qu'il vérifie.
3 Prendre chaque cas limite de la spécification : entrée vide, un seul élément, valeurs égales, borne maximale.
4 Prendre un cas par branche du code, y compris celles que le cas nominal ne traverse pas.
5 Conclure sur ce que le jeu de tests NE prouve pas : un test ne démontre jamais l'absence de bogue.

Phrase de conclusion

« Le jeu retenu couvre le cas nominal, la liste vide, la liste à un élément et le cas de deux maxima égaux, soit une entrée par branche du code. Il ne démontre pas la correction, qui repose sur l'invariant, mais il exercerait chaque branche au moins une fois. »

Le piège : Aligner cinq tests sans dire ce que chacun couvre : le barème note la justification, pas le nombre.

Barème : 1 point par cas limite justifié, 1 point pour la phrase de portée.

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.

Dérouler la récursion sur trois niveaux

Écrire les cadres empilés pour un petit argument, puis les valeurs renvoyées à la remontée. Si le cas de base n'apparaît pas, il n'est pas atteignable.

fact(3) doit produire exactement trois cadres et s'arrêter sur fact(1) : quatre cadres signalent un cas de base placé trop bas.
Compter les noeuds de l'arbre des appels

Pour une récursion double, dessiner l'arbre sur un petit argument et compter : si des sous-arbres se répètent, le coût est exponentiel et la mémoïsation est attendue.

L'arbre de fib(5) compte quinze noeuds pour six valeurs distinctes, de fib(0) à fib(5) : neuf appels sont des recalculs.
Relire chaque accès dans une méthode

Dans le corps d'une méthode, chaque attribut se lit par self, et chaque méthode s'appelle avec ses parenthèses. Un nom nu désigne une variable locale, qui n'existe pas.

return longueur * largeur dans la méthode aire lève une NameError ; return self.longueur * self.largeur renvoie 24 pour un rectangle de 6 sur 4.
Vérifier que le variant est bien un entier positif

Un variant doit être entier, positif ou nul, et décroître STRICTEMENT. Une quantité qui peut stagner un tour ne prouve rien.

$n - i$ convient si $i$ augmente d'au moins 1 par tour ; il ne convient pas si $i$ n'augmente que sous condition.
Relire la spécification avant les tests

Chaque cas limite de la spécification doit avoir son test. Une spécification sans cas limite est probablement incomplète.

Une fonction qui renvoie le maximum d'une liste doit préciser ce qu'elle fait sur une liste vide, sinon aucun test ne peut couvrir ce cas.

L'exercice type décortiqué

Une récursion double, son coût, et la mémoïsation

On écrit la suite de Fibonacci en récursivité naïve, avec $fib(0) = 0$ , $fib(1) = 1$ et $fib(n) = fib(n-1) + fib(n-2)$ .

Dessiner l'arbre des appels pour $n = 5$ , en déduire le nombre d'appels pour $n = 30$ , puis proposer une correction et chiffrer le gain.

Étape 1

L'arbre de $fib(5)$ compte 15 noeuds : $fib(3)$ y apparaît deux fois et $fib(2)$ trois fois.

Pourquoi

Le dessin est la réponse à la moitié de la question : il fait voir que le coût vient de la redondance et non de la récursivité, ce qu'aucune formule seule ne montre.

Étape 2

Le nombre d'appels vérifie $T(n) = 1 + T(n-1) + T(n-2)$ , dont la solution est $T(n) = 2F(n+1) - 1$ .

Pourquoi

La récurrence se lit directement sur la définition : un appel, plus les deux sous-appels. C'est le passage de l'observation à la formule que le barème attend.

Étape 3

Contrôle sur $n = 5$ : $F(6) = 8$ , donc $T(5) = 2 \times 8 - 1 = 15$ , ce qui coïncide avec l'arbre.

Pourquoi

Vérifier la formule sur le cas déjà dessiné coûte une ligne et prouve qu'elle n'a pas été recopiée au hasard. C'est le contrôle le plus rentable de la question.

Étape 4

Pour $n = 30$ : $F(31) = 1\,346\,269$ , donc $T(30) = 2\,692\,537$ appels.

Pourquoi

Le chiffre est ce qui rend la conclusion défendable. « C'est exponentiel » ne vaut rien tant qu'on n'a pas montré ce que cela donne sur une valeur réaliste.

Étape 5

Correction : mémoïsation dans un dictionnaire, consulté avant tout calcul et rempli après.

Pourquoi

Il faut décrire le mécanisme, pas seulement le nommer : consulter AVANT, ranger APRÈS. C'est cet ordre qui garantit qu'aucune valeur n'est calculée deux fois.

Étape 6

Nouveau coût : chaque valeur de 0 à $n$ est calculée une seule fois, soit 31 valeurs pour $n = 30$ , et le nombre d'appels tombe à $2n - 1 = 59$ , contre $2\,692\,537$ .

Pourquoi

Le rapport des nombres d'appels, de l'ordre de quarante-cinq mille, est la réponse chiffrée à « quel gain ». Sans lui, la question reste sans réponse même si la mémoïsation est décrite.

Conclusion rédigée

« La récursivité naïve effectue $T(n) = 2F(n+1) - 1$ appels, soit 15 pour $n = 5$ et $2\,692\,537$ pour $n = 30$ , parce que les mêmes sous-appels sont refaits un nombre exponentiel de fois. En mémoïsant, chaque valeur n'est calculée qu'une fois : 31 valeurs et 59 appels suffisent pour $n = 30$ . »

L'erreur classique sur cet exercice : Répondre « la récursivité est lente » : ce n'est pas la récursivité qui coûte, mais la redondance des sous-appels, et c'est exactement ce que la mémoïsation supprime sans rien changer à la structure récursive.

À savoir par cœur

• À la descente, rien n'est calculé. Tout se fait à la REMONTÉE.
• Pas de cas de base atteignable : RecursionError, pas boucle infinie. Profondeur limitée à environ mille.
• Récursion double sur des sous-problèmes qui se recoupent : mémoïser, sinon coût exponentiel.
• $c.methode(x)$ vaut $Classe.methode(c, x)$ : self est le premier paramètre.
• Le tiret bas SIGNALE, il n'interdit pas. L'encapsulation est un contrat.
• Classe, attribut, méthode, objet : le vocabulaire exigible. Héritage et polymorphisme : hors programme de Terminale.
• INVARIANT pour la correction, VARIANT pour la terminaison. Correction totale = les deux.
• Le problème de l'arrêt est indécidable : pas de méthode UNIVERSELLE, mais chaque programme reste prouvable à la main.

Questions fréquentes

Pourquoi ma fonction récursive donne-t-elle une RecursionError ?

Parce que le cas de base n'est jamais atteint : chaque appel en empile un nouveau, et Python limite la profondeur à environ mille cadres. Ce n'est pas une boucle infinie mais un débordement de pile. On vérifie que l'argument décroît strictement à chaque appel et que le cas de base est testé avant tout appel récursif.

Pourquoi Fibonacci en récursif est-il si lent ?

Parce que les mêmes sous-appels sont refaits un nombre exponentiel de fois : l'arbre des appels compte quinze noeuds pour n égal à 5, et deux millions six cent quatre-vingt-douze mille cinq cent trente-sept pour n égal à 30. Ce n'est pas la récursivité qui coûte, mais la redondance. Mémoïser dans un dictionnaire ramène le nombre de valeurs calculées à trente et une, et le nombre d'appels à cinquante-neuf.

Quelle différence entre un invariant et un variant de boucle ?

L'invariant est une propriété vraie à chaque tour, qui décrit le travail déjà fait, et il sert à prouver que le résultat est juste. Le variant est un entier positif qui décroît strictement à chaque tour, et il sert uniquement à prouver que la boucle s'arrête. Une preuve complète comporte les deux : c'est ce qu'on appelle la correction totale.

L'héritage est-il au programme de NSI en Terminale ?

Non. Le programme de Terminale demande le vocabulaire de la programmation objet, classe, attribut, méthode et objet, de savoir écrire la définition d'une classe et d'accéder à ses attributs et à ses méthodes. Il précise qu'on n'y aborde pas le polymorphisme et l'héritage : un sujet peut les montrer, en les expliquant, mais ils ne sont pas exigibles.

Si le problème de l'arrêt est indécidable, peut-on prouver qu'un programme s'arrête ?

Oui, pour un programme donné. L'indécidabilité signifie qu'aucune méthode universelle ne peut répondre pour tout couple programme-entrée, ce qui n'empêche pas de démontrer à la main la terminaison d'un algorithme précis, généralement en exhibant un variant. C'est même exactement ce que demandent les questions de preuve du programme de Terminale.

Passer à la pratique

Exercices corrigés : Récursivité, objet, mise au point et calculabilité

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.

15 exercices corrigés
150 points
255 minutes

Faire les exercices

Il manque quelque chose dans cette fiche ? Une méthode, un piège, un exercice pour l'appliquer, une erreur repérée : dis-le-moi, je lis chaque demande.

L'envoi passe par ton espace gratuit : c'est ce qui me permet de te répondre et de te prévenir quand l'exercice est ajouté. Un courriel suffit, pas de mot de passe. Crée ton espace. Pas envie de créer un compte ? Écris-moi directement.

Fiche précédente Processus, réseaux et sécurisation Fiche suivante Diviser pour régner, programmation dynamique et graphes

© Ahmed Squalli Houssaini. Fiche publiée sur www.letuteurscientifique.ca/fiches/tnsi-langages-programmation. Libre pour l'usage personnel et en classe ; sa republication ailleurs demande une autorisation écrite (mentions légales).

Voir aussi

Toutes les fiches Tous les exercices Tuteur NSI NSI : les structures de données Tuteur Terminale

Vous cherchez un tuteur en NSI à Montréal ?

Contactez-moi pour une première séance. On reprend les points de méthode qui font perdre des points en évaluation, puis on les met à l'épreuve sur des exercices du niveau réel de l'examen.

Me contacter WhatsApp

Site par Studio Squalli