Complexity-04 — Décider sans connaître la suite

Navigation : Index | 03 — Plus de temps, plus de problèmes | 04b — Secrétaire matroïdal et k-server

Public : Licence. Les conjectures de septembre 2026, le secrétaire matroïdal et le work function algorithm sont conservés dans l’approfondissement 04b ; ce notebook s’arrête aux trois objets classiques du domaine.

Ce que ce notebook suppose

• 01 — Compter des pas : le coût d’un algorithme se compte, il ne se chronomètre pas ;
• 03 — Plus de temps, plus de problèmes : comparer un algorithme à ceux d’une classe entière, et pourquoi une table finie ne démontre rien.

Objectifs : poser le modèle d’une décision irréversible prise sans connaître la suite ; mesurer un rapport de compétitivité sur trois problèmes classiques — louer ou acheter, pagination, secrétaire ; séparer ce qui se mesure de ce qui se démontre. Durée estimée : 45 minutes.

1. Louer ou acheter, sans savoir combien de temps

Un magasin loue des skis 1 € par jour, ou les vend \(B\) € une fois pour toutes. Vous skiez demain, mais vous ne savez pas jusqu’à quand : acheter trop tôt et acheter trop tard se paient tous les deux. Un algorithme en ligne décide jour après jour sans connaître la durée ; un algorithme hors ligne la connaît, et paie l’optimum \(\min(n, B)\).

La règle en ligne la plus simple fixe un seuil : louer jusqu’au jour \(T-1\), acheter au jour \(T\). Comme la durée réelle reste inconnue, on ne juge pas la règle sur une saison mais sur toutes les durées possibles, par le pire rapport coût payé sur coût optimal — le rapport de compétitivité.

Reste à choisir \(T\). Balayons-les tous, pour \(B = 10\).

import numpy as np

rng = np.random.default_rng(42)
print("numpy", np.__version__)

# Location de skis : louer 1 par jour, ou acheter B une fois pour toutes.
B = 10


def cout_seuil(T, n, B=B):
    """Coût de la règle « louer jusqu'au jour T-1, acheter au jour T » sur une saison de n jours."""
    return n if n < T else (T - 1) + B


def optimum(n, B=B):
    """Optimum hors ligne : connaître la durée permet de payer min(n, B)."""
    return min(n, B)


print(f"Location de skis — achat B = {B}, location 1 par jour")
print(f"{'seuil T':>8} | {'pire rapport':>12}")
for T in range(1, B + 1):
    pire = max(cout_seuil(T, n) / optimum(n) for n in range(1, 4 * B + 1))
    print(f"{T:>8} | {pire:>12.4f}")

pire_B = max(cout_seuil(B, n) / optimum(n) for n in range(1, 4 * B + 1))
assert abs(pire_B - (2 - 1 / B)) < 1e-12
print(f"\nMeilleur seuil : T = {B}, pire rapport = {pire_B:.4f} = 2 - 1/{B}")

numpy 2.4.4
Location de skis — achat B = 10, location 1 par jour
 seuil T | pire rapport
       1 |      10.0000
       2 |       5.5000
       3 |       4.0000
       4 |       3.2500
       5 |       2.8000
       6 |       2.5000
       7 |       2.2857
       8 |       2.1250
       9 |       2.0000
      10 |       1.9000

Meilleur seuil : T = 10, pire rapport = 1.9000 = 2 - 1/10

Lecture du résultat. Le balayage désigne le seuil \(T = B\) : louer les \(B-1\) premiers jours, puis acheter au jour \(B\). Son pire rapport vaut exactement \(2 - 1/B\), soit \(1{,}9\) pour \(B = 10\) ; le pire cas est la saison de \(n = B\) jours, où l’optimum paie \(B\) et la règle paie \((B-1) + B\). Acheter plus tôt est bien pire — à \(T = 1\) le pire rapport vaut \(B\) entier. Aucun seuil de cette famille ne descend sous \(2 - 1/B\), et il se trouve que la barrière est plus haute que la famille : elle vaut pour tous les algorithmes déterministes (§5).

