1. Signature. La fonction prend une liste de nombres naturels et retourne une liste de nombres naturels:

$\text{next} : \text{liste}(\mathbb{N}) \to \text{liste}(\mathbb{N})$

Toute fonction définie par récurrence structurelle sur les listes a une signature de cette forme: la structure apparaît en entrée et en sortie, puisque chaque appel récursif en produit une.

2. Application à L = 3 · 2 · 10 · []. Le point de notation à fixer d'abord: dans el + 1 · next(L1), l'élément de tête du résultat est el + 1 — le · sépare la tête de la queue, il ne s'applique pas à 1. On déroule de la tête vers la queue:

1next(3 · 2 · 10 · [])2  el = 3,  L1 = 2 · 10 · []   ->  (3 + 1) · next(2 · 10 · [])3next(2 · 10 · [])4  el = 2,  L1 = 10 · []       ->  (2 + 1) · next(10 · [])5next(10 · [])6  el = 10, L1 = []            ->  (10 + 1) · next([])7next([])                      ->  []

En remontant: 11 · [] = [11], puis 3 · [11] = [3, 11], puis 4 · [3, 11] = [4, 3, 11].

$\text{next}(3 \cdot 2 \cdot 10 \cdot [\,]) = [4, 3, 11]$

En Python, la traduction est directe — le constructeur · devient la concaténation d'une liste à un élément avec le résultat récursif:

1def next_(L: list[int]) -> list[int]:2    if L == []:3        return []4    return [L[0] + 1] + next_(L[1:])5 6print(next_([3, 2, 10]))   # [4, 3, 11]

3. Preuve que taille(next(L)) = taille(L). Par récurrence structurelle sur L.

Base: L = []. Alors next([]) retourne [], et taille([]) = 0 = taille([]). La propriété est vraie.

Récurrence: L = el · L1, avec L1 une liste strictement plus petite. L'hypothèse de récurrence est taille(next(L1)) = taille(L1). On calcule:

1taille(next(L))  = taille([el + 1] + next(L1))     par définition de next2                 = 1 + taille(next(L1))            par définition de taille3                 = 1 + taille(L1)                  par hypothèse de récurrence4                 = taille([el] + L1)               par définition de taille5                 = taille(L)

La propriété est donc établie pour toute liste. ∎

1. Signature. Mistery prend une liste d'entiers et retourne une liste d'entiers:

$\text{Mistery} : \text{liste}(\mathbb{Z}) \to \text{liste}(\mathbb{Z})$

Le cas de base retourne la liste vide; le cas récursif retourne une liste construite à partir d'un élément et d'un appel récursif: le type de retour est donc bien une liste d'entiers.

2. Application à X = -5 · 16 · 14 · 3 · []. On descend jusqu'au cas de base, puis on remonte:

1Mistery(-5 · 16 · 14 · 3 · [])2  el = -5,  -5 > 10 ? non  ->  -5 · Mistery(16 · 14 · 3 · [])3Mistery(16 · 14 · 3 · [])4  el = 16,  16 > 10 ? oui  ->  Mistery(14 · 3 · [])5Mistery(14 · 3 · [])6  el = 14,  14 > 10 ? oui  ->  Mistery(3 · [])7Mistery(3 · [])8  el = 3,   3 > 10 ? non   ->  3 · Mistery([])9Mistery([])                ->  []

En remontant: 3 · [] = [3]; puis [3], [3], et enfin -5 · [3] = [-5, 3].

$\text{Mistery}(-5 \cdot 16 \cdot 14 \cdot 3 \cdot [\,]) = [-5, 3]$

La fonction est un filtre: elle conserve les éléments inférieurs ou égaux à 10 et supprime les autres.

1def mistery(X: list[int]) -> list[int]:2    if X == []:3        return []4    if X[0] > 10:5        return mistery(X[1:])          # élément écarté6    return [X[0]] + mistery(X[1:])     # élément conservé7 8print(mistery([-5, 16, 14, 3]))   # [-5, 3]

3. Preuve que taille(Mistery(X)) ≤ taille(X). Par récurrence structurelle sur X.

Base: X = []. Alors Mistery([]) = [] et taille(Mistery(X)) = 0 = taille(X). Vrai.

