L'erreur naturelle est de renvoyer dès la première correspondance trouvée. Une liste non triée ne permet pas de savoir si une occurrence plus tardive existe: il faut parcourir toute la liste, en mémorisant la dernière correspondance rencontrée.

1DERNIERE-OCCURRENCE(L, k)21  resultat = NIL32  x = L.PREMIER43  tant que x ≠ NIL54      si x.DONNEE == k65          resultat = x              // on écrase: la correspondance suivante est plus tardive76      x = x.SUIVANT87  renvoyer resultat

Correction. Invariant de boucle: après le traitement du i-ième maillon, resultat pointe sur la dernière occurrence de k parmi les i premiers maillons, ou vaut NIL si aucune n'a été trouvée. Initialisation: avant la boucle, aucun maillon n'a été traité et resultat = NIL. Maintenance: à l'itération portant sur x, si x.DONNEE == k alors x est la dernière occurrence vue jusqu'ici et remplace resultat; sinon resultat reste inchangé, ce qui est correct puisque x n'est pas une occurrence. Terminaison: la boucle s'arrête quand x = NIL, c'est-à-dire après le dernier maillon, donc resultat est la dernière occurrence de toute la liste.

Coût. Θ(n) en temps, où n est le nombre de maillons: le parcours est intégral, aucune terminaison anticipée n'est possible. Θ(1) en espace supplémentaire. À noter: avec une liste doublement chaînée, on peut parcourir depuis la queue et s'arrêter à la première correspondance — même Θ(n) dans le pire cas, mais un meilleur cas en Θ(1) si la clé est en queue.

1INSERER-APRES(L, o, x)21  x.s = o.s32  o.s = x

Ordre des deux affectations. Il est impératif de lire o.s avant de l'écraser. Écrire o.s = x puis x.s = o.s produirait x.s = x: l'élément se pointerait sur lui-même et toute la suite de la liste serait perdue. C'est l'erreur classique de cet exercice.

Cas limites. Si o est la queue de la liste, o.s valait NIL: après l'insertion, x.s = NIL et x devient la nouvelle queue, sans code supplémentaire. Si o vaut NIL, l'appel est invalide: la précondition est que o référence un nœud de L. Si la liste est vide, il n'y a pas de o et il faut une insertion en tête, donc une procédure différente (ou une sentinelle, voir plus bas).

Coût. Θ(1): deux affectations de pointeurs, aucune traversée. C'est le gain structurel de la liste chaînée sur le tableau, où insérer après la position i coûte Θ(n − i) décalages.

Le cas symétrique. Insérer avant o demande, dans une liste simplement chaînée, de trouver le prédécesseur de o, donc de parcourir la liste depuis la tête: Θ(n). La parade est le chaînage double, où o.p donne le prédécesseur en Θ(1). Autre parade, la sentinelle en tête: elle garantit que tout nœud a un prédécesseur, ce qui supprime le cas « insertion en tête » et rend la procédure uniforme.

Idée. Deux arbres binaires de recherche qui contiennent la même collection produisent le même parcours infixe, puisque le parcours infixe d'un BST énumère ses clés en ordre trié croissant. Deux collections égales ont donc des suites triées égales, et réciproquement. L'algorithme compare les deux parcours infixes en parallèle, sans jamais matérialiser les deux listes: dès qu'une clé diffère, on peut répondre FAUX.

1THE_SAME(A1, A2)21  P1 = pile vide ; P2 = pile vide32  x = A1.racine ; y = A2.racine43  repeter54      tant que x ≠ NIL65          empiler(P1, x) ; x = x.g76      tant que y ≠ NIL87          empiler(P2, y) ; y = y.g98      si vide(P1) ≠ vide(P2) alors renvoyer FAUX109      si vide(P1) alors renvoyer VRAI            // les deux parcours sont épuisés1110     x = depiler(P1) ; y = depiler(P2)1211     si x.r ≠ y.r alors renvoyer FAUX           // clés différentes1312     x = x.d ; y = y.d

