Algorithmique en Terminale NSI : arbres, graphes, tri et recherche

Un arbre binaire est soit vide, soit un nœud composé d’une valeur, d’un sous-arbre gauche et d’un sous-arbre droit. La représentation du cours est donc None ou le tuple (valeur, gauche, droite). Deux mesures se déduisent de cette définition. La taille vérifie taille(vide)=0 et taille(nœud)=1+taille(gauche)+taille(droite). La hauteur compte les arêtes du plus long chemin : hauteur(vide)=−1 et hauteur(nœud)=1+max(hauteur(gauche),hauteur(droite)). Une feuille a ainsi hauteur 0, sans convention cachée.

Un parcours répond à une autre question : dans quel ordre lis-tu les nœuds ? Préfixe lit racine, gauche, droite. Infixe lit gauche, racine, droite. Suffixe lit gauche, droite, racine. La largeur utilise une file : elle retire tous les nœuds d’un niveau avant le suivant. Ces quatre sorties ne sont pas quatre écritures du même résultat ; elles servent à rendre visible une décision de lecture.

Sur l’arbre A de racine 4, avec 2 et 6 comme fils, puis 1,3,5,7 comme feuilles, taille(A)=7 et hauteur(A)=2. Préfixe rend 4,2,1,3,6,5,7. Infixe rend 1,2,3,4,5,6,7. Suffixe rend 1,3,2,5,7,6,4. Largeur rend 4,2,6,1,3,5,7. Compare ces quatre listes : la structure est identique, seul le moment où une racine est produite change.

La récursion est justifiée par la forme de l’arbre. Pour une mesure ou un parcours, chaque appel non vide délègue aux deux sous-arbres, qui ont une profondeur plus petite. Les cas vides ferment les branches. Le programme n’a pas besoin de deviner où finir : la structure fournit à la fois le cas de base et la décomposition. Une trace de largeur, elle, montre la file restante après chaque retrait, ce qui explique pourquoi 2 et 6 précèdent 1 et 3.

Avant de raisonner, le laboratoire vérifie que chaque nœud est bien un tuple ternaire, que les valeurs sont des entiers stricts et qu’aucune référence cyclique ne transforme une prétendue structure en boucle. Cette validation protège les données d’entrée. Le noyau de taille, hauteur ou parcours suit ensuite directement les formules ci-dessus. Distinguer contrôle de forme et calcul rend l’erreur lisible sans cacher le mécanisme de l’arbre. Le laboratoire accepte une hauteur de −1 à 8 et des valeurs entières de −1000 à 1000 ; un même sous-arbre partagé à deux emplacements est compté deux fois, comme deux branches. Avec deque, le retrait de file ne décale pas tous les éléments. Sans les instantanés, ces parcours visitent chacun des n nœuds en O(n) ; conserver une copie de la sortie après chaque retrait peut en revanche prendre O(n²) places dans la trace.

Un ABR est un arbre binaire auquel s’ajoute un invariant d’ordre : toute clé du sous-arbre gauche est strictement inférieure à la racine, toute clé du sous-arbre droit lui est strictement supérieure. Chercher 5 dans une racine 4 n’examine donc pas la gauche : 5 ne peut s’y trouver. À chaque comparaison, un sous-arbre entier, pas nécessairement la moitié des nœuds est écartée parce que l’invariant l’autorise, non parce qu’un parcours serait magique.

L’insertion suit exactement le même chemin. Dans l’ABR 4,2,6, insérer 3 compare 3 à 4, va à gauche ; compare 3 à 2, va à droite ; la place vide devient le nœud 3. Avec le contrat du cours, une clé égale est ignorée : insérer 3 une seconde fois rend le même arbre. Le retour de nouveaux tuples conserve l’ancien arbre, ce qui permet de vérifier qu’une insertion ne l’a pas muté.

