Algorithmique : parcourir, trier, chercher et justifier

Imagine une rangée de casiers numérotés à partir de zéro. Pour trouver une valeur sans information d’ordre, ouvre les casiers un à un. La recherche séquentielle rend ici l’indice de la première occurrence, ou None si elle est absente. Elle s’applique aussi à des chaînes ou à des tuples dès lors que leur égalité a le sens attendu. Un indice nul est un résultat valide : teste indice is not None, pas simplement if indice.

Avant de tester la case i, l’invariant est : « la cible n’apparaît dans aucune case d’indice strictement inférieur à i ». Au début, le préfixe est vide, donc la propriété est vraie. Si la case i est différente, elle rejoint le préfixe écarté ; sinon le retour donne une occurrence. À la fin, tout le tableau a été écarté : None est justifié. Le nombre de cases restantes diminue, ce qui explique aussi l’arrêt.

Pour un extremum, le candidat est une valeur du tableau et reste le plus petit ou le plus grand élément du préfixe traité. Pour une moyenne, la somme partielle est celle de ce préfixe ; on divise seulement à la fin par l’effectif total. Le tableau vide est accepté par la recherche, mais refusé pour le résumé. Celui-ci accepte des int ou float, pas des booléens ; nombres non finis et calcul flottant non représentable sont refusés. Un résultat décimal peut être approché.

Une recherche lit au mieux une case et au pire n cases ; un résumé complet lit les n valeurs. Le coût du parcours est linéaire si une comparaison et une opération numérique ont un coût unitaire. Ce modèle ne mesure pas les secondes et ne décrit pas le coût en bits de très grands entiers. La trace de recherche stocke au plus n lignes ; elle réutilise le résultat du test au lieu d’effectuer deux égalités.

Comme pour ranger des cartes dans ta main, prends la première valeur encore à traiter et insère-la parmi celles déjà rangées. À l’étape i, la clé est la valeur de la case i ; les valeurs strictement plus grandes sont décalées vers la droite. La clé, mise à l’abri dans une variable, est écrite dans la place libérée. La solution retourne une nouvelle liste : l’entrée n’est pas modifiée.

Avant l’étape i, les cases d’indices 0 à i−1 sont triées et contiennent exactement les valeurs initiales de ce préfixe, avec leurs répétitions. Ce n’est pas forcément l’ensemble des plus petites valeurs de tout le tableau. Après insertion de la clé, la propriété s’étend à i+1 cases. Elle est vraie au départ pour une seule case et donne tout le tableau trié à la fin. Pendant les décalages, la liste peut temporairement contenir une valeur deux fois : la clé conservée dans la variable et la place à remplir font partie de l’état.

La boucle extérieure parcourt une plage finie. À l’intérieur, j+1 est un entier positif tant que la place n’est pas trouvée ; chaque décalage le diminue d’une unité. La boucle s’arrête donc. Le test strict tableau[j] > cle ne fait pas passer une clé devant une valeur égale. Si l’on adapte les comparaisons à une clé d’enregistrement, cette méthode conserve ainsi l’ordre des ex æquo : c’est la stabilité.

Le laboratoire accepte une liste ou un tuple d’entiers, hors booléens. Il distingue comparaisons entre valeurs et décalages. Une liste déjà triée de n valeurs exige n−1 comparaisons et zéro décalage pour n≥1. En ordre strictement décroissant, les deux compteurs valent 1+2+…+(n−1), soit n(n−1)/2. Les vérifications d’indices et de types ne sont pas incluses dans ces compteurs. Les copies de préfixes de la trace ajoutent un coût quadratique, même sur une entrée triée : utilise tracer=False pour étudier le temps du tri sans ces instantanés. Sans trace, le cas déjà trié est linéaire, validation et copie d’entrée comprises.

La sélection procède autrement : à la position i, cherche le minimum parmi les cases i à n−1, puis échange-le avec la case i s’il n’y est pas déjà. L’indice du candidat minimum commence à i, jamais systématiquement à zéro. Ainsi le préfixe déjà fixé n’est plus déplacé. La solution copie l’entrée avant les échanges.