Chaque tant que descend dans la branche gauche en empilant le chemin; chaque depiler remonte et fait un pas à droite. C'est un parcours infixe itératif avec pile explicite — la version récursive ne convient pas ici, car il faut suspendre deux parcours en même temps.

Correction. Par le théorème du parcours infixe, depiler(P1) fournit les clés de A1 en ordre croissant, et depiler(P2) celles de A2 en ordre croissant. L'algorithme compare ces deux suites terme à terme; elles sont égales si et seulement si les deux multiensembles de clés sont égaux. Les doublons sont traités naturellement: deux occurrences de la même clé apparaissent deux fois dans chaque suite, et l'alignement terme à terme impose des multiplicités égales.

Complexité. Chaque nœud est empilé une fois et dépilé une fois: Θ(n) en temps dans le cas favorable comme dans le pire cas, où n est le nombre de nœuds. En espace, les deux piles contiennent au plus la hauteur des arbres: Θ(h1 + h2), soit Θ(log n) pour des arbres équilibrés et Θ(n) pour des arbres dégénérés. La version qui construirait deux listes triées coûterait le même temps mais Θ(n) d'espace supplémentaire — inutile ici.

Variante naïve à éviter. Comparer récursivement les structures (r égales, sous-arbres gauche égaux, sous-arbres droit égaux) est faux: deux BST contenant les mêmes clés peuvent avoir des formes totalement différentes. Exemple avec S = {1, 2, 3}: insérer 2, 1, 3 donne un arbre de hauteur 1; insérer 1, 2, 3 donne un peigne de hauteur 2. Les deux sont des BST valides pour le même ensemble, et la comparaison structurelle répondrait FAUX.

On définit d'abord la fonction de comptage, sans quoi il n'y a rien à démontrer:

1taille([ ]) = 02taille([el1] L1 [el2]) = 1 + taille(L1) + 1

Puis on procède par induction structurelle sur L.

Base. L = [ ]: taille(L) = 0, et 0 est un entier pair. La propriété est vérifiée.

Récurrence. Soit L = [el1] L1 [el2] avec L1 une liste symétrique. L'hypothèse de récurrence est: taille(L1) est pair, c'est-à-dire taille(L1) = 2p pour un entier p.

1taille(L) = 1 + taille(L1) + 1        (par construction)2          = taille(L1) + 2            (arithmétique)3          = 2p + 2                    (par hypothèse de récurrence)4          = 2(p + 1)

taille(L) est donc pair. Par le principe d'induction structurelle, la propriété vaut pour toute liste symétrique.

Ce que l'exercice fait travailler. La structure récursive ajoute deux éléments à chaque étape (un à chaque extrémité), d'où la parité conservée. Si la récurrence avait été [el] L1 (un seul élément ajouté à gauche), la conclusion « pair » serait fausse — le contre-exemple [1] [ ] a un élément. Repérer le nombre d'éléments ajoutés par la règle de récurrence est le réflexe qui donne la démonstration.

C'est l'invariant de recherche d'un arbre binaire de recherche, énoncé sur les sous-arbres entiers. La démonstration procède par récurrence sur la structure de T.

Base. T ne contient qu'un nœud. Alors min(T) = max(T), et ce nœud unique est à la fois le plus à gauche et le plus à droite. La propriété est vérifiée.

Récurrence. T est constituée d'une racine R avec deux sous-arbres, l'arbre gauche T1 et l'arbre droit T2. Comme T1 et T2 sont strictement plus petits que T, l'hypothèse de récurrence s'applique: notons m1 et M1 le minimum et le maximum de T1, m2 et M2 ceux de T2. Par hypothèse de récurrence, m1 est la feuille la plus à gauche de T1 et M2 la feuille la plus à droite de T2.

Minimum. Par construction, tout nœud de T1 est inférieur à R, et R est inférieur à tout nœud de T2. Donc m1 < R < m2, et m1 est le minimum de T tout entier. Comme T1 est le fils gauche de R, la feuille la plus à gauche de T1 est aussi la feuille la plus à gauche de T: c'est m1.

