1. Objectifs, niveau et prérequis

• Définir les entrées autorisées et la sortie exigée d'un algorithme.
• Tracer une recherche de maximum avec une variable, une condition et une boucle.
• Justifier la correction et la terminaison, puis distinguer preuve et tests.

Un algorithme décrit une méthode précise pour transformer des données d'entrée en un résultat. Ici, nous étudions des algorithmes déterministes qui doivent terminer pour toute entrée autorisée. Un programme exprime une telle méthode dans un langage qu'une machine peut exécuter ; une même méthode peut avoir plusieurs programmes.

À la fin de cette initiation, vous pourrez préciser les entrées et la sortie attendue, suivre les valeurs d'une variable et justifier pourquoi une recherche de maximum termine et donne le bon résultat. Cette compétence sert à vérifier une procédure plutôt qu'à faire confiance à une sortie plausible.

Niveau : débutant. Il suffit de comparer des nombres entiers et de lire une suite ordonnée de valeurs, appelée ici une liste. Les nombres négatifs sont permis. Aucun langage de programmation n'est requis : commencez sur papier. Le passage au code est une application, pas un prérequis caché.

2. Définir le problème avant la méthode

Nous cherchons la plus grande valeur d'une liste finie non vide d'entiers. L'entrée peut contenir des répétitions et n'a pas besoin d'être triée. La sortie est une valeur, pas sa position ni le nombre de fois où elle apparaît. Pour [3, 7, 7, 2], le résultat attendu est 7.

La condition « non vide » est une précondition : elle précise les entrées autorisées. La postcondition exprime le résultat exigé : la sortie appartient à la liste et elle est supérieure ou égale à chacune de ses valeurs. Sur une liste vide, il n'existe aucun maximum à retourner. Une procédure destinée à accepter aussi ce cas devrait définir explicitement une erreur ou un autre résultat ; elle ne devrait pas inventer zéro.

3. Construire une procédure sans ambiguïté

Gardez un candidat nommé best. Initialisez-le avec la première valeur, puis parcourez les autres dans leur ordre. Si la valeur examinée est strictement supérieure à best, remplacez best par cette valeur. Sinon, conservez-le. Après la dernière valeur, retournez best.

L'affectation change une valeur mémorisée : best ← x signifie « mémoriser la valeur actuelle de x dans best ». Ce n'est pas une équation valable pour toujours. Une condition choisit l'action ; une boucle répète les étapes pour les valeurs restantes. L'ordre, l'initialisation et la condition font partie de la méthode, autant que le résultat final.

best ← première valeur de la liste
pour chaque valeur x après la première :
    si x > best :
        best ← x
retourner best

Ce texte est du pseudocode : il décrit la méthode sans imposer la syntaxe d'un langage. Il ne faut pas le coller tel quel dans un interpréteur Python.

Illustration générée avec une assistance d’intelligence artificielle. Elle suggère le rôle de la mémoire ; la trace numérique exacte et sa justification sont données dans le texte et le tableau.

4. Suivre un exemple résolu

Pour [3, 7, 7, 2], l'initialisation donne best = 3. Il reste trois valeurs à comparer.

La seconde occurrence de 7 ne change pas la valeur du maximum. Le résultat est 7 après exactement trois comparaisons. Avec une seule valeur, la boucle ne s'exécute pas et cette valeur est retournée. Compter les comparaisons n'est pas mesurer le temps réel d'exécution : ce dernier dépend aussi du programme et de la machine.

5. Justifier la correction et la terminaison

Après chaque étape, best est le maximum de la partie déjà parcourue. Cette propriété conservée s'appelle un invariant. Elle est vraie au départ, puisque la partie parcourue ne contient que la première valeur. Si la valeur suivante est plus grande, la remplacer préserve la propriété ; sinon, conserver le candidat la préserve aussi. À la fin, la partie parcourue est toute la liste : la postcondition est donc satisfaite.

Une liste finie de n valeurs laisse n − 1 valeurs après la première. Chaque étape en traite une, sans revenir en arrière : le nombre restant diminue jusqu'à zéro. Cela justifie la terminaison et n − 1 comparaisons, même si toutes les valeurs sont égales. Les tests d'exemples peuvent révéler une erreur ; ils ne remplacent pas cette justification pour toutes les entrées autorisées.

6. Traduire en programme Python

Voici une traduction pour une liste non vide d'entiers. values[0] désigne sa première valeur ; range(1, len(values)) parcourt les indices après elle. L'indentation délimite la boucle et la condition.

def maximum(values):
    best = values[0]
    for i in range(1, len(values)):
        x = values[i]
        if x > best:
            best = x
    return best

Cette fonction suppose la précondition satisfaite. Elle ne constitue pas une interface complète de validation d'entrées : la liste vide provoque une erreur à l'accès values[0]. Les valeurs manquantes, les mélanges de types et les listes infinies sortent du problème défini. Avant de la réutiliser, préciser le contrat et le traitement des entrées refusées. Le code vise la compréhension de la méthode ; en pratique, une fonction intégrée de maximum peut être préférable.

7. Exercice guidé