Le noyau recherche ou insertion suit un chemin de longueur h, où h est la hauteur : son nombre de comparaisons est au plus h+1, donc O(h+1). Si l’arbre est équilibré, h est de l’ordre de log n ; si les clés 1,2,3,4 sont insérées dans cet ordre, l’arbre est une chaîne et h=3. Il ne suffit donc pas de dire « ABR, donc logarithmique ». La validation avant la recherche ou l’insertion, puis le contrôle du résultat de l’insertion, parcourent la structure entière. La prévalidation complète de l’objet du laboratoire peut parcourir tous ses nœuds et être linéaire ; elle protège le contrat, mais ne change pas le raisonnement sur le noyau de recherche une fois la structure validée.

L’infixe est un contrôle adapté à l’invariant : gauche, racine, droite rend les clés croissantes pour un ABR valide. Il ne prouve pas à lui seul que la forme est équilibrée. Inversement, une hauteur faible ne vérifie pas l’ordre des clés. Lis l’infixe et mesure la hauteur pour répondre à deux questions distinctes : « les comparaisons éliminent-elles la bonne branche ? » et « quelle longueur peut avoir ce chemin ? »

Les clés sont des entiers stricts et bornés dans le laboratoire ; True, NaN et une valeur non comparable ne deviennent pas des clés par accident. Les cas utiles sont l’arbre vide, la feuille, une clé absente, un doublon et l’ordre d’insertion trié. Chaque cas éclaire une partie précise du contrat. Le test ne remplace pas l’invariant : il vérifie que les exemples observables restent cohérents avec lui. Pour garder la récursion lisible, une construction accepte au plus 100 clés et un arbre fourni a une hauteur d’au plus 100. Un résultat d’insertion dépassant cette hauteur est refusé ; le constructeur peut donc toujours traiter ses 100 clés.

Un graphe associe à chaque sommet ses voisins. Le laboratoire utilise un dictionnaire de 1 à 100 sommets nommés par des chaînes de 1 à 20 caractères ; tous les voisins doivent être déclarés, sans boucle sur soi ni voisin répété. L’ordre des listes de voisins est conservé. La largeur marque un sommet quand il entre dans la file. La profondeur conserve, dans une pile de cadres, le sommet courant et les voisins qu’il reste à examiner : elle descend vers un seul voisin non visité avant de revenir aux autres.

Depuis A dans le graphe A→B, A→C, B→D, C→D, la largeur commence avec la file [A]. Elle retire A, marque B et C, puis sa file est [B,C]. Elle retire B, marque D, puis sa file est [C,D]. Elle retire C sans réinsérer D, enfin D. La trace A,B,C,D montre les niveaux : A est à distance 0, B et C à distance 1, D à distance 2. A est le parent de B et de C ; B est ici le premier parent enregistré de D.

La profondeur du cours suit A,B,D,C : le cadre de A garde C en attente pendant la descente dans B puis D. Le sommet est marqué quand son cadre est empilé, avant l’exploration de ses propres voisins. Il ne sera donc pas visité une seconde fois. Cette implantation reproduit une exploration récursive complète ; empiler tous les voisins d’un coup en les marquant immédiatement peut produire un autre arbre de parcours. Contrairement à la largeur, la profondeur ne garantit pas que son premier chemin vers un sommet minimise le nombre d’arêtes.

Pourquoi le premier chemin de largeur est-il minimal en nombre d’arêtes ? Tous les sommets à distance k sont retirés avant les sommets à distance k+1. Quand D reçoit son premier parent B, B est au niveau 1 : le chemin A,B,D a donc deux arêtes. Aucun chemin vers D d’une arête n’existe, car seuls B et C étaient voisins de A. Le dictionnaire parents permet de remonter D,B,A puis d’inverser la liste. La fonction renvoie None pour une arrivée déclarée mais inaccessible. Si départ et arrivée sont identiques, elle renvoie le chemin à un seul sommet. Un nom non déclaré provoque ValueError.

Le cycle du laboratoire est non orienté. Il vérifie donc que chaque arête est symétrique. Pendant une profondeur, atteindre un voisin déjà vu signale un cycle si ce voisin n’est pas le parent par lequel on est arrivé ; l’arête de retour vers ce parent est normale. Cette règle ne s’importe pas telle quelle dans un graphe orienté. Teste séparément une chaîne, un sommet isolé, un cycle, deux composantes et un graphe non fermé : ce sont des modèles qui mettent l’invariant à l’épreuve. La file deque et la pile de cadres permettent au noyau de visiter chaque sommet et chaque arc une fois, soit O(V+E). Le contrôle de symétrie affiché utilise des recherches dans les tuples de voisins ; son coût préalable est distinct et peut être plus élevé.