Maximum. Symétriquement, M2 est supérieur à R et à tout nœud de T1, donc M2 = max(T). Comme T2 est le fils droit de R, la feuille la plus à droite de T2 est la plus à droite de T: c'est M2.

Conséquence algorithmique. Le minimum s'obtient en descendant toujours à gauche et le maximum toujours à droite, sans jamais examiner l'autre branche: le coût est donc O(h), la hauteur de l'arbre, et non O(n). C'est le premier avantage concret du BST sur une structure non ordonnée, où trouver le minimum coûte Θ(n).

Précision de vocabulaire. L'énoncé parle de « feuille ». En toute rigueur, le nœud minimal est le nœud le plus à gauche (celui atteint en descendant systématiquement à gauche); il n'a pas de fils gauche, mais peut avoir un fils droit, auquel cas ce n'est pas une feuille. Dans un arbre binaire complet (tout nœud interne a deux fils), le nœud le plus à gauche est effectivement une feuille, et l'énoncé est exact.

Notons n(T) le nombre de nœuds de T. On démontre n(T) ≤ 2^(h(T)+1) − 1 par induction structurelle.

Base. T se réduit à une racine: n(T) = 1 et h(T) = 0, donc 1 ≤ 2^(0+1) − 1 = 1. L'égalité est atteinte.

Récurrence. T est une racine r avec deux sous-arbres TL et TR. Les hypothèses de récurrence donnent

1n(TL) ≤ 2^(h(TL)+1) − 1     et     n(TR) ≤ 2^(h(TR)+1) − 1

Or n(T) = 1 + n(TL) + n(TR), donc

1n(T) ≤ 1 + 2^(h(TL)+1) − 1 + 2^(h(TR)+1) − 12     = 2^(h(TL)+1) + 2^(h(TR)+1) − 1

Comme la fonction puissance est croissante et que h(TL) ≤ max(h(TL), h(TR)) = h(T) − 1 (de même pour TR),

12^(h(TL)+1) ≤ 2^h(T)     et     2^(h(TR)+1) ≤ 2^h(T)

d'où

1n(T) ≤ 2·2^h(T) − 1 = 2^(h(T)+1) − 1

La borne est donc établie.

Égalité et cas de l'arbre presque complet. L'égalité est atteinte exactement quand les deux sous-arbres sont eux-mêmes de hauteur h(T) − 1 et saturent leur propre borne: l'arbre est alors presque complet (tous les niveaux pleins sauf éventuellement le dernier, rempli de gauche à droite). C'est la forme que prennent les tas, et c'est ce qui justifie leur hauteur ⌊log₂ n⌋ et donc le coût O(log n) de leurs opérations.

Cas d'un nœud à un seul fils. La définition de l'énoncé ne couvre que la racine à deux sous-arbres. Pour un nœud r ayant un unique fils T1, on pose h(r) = 1 + h(T1) et n(r) = 1 + n(T1); la borne tient toujours, et de façon stricte: n(r) ≤ 1 + 2^(h(T1)+1) − 1 = 2^h(T) − 1 < 2^(h(T)+1) − 1.

Conséquence inverse, souvent demandée à l'oral. Tout arbre binaire à n nœuds a une hauteur au moins ⌊log₂ n⌋. En effet, n ≤ 2^(h+1) − 1 donne h + 1 ≥ log₂(n + 1), donc h ≥ ⌊log₂ n⌋. C'est la borne que les arbres équilibrés atteignent et que les arbres dégénérés (hauteur n − 1) manquent complètement.

Notons #n(T) le nombre de symboles n (les nœuds internes) de T. On démontre #n(T) = 2^(h(T)) − 1 par récurrence structurelle sur T ∈ Trees.

Base. T = ( ): #n(T) = 0 et h(T) = 0, donc 0 = 2^0 − 1 = 0. Vérifié.

Récurrence. T = (n) T1 T1. L'hypothèse de récurrence est #n(T1) = 2^(h(T1)) − 1.