Récurrence: X = el · X1. L'hypothèse de récurrence est taille(Mistery(X1)) ≤ taille(X1). Deux cas:

• Si el > 10, alors Mistery(X) = Mistery(X1), donc

  $\text{taille}(Mistery(X)) = \text{taille}(Mistery(X_1)) \le \text{taille}(X_1) < \text{taille}(X)$

• Sinon Mistery(X) = el · Mistery(X1), donc

  $\text{taille}(Mistery(X)) = 1 + \text{taille}(Mistery(X_1)) \le 1 + \text{taille}(X_1) = \text{taille}(X)$

Dans les deux cas la propriété tient. ∎

1. Définition récursive. Un arbre binaire étiqueté par l'alphabet {A, B} se définit par:

1Base     : l'arbre vide ∅ appartient à AB2Récursion: si g et d appartiennent à AB, alors (A, g, d) et (B, g, d) appartiennent à AB

La base est l'arbre vide; les deux règles de construction correspondent aux deux étiquettes possibles. Rien d'autre n'appartient à AB — c'est le principe d'induction structurelle qui autorise à raisonner par récurrence sur ces objets.

2. Fonction de parité. On écrit une fonction qui retourne le nombre de A modulo 2, en suivant la forme de la définition:

1function pariteA(T)2  if T = ∅ then return 03  if T = (A, g, d) then return (1 + pariteA(g) + pariteA(d)) mod 24  if T = (B, g, d) then return (pariteA(g) + pariteA(d)) mod 2

L'appel récursif sur l'arbre vide retourne 0, qui est bien la parité du nombre de A dans l'arbre vide. En Python, l'arbre vide se représente par None:

1def parite_A(T) -> int:2    """Retourne 0 si le nombre de A est pair, 1 sinon."""3    if T is None:4        return 05    lettre, g, d = T6    contribution = 1 if lettre == 'A' else 07    return (contribution + parite_A(g) + parite_A(d)) % 28 9#         A10#        / \11#       B   A12arbre = ('A', ('B', None, None), ('A', None, None))13print(parite_A(arbre))   # 0 : deux A, donc pair

Justification. Le nombre total de A dans T = (l, g, d) vaut n_A(g) + n_A(d) plus 1 si l = A. Comme (x mod 2 + y mod 2) mod 2 = (x + y) mod 2, réduire modulo 2 à chaque étape est équivalent à réduire le total: la fonction retourne bien la parité du nombre de A. Sur l'arbre de l'exemple, il y a exactement deux A, donc la réponse est 0.

L'arbre de sortie a la même forme que l'arbre d'entrée: seule l'étiquette de chaque nœud change. La fonction ne parcourt donc pas l'arbre pour compter ou chercher, elle le reconstruit nœud par nœud.

1def voyelles_consonnes(T):2    """Arbre de même forme, où voyelle -> '1' et consonne -> '2'."""3    if T is None:4        return None                          # cas de base: arbre vide5    lettre, g, d = T6    remplacement = '1' if lettre.lower() in 'aeiouy' else '2'7    return (remplacement, voyelles_consonnes(g), voyelles_consonnes(d))8 9#         a10#        / \11#       b   e12arbre = ('a', ('b', None, None), ('e', None, None))13print(voyelles_consonnes(arbre))   # ('1', ('2', None, None), ('1', None, None))

Analyse.

• Signature: voyelles_consonnes : arbre(lettre) → arbre(caractère).
• Cas de base: l'arbre vide, qui se transforme en lui-même.
• Cas progressif: un nœud, dont on transforme l'étiquette puis les deux sous-arbres.
• Coût: chaque nœud est visité exactement une fois, donc Θ(n) où n est le nombre de nœuds.
• Terminaison: chaque appel récursif porte sur un sous-arbre strictement plus petit; on atteint donc nécessairement l'arbre vide.

Le test lettre.lower() traite les majuscules: 'A' est bien une voyelle. En pseudocode du cours, on écrirait simplement un test d'appartenance à l'ensemble des voyelles.

C'est exactement le même schéma que l'exercice précédent, avec une transformation numérique au lieu d'une substitution de lettre.

1function mul5(T)2  if T = [] then return []3  if T = T1 node T2 then return mul5(T1) node*5 mul5(T2)

En Python:

1def mul5(T):2    """Arbre de même forme, où chaque valeur est multipliée par 5."""3    if T is None:4        return None5    valeur, g, d = T6    return (valeur * 5, mul5(g), mul5(d))7 8arbre = (1, (2, None, None), (3, (4, None, None), None))9print(mul5(arbre))10# (5, (10, None, None), (15, (20, None, None), None))

Analyse. La fonction est une récursion structurelle: un cas de base (l'arbre vide) et un cas de construction (le nœud), avec un appel récursif par sous-arbre. Le coût est linéaire en nombre de nœuds, Θ(n), et la mémoire auxiliaire est en Θ(h) pour la pile d'appels, où h est la hauteur de l'arbre — c'est le seul coût caché de la récursion.

On peut vérifier que la forme de l'arbre est préservée: la fonction retourne un nœud partout où l'entrée avait un nœud, et None partout où l'entrée avait un sous-arbre vide. C'est la propriété qu'il faut énoncer si l'énoncé demande une preuve.

1function mul3(L)2  if L = [] then return []3  if L = node · L1 then return node*3 · mul3(L1)

En Python, avec les deux versions — récursive et itérative:

1def mul3(L: list[int]) -> list[int]:2    """Version récursive: suit la définition inductive de la liste."""3    if L == []:4        return []5    return [L[0] * 3] + mul3(L[1:])6 7def mul3_iteratif(L: list[int]) -> list[int]:8    """Version itérative: parcourt la liste et construit le résultat."""9    resultat = []10    for x in L:                 # invariant: resultat = 3 * elements deja traites11        resultat.append(x * 3)12    return resultat13 14print(mul3([1, 2, 3]))            # [3, 6, 9]

Preuve que taille(mul3(L)) = taille(L). Par récurrence structurelle. Base: mul3([]) = [], donc 0 = 0. Récurrence: mul3(node · L1) = [node × 3] + mul3(L1), donc taille = 1 + taille(mul3(L1)) = 1 + taille(L1) = taille(L) par hypothèse de récurrence. ∎

Version itérative. L'invariant de la boucle est: au début de l'itération traitant l'élément d'indice i, resultat contient les i premiers éléments de L, chacun multiplié par 3. Initialisation: resultat est vide avant la première itération. Conservation: on ajoute 3 × L[i]. Terminaison: après le dernier élément, resultat contient les n éléments transformés.

Les deux versions ont le même coût Θ(n), mais la version récursive consomme un cadre de pile par élément: sur une liste de plusieurs milliers d'éléments, elle lève RecursionError là où la boucle passe sans difficulté. La récursion est ici plus lisible parce qu'elle épouse la définition de la liste; elle n'est pas plus efficace.

L'ensemble Expr a deux constructeurs: un nombre (la base) et le produit de deux expressions (la règle). La fonction doit donc distinguer ces deux formes:

1function mul4(E)2  if E = n then return n*43  if E = E1 * E2 then return mul4(E1) * mul4(E2)

En Python, on représente une expression par un entier dans le cas de base, et par un couple (E1, E2) dans le cas récursif:

1def mul4(E):2    """Expression où chaque nombre est multiplié par 4."""3    if isinstance(E, int):4        return E * 4                    # cas de base: un nombre5    gauche, droite = E                  # cas récursif: un produit6    return (mul4(gauche), mul4(droite))7 8# ((2 * 3) * 4) représenté par ((2, 3), 4)9print(mul4(((2, 3), 4)))    # ((8, 12), 16)

Analyse. Le nombre d'appels récursifs est exactement le nombre de nœuds de l'arbre syntaxique de l'expression. Une expression construite par k applications de la règle E1 * E2 contient k + 1 nombres: c'est la propriété que l'on démontre par récurrence structurelle (voir l'exercice 8), et c'est elle qui garantit la terminaison — chaque appel récursif porte sur une sous-expression strictement plus petite.

Vérification sur l'exemple. mul4(((2,3),4)): la racine est le couple ((2,3), 4), donc mul4((2,3)) = (mul4(2), mul4(3)) = (8, 12) et mul4(4) = 16. Le résultat ((8,12), 16) correspond bien à (2×4 × 3×4) × 4×4.