2. Tirer au sort le jour de l’achat

Une règle déterministe a un défaut que le tableau rend visible : son pire cas est une durée, et l’adversaire la choisit. Randomiser change la nature du jeu — l’adversaire ne choisit plus contre une règle, mais contre une distribution. On tire le jour d’achat selon \(p_T\) proportionnelle à \((1 + 1/B)^{T-1}\) : une distribution qui privilégie les achats tardifs sans jamais exclure les précoces.

Le rapport devient alors une espérance, \(\mathbb{E}[\mathrm{ALG}(n)] / \mathrm{OPT}(n)\), maximisée sur les durées. Comparons-la au seuil déterministe et à la valeur que la littérature donne pour optimale, \(e/(e-1) \approx 1{,}582\).

# La règle déterministe plafonne à 2 - 1/B. La randomisation fait-elle mieux ?
def pire_ratio_randomise(B):
    """Pire espérance de rapport pour la distribution p_T proportionnelle à (1+1/B)^(T-1)."""
    T = np.arange(1, B + 1, dtype=float)
    p = (1 + 1 / B) ** (T - 1)
    p /= p.sum()
    # Durées n < B : E[cout(n)] = n(1 - P_n) + M_n, avec P la fonction de répartition
    # et M_n la somme des p_T (T-1+B) pour T <= n. Durées n >= B : E[T] - 1 + B.
    n = np.arange(1, B, dtype=float)
    cum_p = np.cumsum(p)[:-1]
    cum_m = np.cumsum(p * (T - 1 + B))[:-1]
    ratios = list((n * (1 - cum_p) + cum_m) / n)
    ratios.append((float((p * T).sum()) - 1 + B) / B)
    return max(ratios)


print(f"{'B':>6} | {'randomise':>10} | {'deterministe':>12} | {'e/(e-1)':>9}")
for Bv in (10, 100, 1000, 10000):
    print(f"{Bv:>6} | {pire_ratio_randomise(Bv):>10.5f} | {2 - 1 / Bv:>12.5f} | {np.e / (np.e - 1):>9.5f}")

     B |  randomise | deterministe |   e/(e-1)
    10 |    1.56471 |      1.90000 |   1.58198
   100 |    1.58071 |      1.99000 |   1.58198
  1000 |    1.58185 |      1.99900 |   1.58198
 10000 |    1.58196 |      1.99990 |   1.58198

Lecture du résultat. La randomisation descend loin sous la barrière déterministe : le pire rapport mesuré vaut \(1{,}56471\) pour \(B = 10\), puis \(1{,}58071\), \(1{,}58185\) et \(1{,}58196\) — il converge vers \(e/(e-1) \approx 1{,}58198\), la valeur que la littérature donne pour optimale. Cette valeur n’a pas été recopiée : elle sort de la mesure, sur une distribution construite ici. L’écart entre les deux barrières mesure le prix de la certitude, et il ne se referme pas : \(2 - e/(e-1) \approx 0{,}418\) à la limite, contre \(0{,}335\) à \(B = 10\).

3. Garder \(k\) pages quand on ne sait pas lesquelles reviendront

Une mémoire rapide de \(k\) cases, des pages demandées une par une ; une page absente coûte un défaut et chasse une page présente. Le futur est inconnu : c’est le problème de la pagination, et c’est le dilemme des skis sous une autre forme — garder une page (payer plus tard) ou la remplacer (payer maintenant).

Deux algorithmes, deux philosophies :

• Belady (hors ligne) : évincer la page dont le prochain usage est le plus lointain. Il connaît la suite ; c’est l’optimum hors ligne, pas une stratégie applicable telle quelle ;
• LRU (en ligne) : évincer la page utilisée le plus anciennement. Aucune connaissance du futur.