Avant l’étape i, le préfixe contient i plus petites valeurs du tableau initial, dans l’ordre, en tenant compte des répétitions. L’invariant ajoute que le tableau complet conserve toutes ses valeurs. Le préfixe vide vérifie la propriété ; choisir le minimum restant la prolonge d’une case. Après n−1 étapes, la dernière valeur est aussi à sa place. Dans la boucle intérieure, le candidat est le minimum de la partie du suffixe déjà examinée. Les deux boucles parcourent des plages finies, ce qui établit leur terminaison. Une entrée vide ou réduite à une valeur est déjà triée et ne demande aucune étape.

Pour n valeurs, la boucle intérieure fait n−1 comparaisons, puis n−2, jusqu’à 1 : exactement n(n−1)/2 comparaisons entre valeurs, quel que soit l’ordre initial. Ce sont les nombres de comparaisons qui sont identiques, pas forcément les paires de valeurs comparées. Le nombre d’échanges varie de zéro à n−1 pour n≥1. Une entrée déjà triée évite les échanges mais pas la recherche des minimums. Comme pour l’insertion, la validation de types et les copies de trace sont hors compteur ; tracer=False supprime les instantanés.

Ne confonds pas petit nombre d’échanges et stabilité. Imagine des enregistrements de clés [2A, 2B, 1C], où la lettre identifie l’enregistrement et seule la valeur numérique est comparée. Le premier échange donne [1C, 2B, 2A] : les deux clés 2 ont changé d’ordre. La sélection par échange n’est donc pas stable en général. Les nombres seuls du laboratoire ne permettent pas de voir cette différence d’identité.

Dans un tableau trié par ordre croissant, compare la cible à la valeur du milieu. Si elle est plus grande, la cible ne peut être dans la moitié gauche ni au milieu ; sinon, si elle est plus petite, écarte la moitié droite et le milieu. Les bornes gauche et droite sont inclusives. Une égalité rend l’indice trouvé ; avec des répétitions, ce n’est pas nécessairement celui de la première occurrence.

L’invariant est : « si la cible apparaît dans le tableau initial, une occurrence demeure dans la zone encore examinée, tant qu’aucun résultat n’a été rendu ». Il est vrai pour la zone initiale complète. L’ordre justifie chaque exclusion et conserve cette propriété. Quand gauche dépasse droite, la zone est vide : aucune occurrence n’a pu y rester, donc la cible est absente. Ce raisonnement exige que le tableau soit trié et ne soit pas modifié pendant la recherche.

Le variant est la taille de la zone, droite−gauche+1. Elle est positive au début d’un tour et chaque nouvelle borne exclut au moins le milieu. Elle décroît strictement et ne devient pas négative avant la sortie : cela prouve l’arrêt. Pour expliquer le coût logarithmique, il faut plus que la décroissance : chaque tour non concluant garde au plus la moitié des cases. Pour n≥1, au plus floor(log₂(n))+1 positions sont examinées. Un tour peut réaliser un test d’égalité puis un test d’ordre ; tours et comparaisons ne sont donc pas interchangeables.

Le code sépare deux usages. rechercher_dans_tableau_trie suppose une liste ou un tuple d’entiers déjà validé et trié ; il ne parcourt pas toute l’entrée avant de chercher. recherche_dichotomique est la version vérifiée : elle appelle d’abord verifier_tableau_trie, puis le noyau. Vérifier l’ordre exige n−1 comparaisons voisines pour une entrée triée non vide : l’appel vérifié complet est linéaire, pas logarithmique. Pour plusieurs recherches, valide une fois un tableau qui restera inchangé, puis appelle le noyau. Trier préalablement aurait encore un coût distinct.

k-NN est une méthode de classification supervisée : chaque exemple possède des caractéristiques et une classe connue. Pour un nouveau point, calcule ses distances aux exemples, retiens les k plus proches, puis compte leurs classes. Ici le point a deux coordonnées numériques finies, la classe est une chaîne non vide et k est un entier de 1 à l’effectif, sans booléen. Le code refuse les coordonnées absentes et les calculs de distance non représentables. Il utilise uniquement des points synthétiques, pas des profils d’élèves.

Dans le plan muni de deux axes de même unité, la distance euclidienne au carré est d² = (x₁−x₂)² + (y₁−y₂)². La racine carrée est croissante sur les nombres positifs : comparer d² donne le même ordre que comparer d, sans la calculer. Il faut bien deux coordonnées par point ; zip seul pourrait ignorer silencieusement une coordonnée manquante. Les carrés empêchent aussi l’annulation d’écarts de signes contraires. Dans le code, les coordonnées sont converties en flottants : les calculs peuvent être arrondis. Une égalité de distances désigne ici l’égalité des résultats calculés.