On note #a(E) le nombre de symboles a dans E et #*(E) le nombre de symboles *. On démontre par récurrence structurelle sur E ∈ Expr que

$\#a(E) = \#*(E) + 1$

Base. E = a. Alors #a(E) = 1 et #*(E) = 0, d'où 1 = 0 + 1. La propriété est vraie.

Récurrence. E = E1 * E2, avec E1, E2 ∈ Expr. Les hypothèses de récurrence sont

$\#a(E_1) = \#*(E_1) + 1 \qquad \text{et} \qquad \#a(E_2) = \#*(E_2) + 1$

Par construction, les symboles de E sont ceux de E1, ceux de E2 et le * central, donc

$\#a(E) = \#a(E_1) + \#a(E_2) \qquad \text{et} \qquad \#*(E) = \#*(E_1) + \#*(E_2) + 1$

On calcule:

1#a(E) = #a(E1) + #a(E2)                     par construction2      = (#*(E1) + 1) + (#*(E2) + 1)         par hypothèse de récurrence3      = (#*(E1) + #*(E2) + 1) + 1           par associativité et commutativité4      = #*(E) + 1                           par construction

La propriété est donc établie pour toute expression. ∎

Vérification expérimentale. La même propriété se vérifie sur le code de l'exercice précédent: une expression est un arbre binaire dont les feuilles sont les nombres et les nœuds internes les produits.

1def nb_a(E) -> int:2    if E == 'a':3        return 14    gauche, droite = E5    return nb_a(gauche) + nb_a(droite)6 7def nb_etoiles(E) -> int:8    if E == 'a':9        return 010    gauche, droite = E11    return 1 + nb_etoiles(gauche) + nb_etoiles(droite)12 13# (a * a) * a14E = (('a', 'a'), 'a')

1. Définition récursive.

1Base     : toute lettre l de l'alphabet est un arbre (c'est une feuille)2Récursion: si g et d sont des arbres, alors (l, g, d) est un arbre

Un nœud porte une lettre et deux sous-arbres; une feuille est un nœud dont les deux sous-arbres sont vides.

2. Fonction. « Ajouter à chaque feuille l'élément [a] » se lit: sous chaque feuille, accrocher une nouvelle feuille étiquetée a. La feuille l devient donc le nœud (l, a, ∅).

1def ajoute_feuille(T):2    """Accroche une feuille 'a' sous chaque feuille de l'arbre."""3    if T is None:4        return None                          # un sous-arbre vide reste vide5    lettre, g, d = T6    if g is None and d is None:7        return (lettre, ('a', None, None), None)   # la feuille reçoit un fils8    return (lettre, ajoute_feuille(g), ajoute_feuille(d))9 10def hauteur(T) -> int:11    """Hauteur: arbre vide -> -1, feuille -> 0."""12    if T is None:13        return -114    _, g, d = T

Le point délicat est le traitement de l'arbre vide: il ne faut pas lui accrocher de feuille, sinon on ajouterait un fils à des sous-arbres vides et l'arbre changerait de forme. Le cas de base de la fonction est donc T is None → None, et le cas « feuille » est traité à part.

3. Preuve que h(T') = h(T) + 1. On note T' le résultat de ajoute_feuille(T). On étend la hauteur aux sous-arbres vides en posant h(∅) = -1, ce qui rend la formule h(T) = 1 + max(h(g), h(d)) valable pour tout nœud, y compris une feuille. L'énoncé porte sur les arbres non vides — ceux que produit la définition récursive — et l'on démontre par récurrence structurelle sur un tel arbre T que h(ajoute_feuille(T)) = h(T) + 1. Le seul point à traiter à part est le comportement de la fonction sur un sous-arbre vide: ajoute_feuille(∅) = ∅, donc h y est inchangée. C'est cette dissymétrie entre « feuille » et « sous-arbre vide » qui rend la preuve délicate.

Base: T est une feuille l, donc h(T) = 0. Par construction, T' = (l, a, ∅), et

$h(T') = 1 + \max(h(a), h(\emptyset)) = 1 + \max(0, -1) = 1 = h(T) + 1$

Récurrence: T = (l, g, d) n'est pas une feuille, donc au moins l'un de g, d est non vide. Par construction T' = (l, g', d'), où g' = ajoute_feuille(g) et d' = ajoute_feuille(d). Par hypothèse de récurrence appliquée aux sous-arbres:

• si g est vide, g' = ∅ et h(g') = -1 = h(g);
• si g est non vide, h(g') = h(g) + 1.

Autrement dit, dans les deux cas, h(g') = h(g) + 1 ou h(g') = h(g) = -1; et comme h(g) ≥ -1 avec égalité seulement pour l'arbre vide, on a toujours h(g') ≥ h(g). Le même raisonnement vaut pour d. On calcule alors:

1h(T') = 1 + max(h(g'), h(d'))2      = 1 + max(h(g), h(d)) + 1     car h(g') = h(g)+1 si g non vide,3                                    et le max est atteint sur un sous-arbre non vide4      = h(T) + 1                    par définition de la hauteur

La justification de la deuxième ligne mérite d'être explicite: au moins un des deux sous-arbres est non vide (sinon T serait une feuille), et pour un sous-arbre non vide la hauteur augmente exactement de 1; l'arbre vide, s'il est présent, conserve -1 et ne peut donc pas être celui qui réalise le maximum. La hauteur du plus haut sous-arbre augmente donc de 1, et h(T') = h(T) + 1. ∎