Mesurons-les sur un motif qu’un adversaire peut construire — \(k+1\) pages demandées en cycle, de sorte que la page demandée soit toujours celle qui vient d’être évincée — puis sur des requêtes aléatoires, où le futur n’est pas hostile.

# Pagination : k cases de mémoire, des pages demandées une par une.
def belady(requetes, k):
    """Optimum hors ligne (Belady 1966) : évincer la page dont le prochain usage est le plus lointain."""
    cache, defauts = set(), 0
    for t, r in enumerate(requetes):
        if r in cache:
            continue
        defauts += 1
        if len(cache) < k:
            cache.add(r)
            continue
        prochain = {p: float("inf") for p in cache}
        for u in range(t + 1, len(requetes)):
            if requetes[u] in cache and prochain[requetes[u]] == float("inf"):
                prochain[requetes[u]] = u
        cache.discard(max(prochain, key=lambda p: prochain[p]))
        cache.add(r)
    return defauts


def lru(requetes, k):
    """En ligne : évincer la page utilisée le plus anciennement."""
    cache, defauts = [], 0
    for r in requetes:
        if r in cache:
            cache.remove(r)
            cache.append(r)
            continue
        defauts += 1
        if len(cache) == k:
            cache.pop(0)
        cache.append(r)
    return defauts


def fifo(requetes, k):
    """En ligne, autre règle : évincer la page entrée le plus anciennement."""
    cache, defauts = [], 0
    for r in requetes:
        if r in cache:
            continue
        defauts += 1
        if len(cache) == k:
            cache.pop(0)
        cache.append(r)
    return defauts


print("Motif cyclique sur k+1 pages (l'adversaire choisit la suite)")
print(f"{'k':>2} | {'T':>4} | {'OPT':>5} | {'LRU':>4} | {'FIFO':>4} | {'rapport LRU':>11} | {'rapport FIFO':>12}")
ratio_lru_cyclique = {}
for k in (2, 3, 4, 5):
    for T in (60, 600):
        req = [i % (k + 1) for i in range(T)]
        o, l, f = belady(req, k), lru(req, k), fifo(req, k)
        ratio_lru_cyclique[(k, T)] = l / o
        print(f"{k:>2} | {T:>4} | {o:>5} | {l:>4} | {f:>4} | {l / o:>11.3f} | {f / o:>12.3f}")

req_alea = [int(x) for x in rng.integers(0, 20, size=600)]
print("\nMotif aleatoire (20 pages, 600 requetes, k = 5)")
o5, l5, f5 = belady(req_alea, 5), lru(req_alea, 5), fifo(req_alea, 5)
ratio_lru_aleatoire, ratio_fifo_aleatoire = l5 / o5, f5 / o5
print(f"  OPT = {o5}  LRU = {l5}  FIFO = {f5}")
print(f"  rapport LRU = {ratio_lru_aleatoire:.4f}   rapport FIFO = {ratio_fifo_aleatoire:.4f}")