Deux égalités demandent des règles différentes. À distance égale, le tri stable conserve ici l’ordre des exemples d’entrée, y compris à la frontière du k-ième voisin. À égalité de votes, le code choisit la classe la plus petite selon l’ordre lexicographique Python. Ces conventions rendent le calcul reproductible, pas neutre. Avec plus de deux classes, un k impair n’empêche même pas toutes les égalités de votes. Le résultat fournit les voisins et les effectifs pour que tu puisses expliquer la décision.

L’échelle change la proximité. Pour le point (0, 0), compare un exemple A en (0, 1000) à un exemple B en (2, 0) : leurs d² valent 1 000 000 et 4, donc k=1 propose B. Si tu divises la seconde caractéristique de tous les points par 1000, les d² deviennent 1 et 4 : A est proposé. Ce choix d’échelle doit être justifié par les caractéristiques, pas choisi pour forcer une réponse. La méthode fait ici un parcours des exemples puis un tri de toutes les distances ; un petit k ne signifie pas que seules k distances sont calculées.

Une majorité de voisins n’est pas une certitude sur la classe réelle et son pourcentage n’est pas automatiquement une probabilité fiable. Les étiquettes, les exemples retenus, les unités, k et les égalités influencent le résultat. Pour évaluer une prédiction, il faudrait des cas connus qui n’ont pas servi au réglage. Le petit jeu illustratif ci-dessous apprend à lire le calcul ; il ne mesure aucune performance sur une population réelle.

Une stratégie gloutonne choisit à chaque étape une option localement avantageuse, sans revenir sur ses choix. Pour rendre une somme avec des pièces fictives disponibles en quantité illimitée, la règle étudiée prend la plus grande valeur qui ne dépasse pas le reste. L’objectif est de minimiser le nombre de pièces ; obtenir la bonne somme est seulement la condition de validité. La somme est un entier positif ou nul, chaque valeur de pièce un entier strictement positif, sans booléens. Les doublons de valeurs sont sans effet ; l’ordre d’entrée n’impose pas l’ordre des choix.

Après chaque choix, « somme des pièces retenues + reste = somme initiale » est un invariant. Le reste est un entier non négatif qui diminue d’au moins un à chaque pièce ajoutée ; la boucle intérieure termine. La liste des valeurs possibles est finie. Si une pièce de valeur 1 existe, le glouton peut toujours terminer avec un reste nul. Sans elle, il peut échouer alors qu’une autre combinaison fonctionne : pour 6 avec [3, 4], prendre 4 bloque sur un reste de 2, mais 3+3 convient.

La validité ne prouve pas l’optimalité. Pour 6 avec [1, 3, 4], le glouton produit 4+1+1 en trois pièces ; 3+3 en utilise deux. Ce cas réfute l’affirmation « cette règle est optimale pour tous les systèmes ». Il ne prouve pas que tout algorithme glouton est mauvais. Pour [1, 2, 4], on peut au contraire justifier la règle : deux pièces de 1 se remplacent par une de 2 et deux pièces de 2 par une de 4. Un rendu minimal n’en conserve donc au plus qu’une de chaque petite valeur ; le choix glouton construit cette forme. Le reste fourni par ces petites pièces est alors entre 0 et 3 ; la somme fixe donc leur nombre et celui des pièces de 4.

Le laboratoire fournit aussi minimum_par_table, un outil de comparaison pour les petites sommes. Il mémorise le meilleur nombre de pièces pour chaque montant de 0 à la cible, puis reconstruit un rendu. Pour un montant m, toute solution non vide se termine par une pièce p et une solution du montant m−p ; tester chaque p permet de choisir le meilleur total. Cette méthode est de la programmation dynamique, un prolongement fourni, pas une recherche exhaustive de toutes les combinaisons ni un attendu à mémoriser en Première.

Pour une somme S et d valeurs, la table examine au plus S×d transitions et stocke S+1 cases de coût ainsi que les choix. Le glouton trie les d valeurs puis ajoute autant de pièces que son résultat en contient. Cette mesure dépend de la valeur numérique de S, pas seulement du nombre de chiffres qui la représentent. Aucun chronométrage n’est déduit de ces comptes. Le projet limite ses montants et distingue un échec glouton, une impossibilité établie par la table et une solution trop longue.