Interprétation. Chaque chemin de la racine à une feuille est allongé d'une arête, et tous les chemins le sont: la hauteur — le plus long de ces chemins — augmente donc exactement de 1.

On note n(L) le nombre d'éléments de la liste symétrique L. On démontre que n(L) est pair, c'est-à-dire qu'il existe un entier k tel que n(L) = 2k.

Base. L = []. Alors n(L) = 0 = 2 × 0. La propriété est vraie.

Récurrence. L = [el1] L1 [el2], avec L1 une liste symétrique. Par construction, L contient tous les éléments de L1, plus el1 et el2:

$n(L) = n(L_1) + 2$

Par hypothèse de récurrence, L1 est une liste symétrique strictement plus petite que L, donc n(L1) est pair: il existe k tel que n(L1) = 2k. Alors

$n(L) = 2k + 2 = 2(k + 1)$

qui est pair. La propriété est donc établie pour toute liste symétrique. ∎

En Python. La structure se représente par une liste ordinaire, et le test de symétrie par une fonction récursive:

1def est_symetrique(L: list) -> bool:2    """Vrai si L est vide ou de la forme el1 · L1 · el2 avec L1 symetrique."""3    if L == []:4        return True5    if len(L) < 2:6        return False7    return est_symetrique(L[1:-1])8 9print(est_symetrique([]))            # True10print(est_symetrique([1, 2, 2, 1]))  # True11print(est_symetrique([1, 2, 3]))     # False

La fonction retire deux éléments par appel: len(L) décroît de 2 à chaque étape, ce qui est la traduction algorithmique exacte de la preuve — le nombre d'éléments reste pair à chaque étape, et l'on s'arrête soit sur la liste vide, soit sur une liste d'un seul élément, qui n'est pas symétrique.

Principe. La partition classique place le pivot à sa position définitive et répartit le reste en « plus petit » et « plus grand ». Les éléments égaux au pivot se retrouvent dispersés de part et d'autre. La partition à trois zones les regroupe au centre, ce qui est décisif quand le tableau contient beaucoup de valeurs répétées: le tri rapide devient alors linéaire sur ces valeurs.

L'algorithme utilise trois indices: lt (dernier élément de la zone « inférieure »), i (élément courant) et gt (premier élément de la zone « supérieure »). La zone A[lt..i-1] contient les éléments égaux au pivot.

1def partition1(a: list, p: int, r: int) -> tuple[int, int]:2    """Partition a trois zones; retourne (q, t) inclusifs: a[q..t] sont egaux."""3    x = a[r]                    # valeur pivot4    lt, i, gt = p, p, r5    while i <= gt:6        if a[i] < x:7            a[lt], a[i] = a[i], a[lt]8            lt += 19            i += 110        elif a[i] > x:11            a[i], a[gt] = a[gt], a[i]12            gt -= 1             # on ne fait pas avancer i: l'element recu est a examiner13        else:14            i += 1              # a[i] == x : il rejoint la zone centrale

