import numpy as np
from itertools import combinations
rng = np.random.default_rng(42)
print("numpy", np.__version__)numpy 2.4.4Complexity-04b — La semaine historique de l’algorithmique online : secrétaire matroïdal et k-server
Navigation : Index | 04 — Décider sans connaître la suite | 05 — Compter est plus dur que vérifier →
Approfondissement de 04 — Décider sans connaître la suite | Index de la série
Ce que ce notebook suppose en plus de sa base : le modèle en ligne de 04 (décision irréversible, rapport de compétitivité) et ses trois objets classiques — louer ou acheter, pagination, secrétaire. Il ajoute la structure de matroïde et son oracle d’indépendance (§2), la work function et les métriques finies (§3), puis deux conjectures de septembre 2026. Cette accrétion de niveau Recherche n’est pas nécessaire au parcours des numéros nus : sa section 1 reprend la baseline \(1/e\) désormais posée en 04 (§4), et seules les sections 2 à 4 en dépendent vraiment.
Hommage : Sahil Singla (The Matroid Secretary Conjecture is True, arXiv:2609.14555, 13/09/2026) et Christian Coester, Elias Koutsoupias, Marek Zbysiński (The k-server conjecture is true, arXiv:2609.15979, 14/09/2026).
Septembre 2026 : deux conjectures fondatrices de l’algorithmique online tombent à environ vingt-quatre heures d’écart, par deux équipes différentes. La conjecture du secrétaire matroïdal (Babaioff–Immorlica–Kleinberg, 2007 — dix-neuf ans) et la conjecture du k-server (Manasse–McGeoch–Sleator–Tarjan, ~1990 — trente-six ans). Le dépôt saisit le domaine en une fenêtre de quarante-huit heures et par trois notebooks liés : ce binôme synthétique (les deux conjectures croisées côté Complexity) et deux distillations sœurs de la série RL — RL/rl_17_k_server_wfa (k-server : WFA exact sur métriques jouets) et RL/rl_18_matroid_secretary (l’algorithme de Singla lui-même, que ce notebook cite sans reproduire, cf. §2).
Ce notebook suit la méthode de la série Complexity : faire tourner les objets (simulations Monte Carlo, implémentation exacte du work function algorithm sur petites métriques), mesurer ce qui se mesure, et citer sans reproduire les preuves. Les encarts de prudence épistémique (§5) et de gap Mathlib (§6) ferment la marche.
Prérequis : Python 3.10+, numpy. Tout est construit dans le notebook — oracles d’indépendance, work functions, métriques — pour que chaque pas soit auditable.
1. Le secrétaire classique — la baseline à battre
Le problème (garder la formulation historique) : \(n\) candidates et candidats se présentent dans un ordre aléatoire ; on ne connaît que leur rang relatif aux personnes déjà vues ; toute acceptation est irréversible. Objectif : maximiser la probabilité d’accepter la meilleure personne.
L’algorithme \(1/e\) (la règle des 37 %) : on observe sans accepter les \(\lfloor n/e \rfloor\) premier·e·s arrivant·e·s, puis on accepte la première personne qui surpasse toutes les observées. La probabilité de capturer le meilleur tend vers \(1/e \approx 0{,}368\) — c’est la référence que toute la littérature du secrétaire matroïdal cite comme point de départ. (04 — Décider sans connaître la suite §4 pose cette baseline ; elle est reprise ici parce que tout le §2 s’y adosse.)
def secretaire_classique(n, perm):
"""Renvoie True si l'algorithme 1/e selectionne le meilleur de la permutation perm (rangs 0..n-1)."""
seuil = max(1, int(round(n / np.e)))
meilleur_vu = max(perm[:seuil], default=-1)
for x in perm[seuil:]:
if x > meilleur_vu:
return x == n - 1
return False
def monte_carlo_classique(n, n_runs=20_000):
succes = 0
for _ in range(n_runs):
perm = rng.permutation(n)
succes += secretaire_classique(n, perm)
return succes / n_runs
for n in (20, 100, 1000):
p = monte_carlo_classique(n)
print(f"n={n:5d} P(meilleur selectionne) = {p:.4f} (theorie: 1/e = {1/np.e:.4f})")n= 20 P(meilleur selectionne) = 0.3876 (theorie: 1/e = 0.3679)
n= 100 P(meilleur selectionne) = 0.3724 (theorie: 1/e = 0.3679)
n= 1000 P(meilleur selectionne) = 0.3741 (theorie: 1/e = 0.3679)Lecture du résultat
La probabilité mesurée converge vers \(1/e \approx 0{,}368\) — l’algorithme récupère le meilleur candidat un peu plus d’une fois sur trois, et c’est optimal pour ce modèle. Tout l’enjeu du secrétaire matroïdal est de savoir ce qui survit quand on ne peut plus tout accepter : sélectionner plusieurs éléments sous une contrainte de structure, avec la même arrivée aléatoire irréversible.
2. Le secrétaire matroïdal — la conjecture tombée
Le problème : les éléments arrivent en ordre aléatoire, chacun porte une valeur positive ; à chaque arrivée, on décide immédiatement et irréversiblement de l’accepter ou non ; l’ensemble accepté doit rester indépendant pour un matroïde connu uniquement via un oracle d’indépendance (et le nombre total d’éléments \(n\)). Objectif : maximiser l’espérance de la somme des valeurs acceptées, comparée à l’optimum offline (le poids maximum d’un ensemble indépendant, calculable par l’algorithme glouton sur toutes les valeurs triées).
La conjecture (Babaioff–Immorlica–Kleinberg 2007) : il existe un algorithme à compétitivité constante — un \(\alpha > 0\) indépendant de \(n\) et du matroïde tel que \(\mathbb{E}[\text{valeur acceptée}] \geq \alpha \cdot \mathrm{OPT}\).
Ce qu’annonce le preprint de Singla : un algorithme online qui accepte chaque élément de l’optimum offline avec probabilité au moins \(1/4\) — compétitivité constante, alors que l’algorithme ne connaît pas le matroïde à l’avance (il n’a que l’oracle d’indépendance et \(n\)). Les meilleurs ratios connus restaient en \(O(\log\log r)\), où \(r\) est le rang du matroïde (Lachish 2014 ; preuve simplifiée par Feldman–Svensson–Zenklusen 2015).
Nous implémentons deux matroïdes classiques et deux stratégies online de référence — puis mesurons leur compétitivité face à \(\mathrm{OPT}\) :
# --- Deux matroïdes, chacun expose independant(S) -> bool ---
class MatroideUniforme:
"""Rang k sur n elements : independant ssi |S| <= k."""
def __init__(self, n, k):
self.n, self.k = n, k
def independant(self, S):
return len(S) <= self.k
class MatroideGraphique:
"""Aretes d'un graphe : independant ssi acyclique (via union-find)."""
def __init__(self, aretes):
self.aretes = aretes # liste de paires (u, v)
def independant(self, S):
parent = {}
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for i in S:
u, v = self.aretes[i]
parent.setdefault(u, u); parent.setdefault(v, v)
ru, rv = find(u), find(v)
if ru == rv:
return False
parent[ru] = rv
return True
def opt_offline(matroide, valeurs):
"""Sur un matroide, le glouton sur valeurs decroissantes est optimal : poids max d'un independant."""
acceptes = []
for i in np.argsort(-valeurs):
if matroide.independant(acceptes + [int(i)]):
acceptes.append(int(i))
return float(sum(valeurs[i] for i in acceptes)), acceptes# --- Deux strategies online de reference (ni l'une ni l'autre n'est l'algorithme de Singla) ---
def online_glouton(matroide, valeurs, gamma=0.5):
"""(a) Glouton pur : accepte tout element independant, des son arrivee."""
n = len(valeurs)
ordre = rng.permutation(n)
acceptes = []
for idx in ordre:
if matroide.independant(acceptes + [int(idx)]):
acceptes.append(int(idx))
return float(sum(valeurs[i] for i in acceptes))
def online_seuil_mediane(matroide, valeurs, gamma=0.5):
"""(b) Glouton a seuil : observe une fraction gamma des arrivees sans accepter,
puis accepte tout element independant dont la valeur depasse la mediane observee."""
n = len(valeurs)
ordre = rng.permutation(n)
t_obs = int(gamma * n)
mediane = float(np.median(valeurs[ordre[:t_obs]]))
acceptes = []
for idx in ordre[t_obs:]:
if valeurs[idx] >= mediane and matroide.independant(acceptes + [int(idx)]):
acceptes.append(int(idx))
return float(sum(valeurs[i] for i in acceptes))
def competitivite(matroide, valeurs, strategie, n_runs=2_000):
opts, gains = [], []
for _ in range(n_runs):
opts.append(opt_offline(matroide, valeurs)[0])
gains.append(strategie(matroide, valeurs))
return float(np.mean(gains) / np.mean(opts))# --- Mesures : matroide uniforme (rang 3 sur 12) puis graphique (grille 3x4) ---
mu = MatroideUniforme(12, 3)
val_u = rng.uniform(1.0, 10.0, size=12)
grille = [(r, c) for r in range(3) for c in range(4)]
aretes = []
for r in range(3):
for c in range(4):
if c < 3: aretes.append(((r, c), (r, c + 1)))
if r < 2: aretes.append(((r, c), (r + 1, c)))
mg = MatroideGraphique(aretes)
val_g = rng.uniform(1.0, 10.0, size=len(aretes))
print("Matroide uniforme (rang 3 / 12 elements), OPT =", round(opt_offline(mu, val_u)[0], 2))
print(" glouton pur : competitivite =", round(competitivite(mu, val_u, online_glouton), 4))
print(" glouton a seuil : competitivite =", round(competitivite(mu, val_u, online_seuil_mediane), 4))
print()
print("Matroide graphique (grille 3x4,", len(aretes), "aretes), OPT =", round(opt_offline(mg, val_g)[0], 2))
print(" glouton pur : competitivite =", round(competitivite(mg, val_g, online_glouton), 4))
print(" glouton a seuil : competitivite =", round(competitivite(mg, val_g, online_seuil_mediane), 4))Matroide uniforme (rang 3 / 12 elements), OPT = 24.93
glouton pur : competitivite = 0.6519
glouton a seuil : competitivite = 0.729
Matroide graphique (grille 3x4, 17 aretes), OPT = 81.69
glouton pur : competitivite = 0.8346
glouton a seuil : competitivite = 0.4307Lecture des mesures
Les deux stratégies de référence échangent leurs rôles selon l’instance. Sur le matroïde uniforme, le glouton à seuil domine (0,729 contre 0,652) : la phase d’observation écarte les petites valeurs et préserve le rang pour les grandes. Sur le matroïde graphique, c’est l’inverse (glouton pur 0,835, glouton à seuil 0,431) : le seuil en médiane rejette des arêtes que la structure du matroïde rendait rentables, et la phase d’observation devient un handicap. Le seuil optimal est instance-dépendant — aucun réglage ne domine sur tous les matroïdes. Aucune des deux n’est l’algorithme de Singla : le résultat annoncé par le preprint — accepter chaque élément de l’optimum avec probabilité \(\geq 1/4\), sans connaître le matroïde à l’avance — est d’une autre nature. Il garantit la constante dans le pire cas, pour tout matroïde, avec pour seule interface l’oracle d’indépendance. Nos simulations mesurent le dilemme que le théorème résout : entre accepter tôt (structure) et attendre (valeur), aucune heuristique simple ne domine sur tous les matroïdes.
3. k-server — le work function algorithm, implémenté
Le problème (Manasse–McGeoch–Sleator–Tarjan ~1990) : \(k\) serveurs occupent des points d’un espace métrique ; une séquence de requêtes (adversariale) arrive, chaque requête est un point ; à chaque requête, un serveur doit s’y déplacer, au coût de la distance parcourue. Objectif : minimiser le coût total, comparé au coût de l’optimum offline qui connaît toute la séquence. Trois quantités à ne pas confondre. Borne inférieure prouvée (Manasse–McGeoch–Sleator 1990) : aucun algorithme déterministe n’atteint un ratio inférieur à \(k\) sur les métriques à plus de \(k\) points — \(k\) est le plancher, atteint déjà pour \(k = 2\) et \(n = k+1\). Meilleure garantie prouvée avant 2026 : le work function algorithm (WFA) est \((2k-1)\)-compétitif sur tout espace métrique (Koutsoupias–Papadimitriou 1995). La conjecture : le WFA atteint exactement le plancher — ratio \(k\) sur tout espace métrique — c’est ce que le preprint de Coester–Koutsoupias–Zbysiński annonce.
Le WFA, de l’aveu général, est « l’algorithme évident qu’on n’arrivait pas à analyser » : à chaque requête, maintenir la work function \(W_t(S)\) = coût minimal pour avoir servi les \(t\) premières requêtes et se trouver en configuration \(S\) ; servir la requête courante par le mouvement qui minimise (coût immédiat + work function résultante) — un regard à la fois vers le passé optimal et vers le futur.
Nous l’implémentons exactement sur deux petites métriques — la ligne uniforme à \(m\) points et le cycle \(C_m\) où l’on peut passer par le bord — où la work function se calcule par programmation dynamique sur les \(\binom{m}{k}\) configurations, pour \(k = 2\) serveurs :
# --- Work function algorithm exact pour k=2, metrique parametree (ligne / cycle) ---
def make_ligne(m):
return lambda i, j: abs(i - j)
def make_cycle(m):
"""Cycle C_m : d(i, j) = min(|i-j|, m-|i-j|) -- on peut passer par le bord."""
return lambda i, j: min(abs(i - j), m - abs(i - j))
def configs(m, k=2):
return list(combinations(range(m), k))
def transition(S1, S2, d):
"""Cout minimal pour passer de la config S1 a la config S2 (assignment k=2 : deux affectations)."""
if S1 == S2:
return 0.0
(a, b), (c, e) = S1, S2
return float(min(d(a, c) + d(b, e), d(a, e) + d(b, c)))
def work_functions(m, init, requetes, d, k=2):
"""W[t][S] = cout minimal pour servir requetes[:t] et finir en S (S doit contenir requetes[t-1]).
Renvoie la liste des work functions W_0..W_T (dictionnaires config -> cout)."""
CFG = configs(m, k)
W = [{} for _ in range(len(requetes) + 1)]
W[0] = {S: transition(init, S, d) for S in CFG} # cout initial de couverture
for t, r in enumerate(requetes, start=1):
for S in CFG:
if r not in S:
continue # une config finale doit contenir le point requete
W[t][S] = min(W[t - 1][S2] + transition(S2, S, d) for S2 in W[t - 1])
return W
def jouer_wfa(m, init, requetes, d, k=2):
"""Simule la trajectoire WFA : a chaque requete, bouge le serveur minimisant cout + W_t(resultat)."""
W = work_functions(m, init, requetes, d, k)
S = tuple(sorted(init))
cout_total = 0.0
for t, r in enumerate(requetes, start=1):
best, best_cout = None, float('inf')
for i in range(len(S)):
if S[i] == r:
cand, cout_mvt = S, 0.0 # un serveur est deja sur la requete
elif r in S:
continue # mouvement domine : un autre serveur occupe deja la requete
else:
cand = tuple(sorted(S[:i] + S[i+1:] + (r,)))
cout_mvt = float(d(S[i], r))
total = cout_mvt + W[t][cand]
if total < best_cout:
best, best_cout = cand, total
# le cout REEL paye : mouvement effectif depuis S vers best
cout_total += transition(S, best, d)
S = best
opt = min(W[len(requetes)].values())
return cout_total, opt
def jouer_greedy(m, init, requetes, d):
"""Baseline : bouge toujours le serveur le plus proche de la requete."""
servs = list(init)
cout_total = 0.0
for r in requetes:
i = min(range(len(servs)), key=lambda j: d(servs[j], r))
cout_total += d(servs[i], r)
servs[i] = r
return cout_total# --- Mesures : le piege canonique du CYCLE C_5, puis la ligne en contraste ---
# Cycle a 5 points, serveurs en (0, 1) -- tous deux du meme cote -- requetes alternant 3, 4.
# OPT paie une reorganisation (0->4 par le bord a cout 1, 1->3 a cout 2) puis sert tout a 0.
# Le greedy, lui, suit l'alternance : a chaque requete le serveur le plus proche bascule de 3 a 4.
d_c5 = make_cycle(5)
k = 2
c_wfa, opt = jouer_wfa(5, (0, 1), [3, 4] * 30, d_c5)
c_gr = jouer_greedy(5, (0, 1), [3, 4] * 30, d_c5)
print("CYCLE C_5, init (0,1), requetes [3,4] x 30 (T=60) :")
print(f" OPT offline = {opt:.0f}")
print(f" WFA = {c_wfa:.0f} ratio = {c_wfa / opt:.3f} (borne k = {k})")
print(f" greedy plus-proche = {c_gr:.0f} ratio = {c_gr / opt:.1f}")
print()
for T in (60, 240):
cw, o = jouer_wfa(5, (0, 1), [3, 4] * T, d_c5)
cg = jouer_greedy(5, (0, 1), [3, 4] * T, d_c5)
print(f" T={T * 2:4d} requetes : ratio WFA = {cw / o:.3f} ratio greedy = {cg / o:.1f} (greedy croit avec T)")
print()
d_l8, m8, init8 = make_ligne(8), 8, (0, 7)
alea = [int(x) for x in rng.integers(0, m8, size=60)]
cw2, o2 = jouer_wfa(m8, init8, alea, d_l8)
cg2 = jouer_greedy(m8, init8, alea, d_l8)
print("LIGNE a 8 points, sequence aleatoire (60 requetes) -- le regime moyen est facile :")
print(f" OPT offline = {o2:.0f} ratio WFA = {cw2 / o2:.3f} ratio greedy = {cg2 / o2:.3f}")CYCLE C_5, init (0,1), requetes [3,4] x 30 (T=60) :
OPT offline = 3
WFA = 5 ratio = 1.667 (borne k = 2)
greedy plus-proche = 61 ratio = 20.3
T= 120 requetes : ratio WFA = 1.667 ratio greedy = 40.3 (greedy croit avec T)
T= 480 requetes : ratio WFA = 1.667 ratio greedy = 160.3 (greedy croit avec T)
LIGNE a 8 points, sequence aleatoire (60 requetes) -- le regime moyen est facile :
OPT offline = 58 ratio WFA = 1.000 ratio greedy = 1.000Lecture des mesures
Sur le cycle \(C_5\), l’optimum paie une réorganisation unique (amener les deux serveurs sur 3 et 4 : coût total 3) puis sert toute la séquence à coût nul — le WFA découvre ce plan et paie 5, ratio mesuré 1,67, sous la borne \(k = 2\). Le greedy, lui, suit l’alternance : à chaque requête le serveur le plus proche bascule entre 3 et 4, coût 1 par requête — son ratio vaut 20,3 pour 60 requêtes, 160,3 pour 480 : il croît linéairement avec la longueur de la séquence, c’est la définition d’un algorithme non compétitif (aucun ratio \(c\) borné ne le majore). C’est exactement le régime pour lequel la conjecture existe : le pire cas adversarial, pas le cas moyen — sur la ligne avec requêtes aléatoires, greedy et WFA font jeu égal (ratios \(= 1\) ici). Ce que le preprint de Coester–Koutsoupias–Zbysiński annonce : le WFA atteint le ratio \(k\) sur tout espace métrique et toute séquence — la technique (représentation algébrique de la work function, chaque valeur comme déterminant de \(k\) colonnes, potentiel sur paires de coordonnées) est citée §5, pas reproduite ici.
4. Le double visage du binôme
Ce qui rend la saisie commune de ces deux résultats nécessaire — c’est le même problème (décisions irréversibles sous incertitude, évaluées au ratio compétitif) résolu par deux philosophies exactement opposées :
| Secrétaire matroïdal (Singla) | k-server (Coester–Koutsoupias–Zbysiński) | |
|---|---|---|
| Modèle d’entrée | ordre aléatoire (hypothèse distributionnelle) | séquence adversariale (aucune hypothèse) |
| Arme | randomisation (accepte chaque élément de l’OPT avec proba \(\geq 1/4\)) | déterminisme (le WFA, un algorithme unique) |
| Analyse | espérance, probabilités | analyse amortie, fonction potentiel |
| Conjecture ouverte depuis | 2007 (dix-neuf ans) | ~1990 (trente-six ans) |
| Outil structurel | matroïdes (oracle d’indépendance) | algèbre des work functions (déterminants, algèbre tropicale) |
| Ce que la machine mesure | compétitivité Monte Carlo \(\approx\) constante | ratio pire-cas \(\leq k\) sur adversaire construit |
# Recapitulatif chiffre des mesures de ce notebook
resume = [
("Secretaire classique n=1000 : P(meilleur)", f"{monte_carlo_classique(1000, 5000):.4f}", "1/e = 0.3679"),
("Matroide uniforme : glouton pur", f"{competitivite(mu, val_u, online_glouton):.4f}", "aucune garantie generale (le 1/4 est celui de Singla)"),
("Matroide uniforme : glouton a seuil", f"{competitivite(mu, val_u, online_seuil_mediane):.4f}", "aucune garantie generale (seuil optimal selon l'instance)"),
("k-server cycle C5 : ratio WFA", f"{c_wfa / opt:.3f}", f"borne k = {k}"),
("k-server cycle C5 : ratio greedy", f"{c_gr / opt:.1f} (croit avec T)", "non competitif (2k-1 est la garantie du WFA, KP95)"),
]
print(f"{'Mesure':46s} {'valeur':>8s} reference")
for nom, val, ref in resume:
print(f"{nom:46s} {val:>8s} {ref}")Mesure valeur reference
Secretaire classique n=1000 : P(meilleur) 0.3782 1/e = 0.3679
Matroide uniforme : glouton pur 0.6520 aucune garantie generale (le 1/4 est celui de Singla)
Matroide uniforme : glouton a seuil 0.7314 aucune garantie generale (seuil optimal selon l'instance)
k-server cycle C5 : ratio WFA 1.667 borne k = 2
k-server cycle C5 : ratio greedy 20.3 (croit avec T) non competitif (2k-1 est la garantie du WFA, KP95)5. Prudence épistémique — ce que ce notebook cite sans le vérifier
Les deux papiers sont des preprints de un à deux jours au moment de la rédaction (soumis les 13 et 14/09/2026), sans évaluation par les pairs publiée, sans écho communautaire enregistré. Les formulations de ce notebook disent donc « le preprint annonce », « la preuve annoncée » — jamais « le théorème » ni « résolu » sans qualificatif. C’est la même discipline que pour la semaine discrepancy (#15944) : la saisie pédagogique peut être immédiate, la canonisation ne peut pas l’être.
Trois niveaux à ne pas confondre, dans ce notebook :
- Mesuré : les probabilités et ratios ci-dessus, produits par les simulations de §1–§3 (reproductibles, seed fixé).
- Cité : les énoncés des deux preprints (compétitivité \(1/4\) sans connaissance du matroïde ; ratio \(k\) du WFA sur tout espace métrique) — des claims d’auteurs, lus sur les abstracts.
- Absent : les preuves elles-mêmes — non lues ligne à ligne ici, non formalisées, non vérifiées mécaniquement.
Si l’une des deux preuves s’effondre en évaluation, ce notebook garde sa valeur pédagogique (les objets, le dilemme, les implémentations de référence) et perdra seulement ses deux phrases d’ouverture — il est conçu pour ça.
6. Encart Mathlib — ce qui existe, ce qui manque
Même exercice que pour 03b — Hartmanis–Stearns : où est la frontière de Mathlib (v4.33.0 au jour de rédaction) sur ces objets ?
- Matroïdes : présents —
Mathlib.Combinatorics.Matroidcouvre indépendance, rang, dualité, matroïdes graphiques. Le vocabulaire du §2 est formalisable dès aujourd’hui (définir « un ensemble est indépendant » et l’algorithme glouton offline y trouverait son cadre). - Algorithmique online : absente — pas de
competitive ratio, pas desecretary, pas dek-server, pas dework function, pas de notion d’algorithme online face à une séquence de requêtes. Formaliser la compétitivité exigerait une couche « adversaire + algorithme + ratio sur toutes les entrées » qui n’existe pas plus que la coucheTIME(f)du notebook 03. - Le pont naturel si un jour ce grain passe en Lean : la work function est décidable (une DP finie) — le calcul est implémentable, c’est la preuve de ratio (le potentiel sur paires de coordonnées du preprint) qui serait le travail dur.
La suite logique côté dépôt serait un online_lean quand les preuves auront mûri — pas avant.
7. Exercices
Trois exercices, stubs exécutables sans erreur (règle C.1 du dépôt) — les corrigés restent la propriété de l’étudiante et de l’étudiant.
# Exercice 1 -- Matroide de partition : les elements portent une couleur parmi 3 groupes,
# et un ensemble est independant ssi il contient au plus q_i elements de chaque groupe i.
# Implementer l'oracle puis mesurer la competitivite du glouton a seuil dessus.
# Indice : independant(S) = toutes les tailles d'intersection groupe_i ∩ S <= q_i.
class MatroidePartition:
def __init__(self, couleurs, quotas):
self.couleurs = couleurs # liste : couleur de chaque element
self.quotas = quotas # dict : quota par couleur
def independant(self, S):
# TODO etudiant
return None
# Exercice 2 -- k-server sur l'ETOILE a m feuilles : point 0 = le centre,
# points 1..m = les feuilles ; d(i, j) = 1 si l'un est le centre, 2 entre
# deux feuilles distinctes. Implementer make_etoile(m) puis chercher une
# sequence adversariale pour greedy (deux serveurs sur des feuilles, requetes
# alternant deux autres feuilles) et verifier que WFA reste sous la borne k = 2.
# Indice : OPT paie une reorganisation unique de cout 4 (placer les deux serveurs
# sur les feuilles requetees) puis sert tout a 0 -- greedy, lui, paie 2 par requete.
def make_etoile(m):
# TODO etudiant
return None
# Exercice 3 -- Secretaire classique avec valeurs log-normales (queue lourde) au lieu
# de valeurs uniformes : montrer que la strategie de RANG (rejeter les n/e premiers
# observes, puis accepter le premier record relatif) reste valable quelle que soit la
# loi des valeurs -- mesurer la probabilite de capturer le maximum, la comparer a 1/e.
# Indice : la strategie n'utilise que l'ORDRE RELATIF des valeurs ; pour des valeurs
# i.i.d. d'une loi continue, les rangs forment une permutation uniforme -- la garantie
# 1/e est distribution-free, la queue lourde ne change rien.
def secretaire_lognormal(n, mu=0.0, sigma=1.0):
# TODO etudiant
return None
print("Exercices a completer (stubs conformes C.1 : le notebook s'execute de bout en bout).")Exercices a completer (stubs conformes C.1 : le notebook s'execute de bout en bout).8. Conclusion
Ce notebook a saisi le domaine online côté Complexity : la baseline \(1/e\) mesurée (§1), le dilemme du secrétaire matroïdal simulé sur deux matroïdes avec oracles d’indépendance (§2), le work function algorithm implémenté exactement et confronté à ses bornes sur séquence adversariale (§3), le tableau du double visage randomisation/déterminisme (§4). Les deux preprints sont cités au conditionnel de rigueur (§5), le gap Mathlib est cartographié (§6), et trois exercices prolongent chacun une section (§7).
Cross-links : Complexity-03b (même méthode : faire tourner, confronter à Mathlib) · RL/rl_17_k_server_wfa (k-server : WFA exact sur métriques jouets — même preprint Coester–Koutsoupias–Zbysiński, en profondeur) · RL/rl_18_matroid_secretary (l’algorithme de Singla implémenté, garantie 1/4 comme banc de mesure — la profondeur que ce notebook cite sans reproduire) · RL/rl_16_dream_rsi (Dream-RSI : l’exploration explicite programmable — l’autre bout du spectre online) · GameTheory (théorie des jeux à information incomplète) · la semaine discrepancy (#15944 : Komlós et Beck-Fiala, l’autre « moment de domaine » récent).