1#n(T) = #n(T1) + #n(T1) + 1        (par construction: les deux sous-arbres plus la racine)2      = 2 · #n(T1) + 13      = 2 · (2^(h(T1)) − 1) + 1     (par hypothèse de récurrence)4      = 2^(h(T1)+1) − 2 + 15      = 2^(h(T1)+1) − 16      = 2^(h(T)) − 1                (par construction: h(T) = 1 + h(T1))

La propriété est donc vraie pour tout T ∈ Trees.

Lecture de la définition. La règle de récurrence impose le même sous-arbre T1 à gauche et à droite. Les arbres de Trees sont donc parfaitement symétriques: ce sont les arbres binaires parfaits (tous les niveaux pleins), et #n(T) compte les nœuds internes. Un arbre de Trees de paramètre T1 a 2^(h(T1)+1) feuilles et 2^(h(T1)+1) − 1 nœuds internes; le nombre total de nœuds vaut donc 2^(h(T)+1) − 1, la borne supérieure de l'exercice précédent.

Ce qu'on ne peut pas conclure. La réciproque est fausse: tout arbre binaire dont le nombre de nœuds internes vaut 2^h − 1 n'est pas nécessairement dans Trees. Le peigne gauche (n) ((n) ( ) ( )) ( ) a 2 nœuds internes, et 2^2 − 1 = 3 ≠ 2: la formule caractérise les arbres de l'ensemble, elle ne les identifie pas parmi tous les arbres binaires.

1. Multiplication par 5.

1MULT5(T)21  si T = [ ] alors renvoyer [ ]32  si T = T1 node T2 alors renvoyer MULT5(T1) node*5 MULT5(T2)

La structure de l'arbre est recopiée à l'identique, seule la valeur de chaque racine est transformée. Coût Θ(n) en temps (un appel par nœud) et Θ(h) en espace de pile pour un arbre de hauteur h.

2. Pairs et impairs remplacés par A et B.

1PAIRIMPAIR(T)21  si T = [ ] alors renvoyer [ ]32  si T = T1 node T2 et node est pair43      alors renvoyer PAIRIMPAIR(T1) A PAIRIMPAIR(T2)54      sinon renvoyer PAIRIMPAIR(T1) B PAIRIMPAIR(T2)

Le test de parité porte sur la racine de chaque sous-arbre; les deux appels récursifs sont identiques dans les deux branches, seul le symbole inséré change. On peut factoriser pour éviter la duplication: calculer d'abord S = PAIRIMPAIR(T1) et D = PAIRIMPAIR(T2), puis renvoyer S suivi du bon symbole suivi de D.

3. Élimination des feuilles.

1ELIMINER-FEUILLES(T)21  si T = [ ] alors renvoyer [ ]32  si T = [ ] node [ ] alors renvoyer [ ]        // la racine est une feuille: on la retire43  si T = T1 node T2 alors renvoyer ELIMINER-FEUILLES(T1) node ELIMINER-FEUILLES(T2)

Le cas 2 est celui qu'on oublie: quand les deux sous-arbres sont vides, le nœud courant est une feuille et doit disparaître, non pas être recopié. L'ordre des cas est donc significatif — le test « deux sous-arbres vides » doit précéder le test général.

Cas limites à vérifier sur les trois fonctions. Un arbre vide renvoie un arbre vide. Un arbre réduit à une feuille: MULT5 renvoie une feuille dont la valeur est multipliée par 5; PAIRIMPAIR renvoie une feuille portant A ou B; ELIMINER-FEUILLES renvoie l'arbre vide — c'est le seul cas où l'arbre rétrécit jusqu'à disparaître, et il faut que la fonction appelante accepte de recevoir [ ] là où elle attendait un sous-arbre. C'est exactement ce que fait la ligne 3 en rappelant la fonction sur les deux sous-arbres: le résultat peut être vide, et la construction [ ] node T2 reste un arbre valide.

1. Définition récursive.

1Base:      Feuille(lettre) est un arbre, pour toute lettre de l'alphabet2Récurrence: si G et D sont des arbres, alors Noeud(G, D) est un arbre

La base est une feuille portant une lettre; la récurrence combine deux arbres sous un nouveau nœud. L'arbre vide n'appartient pas à cet ensemble: tout arbre est non vide.