Le tableau obtenu est [3, 5, 1, 4, 2 | 6, 6, 6 | 7, 8]: les indices q = 5 et t = 7 délimitent la zone des éléments égaux au pivot, tout ce qui précède est strictement inférieur à 6, tout ce qui suit est strictement supérieur.

Invariants de la boucle. Au début de chaque itération:

• a[p:lt] ne contient que des éléments strictement inférieurs à x;
• a[lt:i] ne contient que des éléments égaux à x;
• a[i:gt+1] contient les éléments non encore examinés;
• a[gt+1:r+1] ne contient que des éléments strictement supérieurs à x.

Initialisation: lt = i = p et gt = r, les trois premières zones sont vides et la zone non examinée est tout le tableau. Conservation: chaque branche étend exactement une zone et réduit la zone non examinée. Terminaison: i dépasse gt quand il ne reste plus d'élément non examiné, et les trois zones forment alors une partition du tableau.

Le détail qui compte. Dans la branche a[i] > x, on échange a[i] avec a[gt] sans incrémenter i: l'élément qui vient d'arriver en a[i] n'a pas encore été examiné. C'est l'erreur classique sur cet exercice; l'oublier fait remonter un grand élément dans la zone centrale.

Complexité. Chaque itération de la boucle while réduit strictement l'intervalle [i, gt], et le corps s'exécute en temps constant: la partition coûte Θ(n) pour un sous-tableau de taille n, comme la partition classique. Le gain apparaît dans la récursion: les éléments égaux au pivot étant regroupés, ils sont exclus des deux appels récursifs. Si le tableau ne contient qu'une seule valeur distincte, q = p et t = r, et les deux appels récursifs portent sur des sous-tableaux vides: le tri termine en Θ(n).