Diviser pour régner suit trois gestes : diviser une suite, résoudre les moitiés, puis combiner leurs résultats. Tri fusion s’arrête sur une suite de longueur zéro ou un, déjà triée. Le cas vide est indispensable : si une suite vide était encore divisée, la taille ne diminuerait plus. Le variant est la longueur de la partie traitée ; chaque appel non terminal le réduit.

La fusion est le cœur de la correction. Elle reçoit deux suites déjà triées, compare leurs têtes et ajoute la plus petite à la sortie. Son invariant est double : la sortie est triée, et elle contient exactement les occurrences consommées des deux entrées. Quand une moitié est épuisée, l’autre fin est déjà triée et peut être ajoutée sans comparaison supplémentaire. Cette justification locale est réutilisée à chaque remontée récursive.

Pour fusionner 1,4 et 2,3, comparer 1 et 2 donne 1 ; comparer 4 et 2 donne 2 ; comparer 4 et 3 donne 3 ; puis 4 restant est ajouté. La sortie est 1,2,3,4 et trois comparaisons ont été nécessaires à cette fusion. Sur 4,1,3,2, les deux petites fusions ajoutent encore une comparaison chacune : la trace entière compte donc cinq comparaisons, pas quatre.

La stabilité concerne des objets dont les clés peuvent être égales. Si la tête gauche et la tête droite ont la même clé, choisir la gauche avec <= conserve l’ordre relatif des occurrences. Des entiers seuls ne permettent pas de le voir : les paires (2,'gauche') et (2,'droite') le montrent. Le noyau numérique du laboratoire garde des entiers stricts pour son contrat ; le transfert étiqueté isole l’observation de stabilité sans brouiller ce domaine.

Il y a environ log₂ n niveaux de division et, à chaque niveau, les fusions parcourent au total n valeurs : le pire cas est donc de l’ordre de n log₂ n. Cette formule décrit la croissance du travail, non un chronomètre. Une trace et des tests sur vide, singleton, doublons, ordre inversé et ordre déjà trié relient enfin cette analyse au comportement concret. L’entrée accepte au plus 100 entiers de −1000 à 1000. Le noyau avec fusions et copies usuelles a un pic de mémoire auxiliaire O(n), hors pile O(log n). Cette version conserve toutefois les entrées et sorties de toutes les fusions dans trace : leur volume total peut atteindre O(n log n). Supprimer ce journal après observation n’est donc pas une modification de l’algorithme de tri, mais de sa mémoire d’observation.

La programmation dynamique s’emploie lorsque plusieurs choix ramènent aux mêmes sous-problèmes. Pour rendre un montant M, on pourrait essayer toutes les suites de pièces, mais beaucoup de branches demanderaient de nouveau de rendre la même somme. On définit donc opt[a] comme le nombre minimal de pièces pour rendre a. La base est opt[0]=0 ; None signale une somme impossible, ce qui n’est pas la même chose que zéro pièce.

Pour une pièce p≤a, si la somme a−p est possible, ajouter p donne une candidate opt[a−p]+1. La récurrence est donc opt[a]=min(1+opt[a−p]) sur les candidats possibles, ou None s’il n’en existe aucun. Les pièces sont strictement positives : a−p<a, donc un remplissage par montants croissants dispose toujours des cases nécessaires. La justification d’optimalité vient du dernier choix : retirer la dernière pièce d’une solution optimale laisse une solution optimale de la somme restante, sinon on pourrait améliorer l’ensemble.

Avec les pièces 1,3,4, les nombres de pièces pour les montants 0 à 6 sont 0,1,2,1,1,2,2. À la case 6, choisir 1 complète la case 5 et donne trois pièces ; choisir 3 complète la case 3 et donne deux pièces ; choisir 4 complète la case 2 et en donne trois. On garde donc 3, puis on remonte de 6 à 3 et de 3 à 0 : la solution est (3,3). La stratégie gloutonne aurait pris 4, puis 1,1 et aurait utilisé une pièce de trop.