2. Fonction d'ajout.

1AJOUTER(T)21  si T = Feuille(l) alors renvoyer Noeud(Feuille(l), Feuille(a))32  si T = Noeud(G, D) alors renvoyer Noeud(AJOUTER(G), AJOUTER(D))

Chaque feuille Feuille(l) devient un nœud interne dont le fils gauche est la feuille d'origine (la lettre l est donc conservée) et le fils droit est une nouvelle feuille a. Le cas de base ne se contente pas de renvoyer une feuille: il ajoute un niveau, ce qui est précisément l'effet que la question 3 demande de mesurer.

3. Démonstration. Définissons la hauteur:

1h(Feuille(l)) = 02h(Noeud(G, D)) = 1 + max(h(G), h(D))

et notons h'(T) = h(AJOUTER(T)). On démontre h'(T) = h(T) + 1 par induction structurelle sur T.

Base. T = Feuille(l): AJOUTER(T) = Noeud(Feuille(l), Feuille(a)), donc

1h'(T) = 1 + max(h(Feuille(l)), h(Feuille(a))) = 1 + max(0, 0) = 1 = h(T) + 1

Récurrence. T = Noeud(G, D), avec pour hypothèses h'(G) = h(G) + 1 et h'(D) = h(D) + 1. Alors

1h'(T) = h(Noeud(AJOUTER(G), AJOUTER(D)))2      = 1 + max(h'(G), h'(D))3      = 1 + max(h(G) + 1, h(D) + 1)4      = 1 + 1 + max(h(G), h(D))5      = h(T) + 1

La propriété est établie pour tout arbre.

Pourquoi +1 exactement, et pas plus. Chaque chemin racine-feuille de T est prolongé d'une arête: la feuille d'origine devient un nœud interne et un nouveau fils apparaît en dessous. Tous les chemins s'allongent donc de la même quantité, et le plus long aussi. C'est le point que la démonstration formalise: l'ajout est uniforme, il ne privilégie aucune branche.

On note j l'indice de la variable de jointure (le même dans les deux relations, par définition de la jointure naturelle), r le nombre de lignes de R et s le nombre de lignes de S. On suppose que DICO accepte plusieurs valeurs pour une même clé — ce que garantit l'implantation par table de hachage avec chaînage: deux lignes de R peuvent porter la même valeur de jointure.

1JOINTURE(R, S)21  si TAILLE(R) > TAILLE(S) alors échanger R et S        // R devient la plus petite32  D = DICO vide43  pour i = 1 à TAILLE(R)54      ASSOCIER(D, R[i][j], i)                           // clé = valeur de jointure65  resultat = SUITE vide76  pour k = 1 à TAILLE(S)87      pour chaque position p dans RECUPERER(D, S[k][j])98          ajouter à resultat la ligne formée de S[k] et de R[p]109  renvoyer resultat

Correction. Après la phase 1, l'invariant de D est: pour toute valeur v de variable de jointure présente dans R, RECUPERER(D, v) renvoie exactement la liste des positions des lignes de R dont la variable de jointure vaut v; si v n'apparaît pas dans R, RECUPERER renvoie la liste vide. La phase 2 parcourt alors toutes les lignes de S et énumère, pour chacune, toutes les lignes de R qui s'apparient. Chaque paire appariée est produite exactement une fois, et aucune paire non appariée ne l'est. Le résultat est donc bien la jointure.

Choix de la relation la plus petite. L'algorithme est symétrique du point de vue du nombre de paires produites, mais la table de hachage occupe Θ(|R|) en mémoire. Construire D sur la plus petite relation minimise l'empreinte mémoire — c'est la raison du test de la ligne 1, et c'est une contrainte réelle quand une des deux relations ne tient pas en mémoire.

Question 4: coût avec une table de hachage avec chaînage.

• Ligne 3-4: r insertions, chacune en Θ(1) attendu, soit Θ(r) attendu.
• Lignes 6-8: s recherches, chacune en Θ(1) attendu, plus la production du résultat.

