Objectif SL pris en charge. Cible de première évaluation 2027 ; PDF officiel renvoyant 403 ; l'ancien résumé acquis est l'évaluation finale 2026. Le guide restant, les exigences d'évaluation et pratiques conservent leurs retenues enregistrées.
Prérequis : lisez les quantités et unités indiquées, utilisez l'arithmétique et les conditions du modèle ci-dessous. Chaque leçon développe sa propre méthode avant un transfert autonome.
Ce sont des exemples pédagogiques originaux ou explicitement fictifs, pas des mesures réelles ni des enquêtes évaluées achevées par des apprenants.
5.2
Algorithmes, traces et preuves de correction
Qu'est-ce qui expliquerait cette observation ?
Un algorithme peut fonctionner pour un exemple et échouer à une limite. Les tests doivent être conçus à partir de la spécification, et non uniquement du chemin heureux.
Commencez par une prédiction. Énoncez les quantités ou caractéristiques que vous compareriez, puis décidez quels éléments de preuve pourraient distinguer deux explications.
Construire le modèle
Un algorithme est une procédure finie et non ambiguë pour une tâche. Une trace enregistre les changements d'état. Un invariant de boucle décrit une propriété préservée par chaque itération et aide à justifier la correction.
algorithme : Procédure finie résolvant une tâche énoncée ; test aux limites : Test effectué à la limite de l'intervalle d'entrées autorisé.
Choisir des preuves capables de le tester
Énoncer les conditions d'entrée et les sorties attendues. Utiliser des cas limites, des collections vides si elles sont autorisées, des doublons et des valeurs invalides. Distinguer un algorithme erroné d'une implémentation défectueuse ou d'une exigence incomplète.
Tracer une recherche sur une petite liste fictive triée. Énoncer la convention d'indexation. Pour la recherche dichotomique, mettre à jour les bornes pour que l'intervalle restant se réduise et rejeter une entrée non triée sauf si le tri fait partie de la tâche.
Travailler à partir de quantités connues
Énoncez les valeurs connues et leurs unités. Choisissez la relation dont les hypothèses s'adaptent à ce cas, puis réarrangez-la avant de substituer les valeurs.
Connu : une recherche linéaire dans une liste de huit éléments peut nécessiter huit comparaisons lorsque l'élément recherché est le dernier ou absent. Doubler la longueur de la liste double le nombre maximal de comparaisons selon ce modèle. La recherche dichotomique réduit l'intervalle d'environ la moitié à chaque étape mais nécessite une structure ordonnée appropriée.
Exemple :
Une recherche linéaire scanne tous les 14 éléments sans correspondance. Combien de comparaisons d'éléments se produisent ? Utiliser la même séquence : quantités connues → modèle → relation → substitution → unité et interprétation.
Vérifier la conclusion et ses limites
Un échantillon de test réussi ne prouve pas la correction pour toutes les entrées valides. N'importez pas la syntaxe de pseudocode spécifique à Cambridge dans un cours du DI sans source de programme.
Revenez à l'observation initiale. Expliquez ce que le résultat soutient, quelles conditions il suppose, et une manière de tester une explication concurrente.
Avertissement :
Un échantillon de test réussi prouve qu'un algorithme est correct pour toute entrée valide. Cette affirmation est fausse : Un échantillon de test réussi ne prouve pas la correction pour toutes les entrées valides. N'importez pas la syntaxe de pseudocode spécifique à Cambridge dans un cours du DI sans source de programme.
Clé :
Algorithmes, traces et preuves de correction : Énoncer les conditions d'entrée et les sorties attendues. Utiliser des cas limites, des collections vides si elles sont autorisées, des doublons et des valeurs invalides. Distinguer un algorithme erroné d'une implémentation défectueuse ou d'une exigence incomplète.
Trace exécutable et limite
def first_index(values, target):
for index, value in enumerate(values):
if value == target:
return index
return -1
print(first_index([4, 7, 4], 4))
print(first_index([4, 7, 4], 9))
print(first_index([], 4))
Sortie attendue :
0
-1
-1
La boucle teste l'index 0 en premier, s'arrête sur une correspondance et retourne −1 uniquement après avoir épuisé la liste. Les doublons retournent donc le premier index. Une liste vide n'exécute aucun corps de boucle.