Tracer une recherche de maximum

Pour [5, 1, 9, 3], exécutez la procédure à la main. Construisez un tableau avec la valeur examinée, best avant et best après ; indiquez la sortie et le nombre de comparaisons.

Critère de réussite : La trace initialise best avec la première valeur, examine chaque autre valeur une fois et explique la décision à chaque comparaison.

Correction guidée, à consulter après votre tentative : le candidat commence à 5 ; après 1, 9 et 3 il vaut successivement 5, 9 et 9. Trois comparaisons conduisent à la sortie 9. Chaque ligne doit rendre visibles la valeur examinée, le candidat avant et le candidat après ; une sortie correcte seule ne suffit pas à expliquer le raisonnement.

8. Projet proportionné

Spécifier et tester une procédure

Pour [12, 8, 15, 15, 4], rédigez la précondition et la postcondition, tracez le maximum et justifiez la terminaison. Ajoutez les tests [-4, -2, -9], [6] et [3, 3]. Expliquez le traitement prévu pour une liste vide et pourquoi initialiser à zéro est dangereux.

Critère de réussite : Le livrable contient un contrat explicite, les quatre traces, un argument d'invariant et une justification de fin. Il distingue les entrées autorisées du cas vide refusé.

Travaillez d'abord sur papier. Si vous utilisez ensuite le programme, comparez sa sortie à votre trace. Une égalité sur ces quelques cas est une vérification limitée ; conservez aussi l'argument d'invariant et la justification de terminaison. Le livrable est une petite spécification accompagnée des traces et des tests, sans collecte de données personnelles.

9. Évaluation de transfert

Transférer la méthode à un minimum

Adaptez la procédure pour chercher le minimum d'une liste finie non vide d'entiers. Donnez le pseudocode, tracez [6, -1, 4, -1] et expliquez la propriété conservée et la terminaison. Trouvez un contre-exemple à l'initialisation à zéro, puis précisez pourquoi une liste vide reste hors contrat.

Critère de réussite : La méthode fonctionne pour tout le domaine annoncé, traite les répétitions et le singleton, sépare test et preuve, et justifie initialisation, comparaison et fin sans reprendre une règle mémorisée sans explication.

Rédigez votre justification sans notes, en expliquant chaque choix. Comparez ensuite votre méthode à la recherche de maximum : quelles étapes se conservent et quelle décision change ?

10. Limites et erreurs fréquentes

Initialiser best à zéro semble fonctionner pour certaines listes positives, mais échoue sur [-4, -2, -9] : le programme retourne alors 0, qui n'appartient même pas à l'entrée. Initialiser avec la première valeur évite cette hypothèse cachée. Une liste singleton et des répétitions sont des cas autorisés, pas des anomalies.

Le maximum d'une liste n'est ni sa somme ni une valeur nécessairement unique dans la liste. Un algorithme peut être correct sans être le seul possible. Une autre méthode pourrait trier avant de choisir le dernier élément, mais cela ajoute un travail inutile pour cette seule question. Cette unité ne prouve pas qu'une procédure quelconque termine, ni qu'un programme quelconque respecte sa méthode : ces deux propriétés exigent leurs propres arguments.

11. Synthèse, rappel actif et prochaine étape

La démarche est : définir le contrat, choisir une méthode, tracer un cas, justifier la propriété conservée et la fin, puis vérifier la traduction. Une sortie plausible n'est pas une preuve générale. Reprenez demain, sans relire, ces quatre questions :

1. Quelle différence faites-vous entre un algorithme et un programme ?
2. Pour [2, 5, 4], quelles valeurs prend le candidat et combien de comparaisons sont faites ?
3. Pourquoi l'initialisation à zéro échoue-t-elle pour certaines entrées ?
4. Expliquez à un débutant pourquoi la procédure termine sur toute liste finie non vide.

Référence courte : la méthode est distincte de sa traduction ; la trace commence à 2, devient 5 puis reste 5, avec deux comparaisons. Zéro impose à tort une borne inférieure aux valeurs. Le nombre d'éléments restant à traiter diminue de un jusqu'à zéro.

Prochaine étape proposée : comparer la recherche d'une valeur dans une liste à la recherche de son maximum. Aucun cours suivant n'est encore désigné : cette racine reste ouverte à une extension du cursus, après qualification du graphe.

12. Sources et méthode éditoriale

Cette unité originale rapproche deux programmes institutionnels indépendants : le programme français de numérique et sciences informatiques, première, BO du 22 janvier 2019, annexe p. 8 « Langages et programmation » et p. 9 « Algorithmique », et le programme anglais de computing, 2013, « Key stage 2 » et « Key stage 3 ». Sources relues le 12 octobre 2026. L'alignement porte sur spécification, séquence, sélection, répétition, tests et justification ; il ne certifie pas la couverture intégrale de ces programmes.

Le texte, les exemples et les activités ont été préparés avec une assistance d'intelligence artificielle. Les traces et les cas de calcul doivent être contrôlés, ainsi que les huit versions linguistiques, avant livraison publique. Aucun gain d'apprentissage ni contrôle humain n'est revendiqué.