Coût attendu: Θ(r + s + |résultat|), où |résultat| est le nombre de lignes produites. Le terme |résultat| est incompressible: il faut bien écrire chaque ligne du résultat. Dans le pire cas (hachage dégénéré, toutes les clés dans la même alvéole), la recherche dégénère en parcours de liste et le coût devient Θ(r·s) — c'est le pire cas de toute table de hachage, et il justifie les précautions d'usage (bonne fonction de hachage, facteur de charge maîtrisé).

Question 5: coût avec un tableau trié.

DICO réalise alors ASSOCIER et RECUPERER par recherche dichotomique sur un tableau maintenu trié.

• Construction: si l'on insère les r lignes une par une dans un tableau trié, chaque insertion coûte Θ(r) en décalages (il faut décaler pour garder le tableau trié), soit Θ(r²) — désastreux. La bonne méthode est de trier d'abord les lignes de R par valeur de jointure, ce qui coûte Θ(r log r), puis de remplir D en une passe.
• Recherches: chaque RECUPERER coûte Θ(log r) par recherche dichotomique, donc Θ(s log r) pour les s lignes de S.

Coût total: Θ(r log r + s log r + |résultat|), à comparer au Θ(r + s + |résultat|) attendu de la table de hachage. La dégradation est logarithmique, pas exponentielle: le tableau trié reste un choix raisonnable, et il a l'avantage d'être contigu en mémoire (meilleure localité) et de ne pas dépendre de la qualité d'une fonction de hachage. Il permet en outre, si la jointure est sur un intervalle plutôt que sur une égalité, de répondre directement — ce qu'une table de hachage ne sait pas faire.

Ce qu'il faut éviter. Comparer les clés deux à deux pour détecter les collisions demande Θ(N²) opérations et n'utilise pas la fonction de hachage: c'est à la fois lent et à côté du sujet. La bonne approche est de compter les clés par valeur de hachage, avec un tableau de compteurs indexé par la valeur de hachage.

1COMPTER-COLLISIONS(N, K, M)2// N: nombre de clés de test; K: borne des clés; M: nombre de valeurs de hachage possibles31  C = tableau de M compteurs, initialisés à 0        // mémoire O(M), indépendante de N42  cles-en-collision = 053  paires-en-collision = 064  pour i = 1 à N75      cle = RAND(K)86      h = HACHAGE(cle)97      si C[h] > 0108          cles-en-collision = cles-en-collision + 1   // cette valeur de hachage est déjà prise119          paires-en-collision = paires-en-collision + C[h]1210     C[h] = C[h] + 11311 renvoyer (cles-en-collision, paires-en-collision)

Les deux définitions de « nombre de collisions ». L'énoncé ne tranche pas, et les deux mesures sont légitimes:

• cles-en-collision compte les clés qui tombent sur une valeur de hachage déjà occupée: c'est le nombre d'insertions « ratées » dans une table idéale, et c'est la quantité minimale à rapporter.
• paires-en-collision compte les paires de clés distinctes ayant le même hachage. Après la boucle, on a paires-en-collision = Σ_i C[i]·(C[i] − 1)/2, ce qui est la mesure naturelle de la qualité du hachage: une fonction parfaite donne 0, une fonction constante donne N(N−1)/2.

Annoncer laquelle des deux on calcule fait partie de la réponse; un énoncé qui demande « le nombre de collisions » sans préciser attend en général la seconde.

Complexité. Θ(N) en temps (une itération par clé, chaque opération interne en Θ(1) attendu) et Θ(M) en espace, où M est le nombre de valeurs de hachage possibles. C'est le point de l'énoncé: la mémoire dépend de l'intervalle des valeurs de hachage, pas du nombre de clés testées. Passer de 1 000 à 1 000 000 de clés ne change pas l'empreinte mémoire; augmenter l'intervalle des hachages la change linéairement, ce qui est inévitable puisque c'est le domaine que l'on mesure.

Vérification croisée. Après la boucle, Σ_i C[i] = N: la somme des compteurs redonne le nombre de clés testées. C'est l'assertion à écrire dans un test unitaire, et elle détecte immédiatement un HACHAGE qui sortirait de l'intervalle [0, M−1] — auquel cas l'algorithme écrit hors du tableau.