Pseudocode (indices de 1 à n, comme dans l'énoncé):

1SELECTION-SORT(A, n)2  for i = 1 to n - 13    mini = i4    for j = i + 1 to n5      if A[j] < A[mini]6        mini = j7    exchange A[i] with A[mini]

En Python (indices de 0 à n-1, comme le veut le langage):

1def tri_selection(a: list) -> None:2    n = len(a)3    for i in range(n - 1):4        mini = i5        for j in range(i + 1, n):6            if a[j] < a[mini]:7                mini = j8        a[i], a[mini] = a[mini], a[i]9 10a = [5, 2, 4, 1, 3]11tri_selection(a)12print(a)     # [1, 2, 3, 4, 5]

Invariant de boucle. Au début de l'itération d'indice i, le sous-tableau a[0:i] contient les i plus petits éléments du tableau, rangés dans l'ordre croissant, et aucun élément de a[i:n] n'est plus petit qu'un élément de a[0:i].

• Initialisation: pour i = 0, a[0:0] est vide; l'invariant est vrai trivialement.
• Conservation: la boucle interne identifie l'indice mini du minimum de a[i:n], et l'échange le place en position i. Le sous-tableau a[0:i+1] contient donc les i+1 plus petits éléments, triés.
• Terminaison: la boucle externe s'arrête à i = n-1; en substituant, a[0:n-1] contient les n-1 plus petits éléments triés, et le dernier élément est nécessairement le plus grand. Le tableau entier est trié.

Estimation du temps d'exécution. La boucle interne effectue n - 1 - i comparaisons au tour i. Le nombre total de comparaisons est donc

$\sum_{i=0}^{n-2}(n-1-i) = (n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}$

soit un coût en Θ(n²). Les échanges, au nombre de n - 1 au plus, sont négligeables devant les comparaisons.

Point remarquable. Ce nombre n(n-1)/2 ne dépend pas de l'entrée: sur un tableau déjà trié comme sur un tableau rangé à l'envers, le tri par sélection effectue exactement le même nombre de comparaisons. Il est donc Θ(n²) dans tous les cas — contrairement au tri par insertion, qui est linéaire sur une entrée déjà triée. Vérification expérimentale:

1def compter_comparaisons(a: list) -> int:2    n, comps = len(a), 03    for i in range(n - 1):4        mini = i5        for j in range(i + 1, n):6            comps += 17            if a[j] < a[mini]:8                mini = j9        a[i], a[mini] = a[mini], a[i]10    return comps11 12for n in (5, 10, 20):13    print(n, compter_comparaisons(list(range(n))), n * (n - 1) // 2)14# 5 10 10

1. Stabilité. Après la deuxième boucle, C[v] contient le nombre d'occurrences de la valeur v. Après la troisième, C[v] contient le nombre d'éléments inférieurs ou égaux à v: c'est donc l'indice (à un près) de la dernière position que doit occuper la valeur v dans le tableau trié.

La dernière boucle parcourt l'entrée de la droite vers la gauche. Pour chaque élément A[j]:

1B[C[A[j]]] = A[j]2C[A[j]] = C[A[j]] - 1

La première affectation place A[j] à la dernière place encore libre pour sa valeur; la seconde libère cette place pour l'occurrence suivante — rencontrée plus à gauche, donc plus tôt dans l'ordre d'entrée.

Considérons deux éléments de même valeur v, d'indices j1 < j2 dans l'entrée. Le parcours décroissant rencontre j2 en premier: il l'écrit à la position C[v], la plus grande des positions destinées à la valeur v. Puis il rencontre j1, qui va à la position C[v] - 1, strictement plus petite. Donc B contient l'élément d'indice j1 avant celui d'indice j2: l'ordre relatif d'entrée est préservé. L'algorithme est stable. ∎

En Python:

1def tri_comptage_stable(paires: list, k: int) -> list:2    """Tri par comptage stable; chaque element est un couple (cle, etiquette)."""3    c = [0] * (k + 1)4    for cle, _ in paires:5        c[cle] += 16    for i in range(1, k + 1):7        c[i] += c[i - 1]8    b = [None] * len(paires)9    for j in range(len(paires) - 1, -1, -1):    # de droite a gauche10        cle, etiquette = paires[j]11        c[cle] -= 112        b[c[cle]] = (cle, etiquette)13    return b14 

Les étiquettes a, c, e apparaissent bien dans l'ordre d'entrée, et de même b, d.

2. Le parcours croissant détruit la stabilité. Si l'on parcourt l'entrée de la gauche vers la droite, le premier élément de valeur v rencontré est écrit à la position C[v] — la dernière de son bloc — puis le suivant à C[v] - 1, et ainsi de suite. Les éléments de même valeur se retrouvent donc dans l'ordre inverse de leur apparition en entrée.

1def tri_comptage_non_stable(paires: list, k: int) -> list:2    c = [0] * (k + 1)3    for cle, _ in paires:4        c[cle] += 15    for i in range(1, k + 1):6        c[i] += c[i - 1]7    b = [None] * len(paires)8    for j in range(len(paires)):                # de gauche a droite9        cle, etiquette = paires[j]10        c[cle] -= 111        b[c[cle]] = (cle, etiquette)12    return b13 14paires = [(2, 'a'), (1, 'b'), (2, 'c'), (1, 'd'), (2, 'e')]

Les étiquettes sont maintenant inversées: d avant b, e avant c avant a. L'algorithme reste correct — le tableau B est bien trié par clé, puisque chaque élément est placé dans le bloc de sa valeur — mais la stabilité est perdue.

Pourquoi la stabilité compte. Elle n'a d'intérêt que lorsqu'une donnée satellite accompagne la clé. Le tri par comptage est utilisé comme sous-routine du tri par base (radix sort): on trie d'abord sur le chiffre des unités, puis des dizaines, etc., et la stabilité garantit que l'ordre établi aux étapes précédentes est conservé. Sans elle, le tri par base ne fonctionne pas.

Complexité. Les quatre boucles ont des longueurs k+1, n, k et n: le coût est Θ(n + k) en temps et en mémoire. Le tri par comptage est donc linéaire, mais seulement si l'étendue k des valeurs reste du même ordre que le nombre n d'éléments.

La procédure. La fusion prend deux listes triées g et d et produit une liste triée contenant tous leurs éléments. C'est la brique du tri par fusion.

1def fusion(g: list, d: list) -> list:2    resultat = []3    i = j = 04    while i < len(g) and j < len(d):     # <- boucle principale5        if g[i] <= d[j]:6            resultat.append(g[i])7            i += 18        else:9            resultat.append(d[j])10            j += 111    resultat.extend(g[i:])               # reste de g, deja trie12    resultat.extend(d[j:])               # reste de d, deja trie13    return resultat

Invariant de boucle. Au début de chaque itération de la boucle while:

1. resultat contient les i + j plus petits éléments de g et de d réunis, rangés dans l'ordre croissant;
2. g[i:] et d[j:] sont les éléments de g et de d qui n'ont pas encore été recopiés, et ils sont triés;
3. g[i] est le plus petit élément non recopié de g, et d[j] le plus petit élément non recopié de d.

Les trois obligations.

Initialisation. Avant la première itération, i = j = 0 et resultat est vide. Les zéros plus petits éléments de g ∪ d forment l'ensemble vide, et g[0:], d[0:] sont les listes complètes, triées par hypothèse. L'invariant est vrai.

Conservation. Supposons l'invariant vrai au début d'une itération, avec i < len(g) et j < len(d). Par le point 3, g[i] et d[j] sont les plus petits éléments non recopiés de chaque liste. Comparons-les:

• si g[i] <= d[j], alors g[i] est plus petit que tous les éléments non recopiés de g (par le point 2, g[i] en est le minimum) et que tous ceux de d (car g[i] <= d[j], minimum de d[j:]). C'est donc le plus petit élément non recopié des deux listes; l'ajouter à resultat et incrémenter i préserve les trois points.
• si g[i] > d[j], le raisonnement symétrique s'applique à d[j].

Terminaison. La boucle s'arrête dès que i = len(g) ou j = len(d). À ce moment, par l'invariant, resultat contient tous les éléments de la liste épuisée, plus les i ou j premiers de l'autre, dans l'ordre. Les éléments restants de l'autre liste n'ont pas encore été recopiés; comme cette liste est triée et que tous ses éléments restants sont supérieurs ou égaux au dernier élément recopié, les ajouter à la suite de resultat produit une liste entièrement triée.

Conclusion. resultat contient à la fin tous les éléments de g et de d, une seule fois chacun, dans l'ordre croissant: la procédure de fusion est correcte. ∎

Coût. Chaque itération recopie exactement un élément; le nombre total d'itérations est donc au plus len(g) + len(d). La fusion est en Θ(n) pour n = len(g) + len(d), et c'est cette linéarité qui donne au tri par fusion sa récurrence T(n) = 2T(n/2) + Θ(n), dont la solution est Θ(n log n).

Méthode. On descend dans l'expression en identifiant, à chaque étape, lequel des trois cas s'applique. L'expression est analysée de l'extérieur vers l'intérieur: la structure parenthésée dicte l'ordre des appels.

Étape 1. L'expression complète est (1 + (! ((!1)+1))). C'est une somme: m1 = 1 et m2 = (! ((!1)+1)).

1Mistery(1) = *

Étape 2. m2 = (! ((!1)+1)) est une négation, donc m1 = ((!1)+1), et l'on doit calculer Mistery(((!1)+1)).

Étape 3. ((!1)+1) est une somme: m1 = (!1) et m2 = 1.

1Mistery((!1)) = [? Mistery(1)] = [? *]2Mistery(1) = *

Donc Mistery(((!1)+1)) = { [? *] ; * }.

Étape 4. En remontant à l'étape 2:

1Mistery((! ((!1)+1))) = [? { [? *] ; * } ]

Résultat final. En remontant à l'étape 1:

1{ * ; [? { [? *] ; * }] }

Vérification par programme. On peut encoder l'expression par des tuples et exécuter la fonction pour confirmer:

1def mistery(m):2    if m == '1':3        return '*'4    if m[0] == '+':5        return '{ ' + mistery(m[1]) + ' ; ' + mistery(m[2]) + ' }'6    if m[0] == '!':7        return '[? ' + mistery(m[1]) + ']'8    raise ValueError(m)9 10# (1 + (! ((!1)+1)))  encode par ('+', '1', ('!', ('+', ('!', '1'), '1')))11print(mistery(('+', '1', ('!', ('+', ('!', '1'), '1')))))12# { * ; [? { [? *] ; * }] }

Ce que l'exercice évalue. La capacité à analyser une structure récursive et à suivre l'ordre des appels sans se perdre dans les parenthèses. La règle pratique: traiter les appels du plus profond vers la surface, en écrivant à chaque niveau l'expression réduite. Les erreurs viennent presque toujours d'un niveau sauté ou d'une parenthèse perdue dans la remontée.