Un cap pour ce chapitre
Ce que vous saurez faire
- Distinguer affirmation, exemple et justification générale.
- Nommer les hypothèses et les conventions.
- Présenter une solution avec un fil logique clair.
Les bases utiles pour commencer
Commencer par la réponse attendue
Si la question demande un résultat, donnez-le clairement puis exposez les étapes qui le rendent vérifiable. Si elle demande une méthode, annoncez son principe avant les détails. « Je compare la cible à la racine pour choisir un seul sous-arbre » fournit un fil directeur ; une liste de lignes Python sans explication peut masquer ce choix.
Le vocabulaire doit rester précis et accessible. Dire « il passe là » oblige le lecteur à deviner l’acteur et la branche. Dire « la recherche poursuit dans le sous-arbre gauche parce que la cible est inférieure à la racine » nomme l’opération, sa destination et sa raison.
Une réponse peut commencer par « Le chemin A-B-D est minimal en nombre d’arêtes : il comporte deux sauts et aucune liaison directe A-D n’existe ». Cette phrase donne résultat, mesure et argument. Les détails du dessin viennent ensuite pour aider le lecteur à contrôler les liaisons utilisées.
Utiliser l’exemple pour éclairer, pas pour tout prouver
Un exemple montre comment une règle s’applique. Pour la dichotomie, une liste courte et une cible absente rendent visibles les bornes et la condition d’arrêt. Mais réussir sur cette liste ne prouve pas tous les cas. La justification générale utilise la propriété de tri et le maintien d’une zone contenant toutes les positions encore possibles.
Un contre-exemple joue un rôle particulier : un seul cas valide qui contredit une affirmation universelle suffit à la réfuter. Le rendu de six avec 4,3,1 montre que le glouton n’est pas toujours optimal. À l’inverse, dix exemples favorables ne prouvent pas une affirmation portant sur tous les systèmes de pièces.
Annoncer les hypothèses qui portent l’argument
Une hauteur d’arbre dépend d’une convention en arêtes ou en niveaux. Un plus court chemin dépend d’une métrique. Une complexité dépend d’une taille et parfois d’une forme de structure. Préciser ces éléments n’allonge pas inutilement la réponse : cela évite une conclusion vraie sous une hypothèse cachée.
Pour un code, un invariant peut suivre trois moments : vrai avant la boucle, conservé par une itération et utile à la sortie. Pour une requête SQL, on explique les lignes retenues, l’association des tables et les éventuels doublons. La structure de justification s’adapte au sujet plutôt qu’à une formule unique.
Préparer l’oral comme une démonstration guidée
Choisissez un exemple assez petit pour tenir sur un schéma et annoncez ce que l’auditeur doit observer. Faites apparaître les états au bon moment au lieu de montrer immédiatement une page chargée. Les pauses permettent de vérifier que les termes ont été compris et de relier chaque détail au problème initial.
Entraînez-vous à répondre à une objection : « Que se passe-t-il si la cible est absente ? », « Pourquoi cette branche peut-elle être exclue ? », « Quelles limites possède ce modèle ? ». Reconnaître une limite précise renforce la qualité de l’explication. Il vaut mieux examiner un cas que multiplier des expressions savantes sans lien avec le raisonnement.
Exemple suivi : transformer une trace en argument général
Pour compter les valeurs positives, une trace sur [-2,3,0,4] donne des totaux 0,1,1,2. Elle explique un exemple. Pour justifier la méthode, on affirme : après k valeurs, le compteur vaut le nombre de valeurs strictement positives parmi les k premières. Au départ, aucune valeur n’est traitée et le compteur est nul. Une itération ajoute un exactement pour une nouvelle valeur positive, donc conserve la propriété.
À la sortie, le préfixe est toute la liste : le compteur répond au contrat. La terminaison vient du parcours borné, et non de l’invariant seul. La condition doit être strictement positive : si l’on écrivait « positive ou nulle », l’invariant décrirait une autre tâche. Une rédaction précise sépare donc ce que la variable signifie, pourquoi cette signification se conserve et pourquoi le programme atteint effectivement une sortie.
Exemple suivi : répondre à une objection sur la portée
Affirmation initiale : « Le glouton est optimal, il a réussi sur trois exemples. » Objection : avec les pièces 4,3,1 pour une somme six, il donne trois pièces alors que deux pièces de trois suffisent. La réponse corrigée devient : « Ces exemples ne prouvent pas une optimalité générale ; ce système fournit même un contre-exemple. » Elle ne doit pas devenir « le glouton est toujours mauvais », car le contre-exemple ne montre pas cela.
À l’oral, présentez d’abord la prétention examinée, puis les données du contre-exemple, les deux résultats et la conclusion limitée. Un petit tableau avec méthode, rendu et nombre de pièces suffit : glouton, 4+1+1, trois ; autre solution, 3+3, deux. Aucun développement technique supplémentaire n’est nécessaire pour réfuter « toujours ». Si l’auditeur demande si deux est minimal, ajoutez qu’aucune pièce de six n’existe et qu’une seule pièce ne peut donc convenir.
| Méthode ou solution | Rendu de six avec 4,3,1 | Nombre de pièces |
|---|---|---|
| Glouton | 4 + 1 + 1 | 3 |
| Solution alternative | 3 + 3 | 2 |
À vous de faire varier les choses
Que permet réellement d’établir cette phrase ?
Classez chaque proposition selon sa fonction argumentative. Les retours expliquent la portée de chaque type de phrase.
Lire les associations expliquées
- On compte la hauteur en nombre d’arêtes. : Hypothèse ou convention
- Cette convention fixe le sens de la mesure.
- Pour [2,4,6], la recherche de quatre réussit au milieu. : Exemple
- Ce cas illustre un mécanisme sans couvrir toutes les listes.
- Le tableau est trié ; toute valeur à gauche du milieu est au plus celle du milieu. : Justification générale
- Cette propriété d’ordre permet de justifier une exclusion pour tous les éléments concernés.
- Le programme fonctionne parce qu’il semble correct. : Affirmation insuffisante
- Aucune propriété ni vérification ne soutient la conclusion.
- Les doublons sont ignorés lors de l’insertion. : Hypothèse ou convention
- La politique de la structure est annoncée.
- Pour six avec 4,3,1, le glouton utilise trois pièces et l’optimal deux. : Exemple
- Cet exemple peut servir de contre-exemple à une affirmation universelle.
- Le variant est un entier naturel qui décroît strictement à chaque itération. : Justification générale
- Sous les conditions annoncées, il ne peut décroître indéfiniment et justifie la terminaison.
- La route est optimale car elle paraît courte sur le dessin. : Affirmation insuffisante
- La forme dessinée ne remplace pas la métrique et sa comparaison.
- Pour la somme six, aucune pièce de six n’existe ; une seule pièce est impossible, et deux pièces de trois suffisent. : Justification générale
- L’argument fournit une solution et exclut toute solution utilisant moins de pièces pour ce problème précis.
- Les trois exemples réussissent ; tous les programmes de cette forme sont donc corrects. : Affirmation insuffisante
- Une généralisation universelle ne découle pas de trois observations. Il faut un argument couvrant les cas annoncés.
- Dans cette étude, « longueur » désigne le nombre de liaisons et non la distance mesurée sur le dessin. : Hypothèse ou convention
- La convention fixe la métrique qui rend ensuite la comparaison de chemins vérifiable.
Une bonne explication distingue ce qui est supposé, illustré et effectivement démontré.
De la compréhension à l’autonomie
À vous de résoudre
Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.
Rendre une phrase vérifiable
Améliorez « la réponse est six parce que ça se voit » pour la somme des entiers de un à trois.
Indice 1
Écrivez les termes additionnés.
Indice 2
La justification peut être très courte quand le calcul est simple.
Comprendre la correction
On peut écrire : « La somme vaut six, car 1+2+3=6. » La phrase donne le résultat et les données du calcul. Une justification adaptée n’est pas forcément longue ; elle rend simplement le passage à la conclusion contrôlable.
Réfuter une généralisation
On affirme que choisir la plus grande pièce donne toujours le nombre minimal de pièces. Quel rôle joue le cas six avec 4,3,1 ?
Indice 1
Comparez trois pièces et deux pièces.
Indice 2
L’affirmation contient toujours.
Comprendre la correction
Le cas constitue un contre-exemple : le glouton donne 4+1+1, alors que 3+3 utilise moins de pièces. Il suffit à réfuter « toujours ». Il ne prouve pas que le glouton échoue sur toutes les sommes ou tous les systèmes.
Ajouter une hypothèse manquante
Complétez « le parcours infixe donne les clés en ordre croissant » pour éviter une affirmation fausse sur un arbre quelconque.
Indice 1
Quelle propriété d’ordre doit respecter l’arbre ?
Indice 2
La convention des doublons doit aussi être cohérente.
Comprendre la correction
On précise qu’il s’agit d’un arbre binaire de recherche respectant sa propriété d’ordre. Le parcours infixe traite les clés plus petites, puis la racine, puis les plus grandes. Sans cette hypothèse, l’ordre des étiquettes peut être quelconque.
Préparer une objection utile
Vous expliquez une recherche de valeur dans une liste. Proposez deux questions qui testent la solidité de votre explication.
Indice 1
Un résultat peut être absent.
Indice 2
La liste peut avoir une taille limite.
Comprendre la correction
« Que renvoie la méthode si la valeur est absente ? » et « Que se passe-t-il pour une liste vide ? » sont deux questions utiles. Elles vérifient le contrat et les conditions d’arrêt. Une question sur les doublons peut également préciser si l’on cherche la première occurrence ou toutes les occurrences.
Étude de cas : préciser une phrase de complexité
Un élève écrit : « La recherche est rapide parce qu’elle est dans un arbre. » Reformulez pour une recherche dans un ABR, en indiquant taille, forme et cas. Donnez un contre-exemple à la garantie logarithmique sans hypothèse de forme. Proposez un dessin utile à l’oral.
Indice 1
Le coût suit la longueur d’un chemin.
Indice 2
Un ABR peut être une chaîne.
Comprendre la correction
On peut écrire : « La recherche compare au plus les clés d’un chemin ; son coût dépend de la hauteur. Il est logarithmique pour un arbre suffisamment équilibré et peut être linéaire dans une chaîne. » Les insertions 1,2,3,4,5 forment une chaîne où chercher 5 demande cinq comparaisons. Un dessin de cette chaîne à côté d’un arbre réparti de mêmes clés rend visible l’hypothèse manquante.
Étude de cas : réparer une preuve de comptage
Une rédaction dit : « Le total augmente parfois, donc il donne le nombre de valeurs ≥10. » Complétez par une propriété avant la boucle, sa conservation et sa conséquence finale. Ajoutez la justification de terminaison et le cas de la liste vide.
Indice 1
Le compteur doit décrire exactement le préfixe traité.
Indice 2
La boucle parcourt un nombre fini de valeurs.
Comprendre la correction
Initialement total=0 compte les valeurs admissibles du préfixe vide. À chaque tour, on ajoute un si et seulement si la nouvelle valeur est ≥10 : le compteur décrit donc le préfixe agrandi. À la fin, ce préfixe est la liste entière. Le parcours borné termine ; pour une liste vide, aucune itération n’a lieu et le résultat reste zéro. L’argument relie le mécanisme à sa signification.
Étude de cas : préparer une explication de deux minutes
Vous présentez un programme de recherche dans une liste qui renvoie la première position de la cible ou -1 si elle est absente. Proposez un ordre d’explication et deux exemples, dont un avec doublon. Formulez une objection utile et indiquez la réponse attendue pour la liste vide.
Indice 1
Annoncez le contrat avant la trace.
Indice 2
La première occurrence diffère de toutes les occurrences.
Comprendre la correction
On annonce l’entrée et la sortie, explique le parcours depuis l’indice zéro, puis montre [4,7,4] avec cible 4 : résultat 0 dès la première case. Un cas absent, cible 9, parcourt tout et renvoie -1. L’objection « pourquoi ignorer le second 4 ? » reçoit la réponse « le contrat demande la première position ». Pour [], aucun accès n’est effectué et -1 est renvoyé.
Les erreurs qui méritent un détour
- Présenter un exemple réussi comme une preuve universelle.
- Un exemple illustre ; une preuve établit tous les cas visés sous ses hypothèses.
- Multiplier les détails avant d’annoncer l’idée.
- Le lecteur a besoin d’un fil directeur pour comprendre leur rôle.
La fiche à garder
L’essentiel à retenir
- Une conclusion doit être reliée à une raison contrôlable.
- Les hypothèses et conventions délimitent la portée de l’argument.
- Les exemples éclairent et les contre-exemples réfutent des généralisations.
Le prochain pas
- Prouver la correction et la terminaison d’un algorithme
- Coûts en temps et en mémoire
- Concevoir et mener un projet de NSI
Retrouver le catalogue des ressources
Ce chapitre s’appuie sur les programmes officiels de NSI (nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.