Motif cyclique sur k+1 pages (l'adversaire choisit la suite)
 k |    T |   OPT |  LRU | FIFO | rapport LRU | rapport FIFO
 2 |   60 |    31 |   60 |   60 |       1.935 |        1.935
 2 |  600 |   301 |  600 |  600 |       1.993 |        1.993
 3 |   60 |    22 |   60 |   60 |       2.727 |        2.727
 3 |  600 |   202 |  600 |  600 |       2.970 |        2.970
 4 |   60 |    18 |   60 |   60 |       3.333 |        3.333
 4 |  600 |   153 |  600 |  600 |       3.922 |        3.922
 5 |   60 |    16 |   60 |   60 |       3.750 |        3.750
 5 |  600 |   124 |  600 |  600 |       4.839 |        4.839

Motif aleatoire (20 pages, 600 requetes, k = 5)
  OPT = 295  LRU = 435  FIFO = 433
  rapport LRU = 1.4746   rapport FIFO = 1.4678

Lecture du résultat. Sur le motif cyclique, LRU fait un défaut à chaque requête, et son rapport mesuré tend vers \(k\) : \(1{,}99\) pour \(k = 2\), \(2{,}97\) pour \(k = 3\), \(3{,}92\) pour \(k = 4\), \(4{,}84\) pour \(k = 5\) — la limite \(k\) est atteinte de plus près à mesure que la séquence s’allonge. FIFO, dont la règle d’éviction est pourtant différente, affiche exactement les mêmes rapports sur ce motif : ce qui coûte ici n’est pas la règle d’éviction, c’est l’absence de futur. Sur les requêtes aléatoires, le même LRU retombe à \(1{,}47\) : le pire cas est adversarial, pas moyen — la même leçon que pour les skis.

4. Choisir sans jamais pouvoir revenir en arrière

Dernier problème, le plus pur des trois : \(n\) candidates et candidats se présentent un par un, dans un ordre aléatoire. À chaque entretien on n’apprend que le rang de la personne parmi celles déjà vues, et il faut décider immédiatement : accepter, ou laisser passer pour toujours. Objectif : maximiser la probabilité d’accepter la meilleure personne.

La règle classique ne regarde aucune valeur, seulement l’ordre : observer sans accepter une fraction \(\gamma\) des arrivées, puis accepter la première personne qui dépasse tout ce qui a été vu. La théorie place le sommet à \(\gamma = 1/e \approx 0{,}368\), pour une probabilité de succès de \(1/e\). Balayons \(\gamma\) : la courbe doit le montrer.

# Secrétaire : n arrivées dans un ordre aléatoire, acceptation immédiate et définitive.
def secretaire(perm, gamma):
    """Vrai si la règle (observer une fraction gamma, puis prendre le premier record) garde le meilleur."""
    n = len(perm)
    seuil = max(1, int(gamma * n))
    vu = max(perm[:seuil])
    for x in perm[seuil:]:
        if x > vu:
            return x == n - 1
    return False


def taux_succes(n, gamma, runs=20_000):
    """Probabilité mesurée de garder le meilleur rang, sur runs permutations."""
    return sum(secretaire(rng.permutation(n), gamma) for _ in range(runs)) / runs


print(f"{'gamma':>7} | {'n=100':>8} | {'n=1000':>8}")
taux_1sur_e = {}
for gamma in (0.1, 0.2, 0.3, 1 / np.e, 0.4, 0.5, 0.6, 0.8):
    t100, t1000 = taux_succes(100, gamma), taux_succes(1000, gamma)
    taux_1sur_e[gamma] = (t100, t1000)
    print(f"{gamma:>7.4f} | {t100:>8.4f} | {t1000:>8.4f}")
print(f"\n1/e = {1 / np.e:.4f}   e/(e-1) = {np.e / (np.e - 1):.4f}   ecart-type d'un sondage a 20000 tirages : {(0.368 * 0.632 / 20000) ** 0.5:.4f}")

  gamma |    n=100 |   n=1000
 0.1000 |   0.2367 |   0.2287
 0.2000 |   0.3244 |   0.3252
 0.3000 |   0.3661 |   0.3632
 0.3679 |   0.3690 |   0.3684
 0.4000 |   0.3695 |   0.3699
 0.5000 |   0.3537 |   0.3484
 0.6000 |   0.3108 |   0.3079
 0.8000 |   0.1777 |   0.1809

1/e = 0.3679   e/(e-1) = 1.5820   ecart-type d'un sondage a 20000 tirages : 0.0034

Lecture du résultat. La courbe monte puis redescend, et son sommet est plat : de \(\gamma = 0{,}3\) à \(\gamma = 0{,}4\), toutes les mesures tiennent entre \(0{,}363\) et \(0{,}370\), alors que l’écart-type de sondage vaut \(0{,}0034\) pour 20 000 tirages. La mesure ne peut donc pas distinguer \(1/e\) de \(0{,}4\) — et ce n’est pas une faiblesse de l’expérience, c’est une propriété du problème : près de l’optimum, la perte est du second ordre, la courbe est localement plate. En revanche, s’écarter franchement du seuil se paie : observer 10 % des arrivées tombe à \(0{,}23\), en observer 80 % à \(0{,}18\).

5. Ce qu’aucune de ces expériences ne démontre

Les trois sections précédentes sont des tables finies : elles évaluent des stratégies données sur des entrées choisies. Aucune ne peut établir qu’aucune stratégie ne fait mieux — exactement la limite que le notebook 03 avait posée pour les budgets de temps. Quatre énoncés le font à leur place ; ils sont cités ici sans être démontrés :

Énoncé	Contenu	Ce que la mesure en montre
Skis, déterministe	aucun algorithme déterministe ne fait mieux que \(2 - 1/B\)	notre meilleur seuil l’atteint : \(1{,}9\)
Skis, randomisé	la meilleure distribution atteint \(e/(e-1) \approx 1{,}582\)	la nôtre y converge : \(1{,}58196\)
Pagination	le rapport optimal d’un algorithme déterministe est exactement \(k\) (Sleator et Tarjan, 1985)	LRU l’atteint sur le motif cyclique
Secrétaire	la probabilité de succès optimale est \(1/e\)	la courbe mesurée place son sommet là, sans pouvoir le distinguer à \(0{,}003\) près

Voici, en une table, tout ce que ce notebook mesure.

# Recapitulatif : tout ce qui est mesure dans ce notebook, en une table.
resume = [
    ("Skis, seuil T = B : pire rapport", f"{pire_B:.4f}", "theoreme : 2 - 1/B = 1.9"),
    ("Skis, randomise B = 10000 : pire rapport", f"{pire_ratio_randomise(10000):.5f}", "theoreme : e/(e-1) = 1.58198"),
    ("Pagination cyclique k = 5, T = 600 : LRU", f"{ratio_lru_cyclique[(5, 600)]:.3f}", "theoreme : borne k = 5"),
    ("Pagination aleatoire 20 pages, k = 5 : LRU", f"{ratio_lru_aleatoire:.4f}", "pire cas adversarial, pas moyen"),
    ("Secretaire n = 1000, gamma = 1/e : P(meilleur)", f"{taux_1sur_e[1 / np.e][1]:.4f}", "theoreme : 1/e = 0.3679"),
]
print(f"{'Mesure':44s} {'valeur':>8s}   reference")
for nom, val, ref in resume:
    print(f"{nom:44s} {val:>8s}   {ref}")

Mesure                                         valeur   reference
Skis, seuil T = B : pire rapport               1.9000   theoreme : 2 - 1/B = 1.9
Skis, randomise B = 10000 : pire rapport      1.58196   theoreme : e/(e-1) = 1.58198
Pagination cyclique k = 5, T = 600 : LRU        4.839   theoreme : borne k = 5
Pagination aleatoire 20 pages, k = 5 : LRU     1.4746   pire cas adversarial, pas moyen
Secretaire n = 1000, gamma = 1/e : P(meilleur)   0.3684   theoreme : 1/e = 0.3679

Exercices

Les trois exercices s’exécutent sans erreur sur des stubs (règle C.1 du dépôt) — le notebook tourne de bout en bout, corrigés compris dans le travail de l’étudiante et de l’étudiant.

Exercice 1 — Le seuil optimal tient-il pour \(B = 20\) ?

Reprenez cout_seuil et optimum avec \(B = 20\), et balayez les seuils de 1 à 20. Le minimum du pire rapport est-il encore atteint en \(T = B\), et vaut-il \(2 - 1/20\) ?

• Indice : les deux fonctions prennent \(B\) en paramètre ; il suffit de le leur passer.
• Etape 1 : balayer \(T\) de 1 à 20 et afficher le pire rapport de chacun.
• Etape 2 : vérifier le minimum trouvé et le comparer à \(2 - 1/B\).

pire_ratio_b20 = None  # TODO etudiant : balayage des seuils pour B = 20
print("Exercice a completer : seuil optimal pour B = 20")

Exercice a completer : seuil optimal pour B = 20

Exercice 2 — Une troisième politique d’éviction

Ajoutez une politique qui évince la page la moins fréquemment demandée depuis le début (LFU), sur le modèle de lru, puis mesurez son rapport en regard de celui de LRU sur les deux motifs : le cyclique (\(k+1\) pages) et l’aléatoire (20 pages).

• Indice : tenir un compteur d’occurrences par page, et évincer celle dont le compteur est le plus petit.
• Etape 1 : écrire lfu(requetes, k) en réutilisant la structure de lru.
• Etape 2 : imprimer son rapport et celui de LRU sur les deux motifs.

rapport_lfu = None  # TODO etudiant : politique LFU et son rapport sur les deux motifs
print("Exercice a completer : troisieme politique d'eviction")

Exercice a completer : troisieme politique d'eviction

Exercice 3 — Le sommet est-il vraiment à \(1/e\) ?

Balayez \(\gamma\) de \(0{,}30\) à \(0{,}45\) par pas de \(0{,}01\), pour \(n = 1000\) et au moins 20 000 tirages par point. Où tombe le sommet mesuré, et que peut-on conclure à cette résolution ?

• Indice : l’écart-type d’une proportion \(p\) sur \(N\) tirages vaut \(\sqrt{p(1-p)/N}\) — ici environ \(0{,}003\).
• Etape 1 : calculer la courbe sur la grille fine avec taux_succes.
• Etape 2 : comparer le sommet mesuré à \(1/e\) et conclure sur ce que la mesure peut trancher.

sommet_fin = None  # TODO etudiant : grille fine autour de 1/e, n = 1000
print("Exercice a completer : sommet fin autour de 1/e")

Exercice a completer : sommet fin autour de 1/e

Conclusion

Geste	Vérifié ici	Non démontré ici
Skis	le meilleur seuil et son pire rapport, sur toutes les durées	qu’aucun algorithme ne fasse mieux, ni en déterministe ni en randomisé
Pagination	LRU, FIFO et Belady mesurés sur deux motifs	que \(k\) soit une borne pour tout algorithme en ligne
Secrétaire	la courbe de succès selon la fraction observée	que \(1/e\) soit la probabilité maximale atteignable

Les trois problèmes partagent une seule structure : une décision irréversible, prise sans la suite, jugée sur le pire cas, par le rapport à un optimum qui sait tout. C’est le même geste de méthode que dans 03 : une table finie mesure des stratégies, elle ne prouve pas qu’aucune autre ne fait mieux.

L’approfondissement 04b — Secrétaire matroïdal et k-server reprend ces objets là où ils deviennent de la recherche : le work function algorithm pour \(k\) serveurs, le secrétaire matroïdal, et deux conjectures de septembre 2026.

Références

• Belady, L. A. (1966), A study of replacement algorithms for a virtual-storage computer, IBM Systems Journal 5(2), 78–101.
• Sleator, D. D. et Tarjan, R. E. (1985), Amortized efficiency of list update and paging rules, Communications of the ACM 28(2), 202–208.
• Karlin, A. R., Manasse, M. S., McGeoch, L. A. et Owicki, S. (1994), Competitive randomized algorithms for nonuniform problems, Algorithmica 11(6), 542–571.
• Borodin, A. et El-Yaniv, R. (1998), Online Computation and Competitive Analysis, Cambridge University Press.
• Lindley, D. V. (1961), Dynamic programming and decision theory, Applied Statistics 10, 39–51 ; Dynkin, E. B. (1963), The optimum choice of the instant for stopping a Markov process, Soviet Mathematics 4, 627–629.