Convention de lecture. Une pulsation de la comptine correspond à un passage de la patate au voisin de gauche. Le joueur qui détient la patate après les k pulsations est éliminé.

Algorithme. Les joueurs restants occupent les positions 1 à m de SUITE, dans l'ordre croissant de leur numéro. Comme la comptine repart du plus petit numéro restant à chaque manche, la patate démarre toujours à la position 1: après k passages circulaires, elle se trouve à la position (k mod m) + 1. Il n'y a donc aucune position à mémoriser d'une manche à l'autre.

1GAGNANT(n, k)21  S = SUITE vide32  pour i = 1 à n43      INSERER(TAILLE(S) + 1, i)         // S = 1, 2, …, n54  tant que TAILLE(S) > 165      m = TAILLE(S)76      p = (k mod m) + 1                  // position du porteur après k passages87      SUPPRIMER(p)                      // il est éliminé98  renvoyer RECUPERER(1)

Correction. Invariant de boucle: au début de chaque itération, S contient exactement les joueurs encore en jeu, dans l'ordre croissant de leur numéro. Initialisation: après la boucle des lignes 2-3, S = 1, 2, …, n, soit tous les joueurs. Maintenance: S[1] est le plus petit numéro restant, donc le porteur initial; les passages successifs parcourent les positions cycliquement, et la position atteinte après k passages est (k mod m) + 1. Supprimer cette position retire le bon joueur, et l'ordre croissant des numéros est préservé puisque SUPPRIMER(p) ne fait que retirer un élément. Terminaison: chaque itération retire exactement un joueur, donc après n − 1 itérations il en reste un seul, le gagnant.

Question 4: coût avec une liste doublement chaînée.

SUPPRIMER(p) est en Θ(1) si l'on dispose déjà d'un pointeur sur la position p. Le coût réel vient de l'atteinte de la position: à chaque manche, il faut avancer de k mod m maillons depuis la position 1, soit k mod m pas. Le coût total est donc

1Σ_{m=2}^{n} (k mod m)  ≤  Σ_{m=2}^{n} min(k, m − 1)  ≤  k(n − 1)

soit O(kn) dans le pire cas, et Θ(n) si k est une constante. Deux conséquences pratiques: pour k grand devant n, chaque manche coûte k mod m pas et l'algorithme est linéaire en kn; pour k petit, il est linéaire en n. On peut améliorer en remarquant que k mod m décroît quand m décroît, mais l'ordre de grandeur kn reste le bon dans le cas général.

Question 5: coût avec un tableau.

L'atteinte de la position p est immédiate, en Θ(1), mais SUPPRIMER(p) doit décaler vers la gauche les m − p éléments suivants pour garder le tableau compact: Θ(m) par manche. Le coût total devient

1Σ_{m=2}^{n} Θ(m) = Θ(n²)

indépendamment de k. Le renversement est net: pour k grand, la liste chaînée l'emporte largement (O(kn) contre Θ(n²) seulement si k est petit devant n); pour k = 1 ou k = 2, le tableau est compétitif et beaucoup plus simple à écrire.

Le point de l'exercice. C'est un cas d'école où la structure de données, et non l'algorithme, décide de la complexité. L'algorithme est identique dans les deux cas; seules les réalisations du type abstrait SUITE diffèrent. Un énoncé qui demande « le coût de votre algorithme en supposant que le type SUITE soit réalisé par… » teste exactement cette distinction entre l'algorithme et sa réalisation.

Remarque historique. Ce problème est connu sous le nom de problème de Josèphe, du nom de Flavius Josèphe, historiographe romain du Ier siècle. La variante classique élimine tous les k-ièmes joueurs en repartant du joueur suivant l'éliminé, et non du plus petit numéro restant; elle admet une solution arithmétique close, en Θ(n) et O(1) mémoire, sans aucune structure de données. C'est un rappel utile: avant d'optimiser une structure, vérifier qu'une formule ne résout pas le problème.