Le nombre minimal ne suffit pas à dire quelles pièces rendre. La table derniere conserve la pièce qui a donné chaque amélioration stricte ; le prédécesseur est alors a−derniere[a]. À égalité, la première pièce essayée est conservée, donc la plus petite puisque les pièces sont triées. Pour 5, choisir 1 après la solution de 4 ou choisir 4 après celle de 1 donne deux pièces : on conserve 1 et la reconstruction renvoie (1,4), dans le sens montant→zéro. Plusieurs solutions optimales peuvent exister sans rendre le résultat incorrect.

Pour k valeurs de pièces et un montant M, le noyau examine au plus kM candidats. Les deux tables occupent O(M) cases et la reconstruction au plus M étapes si la pièce 1 est disponible. Cette version stocke nombres et prédécesseurs, pas une copie de toute la solution dans chaque case. Le laboratoire accepte de 1 à 9 pièces entières distinctes comprises entre 1 et 9, triées, et un montant entier de 0 à 30. Les bornes rendent les tables faciles à inspecter ; elles ne sont pas une limite théorique de la méthode.

Le transfert passe à un autre problème : une plus longue sous-séquence commune. Une sous-séquence conserve l’ordre, mais peut sauter des éléments ; elle n’est ni un ensemble ni nécessairement un bloc contigu. Cette fois les sous-problèmes dépendent de deux préfixes, donc la mémoire prend la forme d’un tableau à deux dimensions. La même démarche reste utile : définir exactement une case, expliquer les transitions, puis reconstruire un témoin de la longueur calculée.

Horspool cherche ici la première occurrence exacte d’un motif non vide dans un texte ASCII majuscule. Le domaine est volontairement fermé : pas de normalisation Unicode, pas de liste de caractères, pas de convention silencieuse pour le motif vide. La fonction rend l’indice 0 si le motif commence le texte, et −1 s’il est absent. Si le motif est plus long que le texte, aucune fenêtre n’est possible et le résultat est −1. Le texte peut être vide et contient au plus 50 lettres ; le motif en contient de 1 à 10. Ces limites de laboratoire gardent les traces courtes.

Pour le motif ABC de longueur 3, la table prépare A→2 et B→1, leurs distances à la dernière position, et donne 3 pour les autres caractères. Le dernier C est exclu du prétraitement pour éviter un saut nul. Après un échec, on lit la lettre x du texte sous la fin du motif. Une occurrence plus loin devrait replacer cette même lettre sur une position compatible du motif : la plus proche est son occurrence la plus à droite avant la fin. On peut donc sauter directement jusqu’à elle ; si x n’y figure pas, les trois alignements partiels sont impossibles et le saut vaut la longueur du motif. Des lettres répétées imposent de conserver l’occurrence préparée la plus à droite.

Dans ABAAABCD, la fenêtre 0 compare d’abord A à C et échoue. Le A placé sous la fin possède le décalage 2, donc la fenêtre suivante commence à 2. Elle échoue encore sur A et saute de nouveau de 2. À l’offset 4, la comparaison de droite à gauche réussit sur C, puis B, puis A : le résultat est 4. La trace est alignements (0,2,4) et sauts (2,2). Aucun saut ne suit ce succès.

La borne de boucle start≤n−m inclut la dernière fenêtre légitime. Elle évite le défaut classique qui oublie un motif placé exactement à la fin du texte. Le tableau de sauts est une préparation du motif ; la comparaison de droite à gauche et le saut sous la fin sont les mécanismes que tu dois pouvoir expliquer sur une fenêtre, pas une formule de coût à réciter.

Horspool est la variante de recherche étudiée ici. Boyer-Moore peut aussi exploiter le caractère au point d’échec et un bon suffixe déjà reconnu ; ces tables ont des règles distinctes. Le prétraitement de Horspool parcourt le motif en O(m) et peut épargner beaucoup d’alignements, mais son pire cas reste O(nm) comparaisons, par exemple sur un texte répétitif avec un motif presque concordant. Le transfert compte séparément comparaisons et alignements, sans chronomètre, pour expliquer un gain sur un exemple et un contre-exemple sans annoncer une supériorité universelle.