Repository navigation
[Complexity] Refondre la progression pedagogique de la serie — curriculum en accretion, socle avant le zoo Aaronson #17063
Description
Activity
Proposition de curriculum — livrable acceptance 1 (arbitrage user)
Grain: DEEP/docs — lane myia-po-2025:CoursIA — prev: MED/guard #17025
Lecture préalable faite firsthand : les 4 notebooks (01-03 sur
main, 04 sur la branchefeature/16781-veine4-dequantificationde #17045), le README de la série, la règlenotebook-accretion-numbering(canonique = numéros nus ; lettre = approfondissement hors chemin principal ; première accrétion =b). La décision appartient au user — ce qui suit est une recommandation decision-ready, chaque point où un arbitrage réel existe est marqué[ARB].Le diagnostic en une phrase
La série commence par des résultats (hiérarchie 1965, conjectures sept. 2026, permanente 2011, stabilisateurs 2004) sans jamais poser les trois gestes qui les rendent lisibles : compter des pas, réduire un problème à un autre, lire un théorème de séparation.
Curriculum cible — l'ordre canonique
Position Notebook Statut Entrée requise (uniquement ce qui précède) Public 01 Compter des pas — la mesure de coût NOUVEAU aucun (Python de base) Découverte 02 P, NP et le sens d'une réduction NOUVEAU 01 Découverte 03 Hartmanis–Stearns — hiérarchie en temps (1965) renum 01→03 (allégé) 01, 02 Licence 04 Conjectures online — secrétaire matroïdal, k-server renum 02→04 + lettre d'entrée 02 (réductions) ; 03 recommandé Recherche 05 Aaronson–Arkhipov — permanente, #P, BosonSampling renum 03→05 + lettre d'entrée 02 ; 03 recommandé Recherche 06 Déquantification — Gottesman–Knill (Aaronson–Gottesman 2004) #17045 puis renum 04→06 + lettre d'entrée 02 ; 05 recommandé (contexte #P) Recherche Lire les numéros nus dans l'ordre redevient le speed-run : socle (01-02) → premier théorème (03) → zoo Aaronson (04-06). Les trois avancés gardent toute leur place (demande user), comme matière de recherche après le socle, chacun ouvert par une lettre d'entrée qui pose SES prérequis au lieu de les supposer.
Les deux notebooks de socle
01 — Compter des pas (nouveau). Ce qui existe déjà dans la série et en sort : le §1 de l'actuel 01 (« Le geste fondateur : compter les pas », machines multi-rubans, comptes exacts, palindromes, les trois croissances
$n\log n$ /$n^2$ /$2^n$ mesurées) est exactement ce socle — il déménage et devient le cœur du nouveau 01. Y entrent : la distinction opération/seconde, la croissance comme objet mesuré, la bascule force-brute/DP sur subset-sum comme première « différence d'ordre de grandeur vécue ». Exercices : prédire le point de bascule (repris de l'exercice 1 actuel).02 — P, NP et le sens d'une réduction (nouveau). Matériau réutilisable nommé par l'issue : le banc subset-sum force brute vs DP de l'actuel 01 (§2 « Séparer ») et le backtracking de
Sudoku-15. Contenu : certificat et vérification ; NP comme « vérifiable en polynomial », pas « non résoluble » ; UNE réduction exécutée de bout en bout (le vrai geste : transformer une instance, pas la citer) ; pourquoi l'exponentielle est le mur de l'ingénieur (le$2^n$ du 01 rendu conceptuel). Sans cuisine NP-complète exhaustive — la réduction est l'outil que 04-06 presupposent.Ce que l'actuel 01 perd (§1 vers nouveau 01, §2 vers nouveau 02), il le gagne en densité : le 03 renuméroté ouvre directement sur la diagonalisation, son vrai sujet.
Lettres d'entrée des avancés + accrétions
Chaque avancé ouvre sur une section « Ce que ce notebook suppose » qui pose ses prérequis au lieu de les supposer — exécutable quand c'est possible :
- 04 (online) : matroïdes via oracle d'indépendance (le banc existe déjà §2), analyse compétitive — définition, un exemple mesuré, ce que « conjecture tombée » veut dire épistémiquement (le §5 actuel « Prudence épistémique » est déjà excellent, il monte en tête).
- 05 (permanente) : permanente définie exécutée (§1 actuel), #P relu depuis 02 (compter les certificats vs en vérifier un), FPRAS en une phrase avant d'en parler.
- 06 (stabilisateurs) : le formalisme est déjà construit from scratch (§1-2 de la branche) ; la lettre d'entrée situe le calcul quantique en 10 lignes depuis 02/#P — pourquoi « simuler classiquement » est une question de complexité.
Lettres d'accrétion (obscur/historique non nécessaire pour avancer — demande user) : à la correction du curriculum, chaque déménagement de matière hors chemin principal devient une lettre
bsur sa position d'origine, pas une suppression (non-but : ne pas retirer du contenu validé). Candidats identifiés : l'encart Mathlib du 03 (gapComputability/Complexity) peut rester dans le corps — il est une signature de la série ; en revanche les digressions historiques des bancs (chronologie 1993/2007/2026, détails des preprints) relèvent de la lettre d'entrée ou d'une accrétion04b/05bsi elles croissent. Rien n'est déplacé en accrétion dans ce curriculum sans besoin mesuré — poser des lettres vides serait l'anti-convention.Étiquetage lecteurs
En tête de chaque notebook + colonne README (à la manière des « 4 types » QC) : Découverte (01-02), Licence (03), Recherche (04-06). L'étiquette dit à qui le notebook s'adresse, pas son mérite.
Articulation #17045 (ouverte)
Deux options, indifférentes au contenu du PR :
- (a) merger Add: Complexity-04 — Gottesman-Knill comme arbitre executable (curation Aaronson veine 4) #17045 tel quel (
Complexity-04-Aaronson-Dequantification-Stabilizer), puis la vague de renum le déplace en 06 — chaque renum est une PR séparée portant le curriculum approuvé comme argument pédagogique écrit ; - (b) retitrer la branche avant merge (économie d'un renum, au prix d'un force-push sur une PR en review).
Recommandation : (a) — le renum est mécanique une fois le curriculum approuvé, et (b) touche une PR en cours de review d'une autre lane.
Plan de livraison (après approbation user)
- PR
renum01→03 (allégé de §1/§2) · 2. PR nouveau 01 · 3. PR nouveau 02 · 4. PRrenum02→04 + lettre d'entrée · 5. PRrenum03→05 + lettre d'entrée · 6. PRrenum04→06 + lettre d'entrée (après merge Add: Complexity-04 — Gottesman-Knill comme arbitre executable (curation Aaronson veine 4) #17045) · 7. PR README (gradation visible + étiquettes). Chaque PR : une par notebook déplacé ou créé (règlenotebook-accretion-numbering, acceptance 2), cellules modifiées re-exécutées (C.2).
Points d'arbitrage
[ARB]- [ARB] Le socle comme deux notebooks nouveaux (01-02) implique de renuméroter les quatre existants. Alternative rejetée : socle ailleurs que dans la série — le canonique (numéros nus) serait toujours sans socle, le problème demandé par le user resterait entier. Si le renumérotage en bloc dérange, l'alternative minimale est un unique nouveau 01 « Compter des pas + réduire » (plus épais, un seul décalage).
- [ARB] Position du nouveau 02 : P/NP avant Hartmanis–Stearns (recommandé : la hiérarchie en temps se lit mieux une fois « réduction » acquis) ou après (lecture historique 1965 → P/NP).
- [ARB] Option (a)/(b) pour Add: Complexity-04 — Gottesman-Knill comme arbitre executable (curation Aaronson veine 4) #17045 ci-dessus.
Aucune PR avant arbitrage (non-but : décider sans le user). À l'approbation, la lane livre la séquence ci-dessus.
Décision ai-01 écrite en tête du body : c'est lui que les lanes lisent.
En résumé, six notebooks principaux simples, du plus accessible au plus exigeant : compter des pas, vérifier ou trouver, hiérarchie, en ligne, compter contre vérifier, simulation quantique. Les quatre notebooks actuels deviennent leurs accrétions
03bà06b, sans perte de contenu validé.Lane :
myia-po-2025:CoursIA. Premier geste : le séquencement des PRs, posté ici. #17362 passe d'abord.[CLAIMED-AMEND] lane myia-po-2025:CoursIA -- paths: MyIA.AI.Notebooks/Complexity/**, MyIA.AI.Notebooks/RL/rl_17_k_server_wfa.ipynb, MyIA.AI.Notebooks/RL/rl_18_matroid_secretary.ipynb
Grain: DEEP/notebook-python — lane myia-po-2025:CoursIA — prev: DEEP/notebook-lean #17556
Séquencement des PRs (réponse à la décision ai-01 du 23/09)
Le point dur. Les quatre notebooks actuels occupent les identifiants 01 à 04. Un nouveau 01 ne peut pas coexister avec
Complexity-01-HartmanisStearns-…, et un actuel ne peut devenirNbqu'une fois sa base N présente. Si l'on déplace directement chaque actuel vers sa lettre, ces deux contraintes obligent à livrer par le haut : 05 et 06, puis 03 et 04, et 01-02 en dernier. Les principaux seraient alors écrits avant leurs prérequis, ce qui contredit la règle 1 (« ne suppose que ce qui le précède ») et l'ordre de valeur.Retenu : un décalage de deux, puis une descente en lettre par PR. Chaque actuel est renommé deux fois, et aucun état intermédiaire ne viole les contraintes.
PR Contenu Complexity/après mergePR1 — 01 + 02 nouveaux 01 Compter des pas et 02 Vérifier ou trouver, avec la réduction subset-sum exécutée de bout en bout. Les quatre actuels passent de 01-04 à 03-06 : git mv, barres de navigation, README et liens entrants, sans toucher aux cellules de code.01 neuf, 02 neuf, 03 HS, 04 Online, 05 AA, 06 Gottesman PR2 — 03 nouveau 03 Plus de temps, plus de problèmes. HS 03 → 03b, allégé de §1-§2 (désormais dans 01-02) et re-exécuté.01-03 neufs, 03b HS, 04 Online, 05 AA, 06 G PR3 — 04 nouveau 04 Décider sans connaître la suite. Online 04 → 04b.01-04 neufs, 03b, 04b, 05 AA, 06 G PR4 — 05 nouveau 05 Compter est plus dur que vérifier. AA 05 → 05b.01-05 neufs, 03b-05b, 06 G PR5 — 06 nouveau 06 Simuler un circuit quantique classiquement. Gottesman 06 → 06b.01-06 principaux, 03b-06b Les deux contraintes, vérifiées à chaque état :
- Identifiants uniques. PR1 libère 01-02 dans le commit qui les remplit. Ensuite, chaque PRk libère
0ken le transformant en0kbdans le commit qui crée le nouveau0k. - Pas de lettre sans base. Aucune lettre n'existe avant PR2, et chaque
bnaît dans la PR qui crée sa base. La tolérance d'une PR de transition n'est pas consommée. - Ordre de valeur. 01 et 02 arrivent en premier, ensemble. Entre deux PRs, le chemin principal s'ouvre toujours sur deux notebooks Découverte. Les actuels pas encore descendus restent en 03-06, derrière eux, et le README les étiquette « Recherche » jusqu'à leur descente.
Préalable #17362. PR1 renomme l'actuel 02, donc elle ne s'ouvre qu'après le merge de #17362. En attendant, j'écris 01 et 02 dans un worktree. Les renommages se font au dernier moment, sur un
mainqui contient déjà le correctif. #17362 ajoute aussi des liens deRL/rl_17etrl_18vers l'actuel 02 : PR1, puis PR3, les suivent.Findings Hermes sur les notebooks actuels. Ils suivent le notebook déplacé : chaque PR de descente les reprend dans son body, avec l'état de chacun.
Coût assumé : huit renommages au lieu de quatre. Mesuré sur
origin/main, seuls le README de la série et les barres de navigation internes citent ces noms de fichier, plus les deux notebooks RL une fois #17362 mergée. Le catalogue généré, les blocsCATALOG-STATUSet_quarto.ymlne listent pas la série, et restent intacts.Rythme. Une seule PR ouverte à la fois pour cette série, sous le plafond de WIP de la lane.
- Identifiants uniques. PR1 libère 01-02 dans le commit qui les remplit. Ensuite, chaque PRk libère
- added a commit that references this issue
on Sep 23, 2026 - added a commit that references this issue
on Sep 25, 2026 - added a commit that references this issue
on Sep 25, 2026 Séquencement des PRs restantes — curriculum #17063 (premier geste dû par la décision ai-01 du 23/09)
Grain: MED/docs — lane myia-po-2025:CoursIA — prev: MED/notebook-dotnet #18815
État mesuré au 02/10 (origin/main, confrontation body ↔ réel)
Position Cible (tableau arbitré) État mesuré sur main01 Compter des pas Livré — Complexity-01-StepCounting.ipynb02 Vérifier ou trouver (P, NP, réduction) Livré — Complexity-02-P-NP-Reduction.ipynb+ correctif #17362 mergé 23/09 (préalable satisfait)03 Hiérarchie / diagonalisation simple Livré — Complexity-03-TimeHierarchy.ipynb+03b(Hartmanis–Stearns) +03c(zoo navigation)04 Algorithmes en ligne Livré — Complexity-04-OnlineAlgorithms-Python.ipynb+04b(secrétaire matroïdal, k-server)05 #P, déterminant contre permanente En attente — Complexity-05-AaronsonArkhipov-PermanenteBosonSampling.ipynb(matière de recherche de l'ancien 03) occupe le chemin principal sans sa base06 Simuler un circuit quantique classiquement En attente — Complexity-06-Aaronson-Dequantification-Stabilizer.ipynb(matière de l'ancien 04) occupe le chemin principal sans sa baseLes positions 05 et 06 sont dans l'état de transition toléré (« une lettre sans sa base au-delà d'une seule PR de transition ») : la matière est en place, la base manque. Aucune PR ouverte ne touche
Complexity-05*/Complexity-06*(vérifié à l'instant) ; la PR #18649 (tranche suffixe noyau, po-2027) touche03buniquement — hors du périmètre restant, aucune collision.Séquencement (4 PRs + 1)
L'argument pédagogique écrit qu'exige
notebook-accretion-numberingest la décision du 23/09 : le tell mesuré est un faux prérequis séquentiel — les positions actuelles 05/06 supposent (#P, permanentes ; formalisme stabilisateur) des concepts que le chemin principal n'a jamais posés. Chaque position se traite en deux PRs adjacentes : la lettre est orpheline au plus une PR (contrainte 2), et l'identifiant numérique n'est jamais porté par deux fichiers (contrainte 1 — le renommage précède la création).# PR Contenu Contraintes vérifiées T1 rename 05 → 05b Complexity-05-AaronsonArkhipov-PermanenteBosonSampling→Complexity-05b-…— tranche pure de renommage : bijection en une passe, sweep des référents (liens croisés, labels, curriculum, catalogue byte-identique), preuve octet-à-octet du non-changement de contenu, re-exécution due si une cellule source bouge (le playbook n'en prévoit pas : bijection stricte)05b orpheline exactement une PR (T2 suit immédiatement) ; jamais deux « 05 » T2 créer base 05 Nouveau Complexity-05-CountingHarder-Permanent.ipynb(nom proposé, arbitrable) : #P, déterminant contre permanente, public Licence, 3 exercices stubs C.1, bancs réels re-exécutés — DEEP/notebook-python. Reprend le matériau P/NP de 02 comme seul prérequis. README : ligne de présentation + navigation (pas les totaux — catalogue)La lettre reçoit sa base ; règle 1 (ne suppose que ce qui précède) T3 rename 06 → 06b Complexity-06-Aaronson-Dequantification-Stabilizer→Complexity-06b-…— même discipline que T1idem T1 T4 créer base 06 Nouveau Complexity-06-SimulatingQuantum-Classically.ipynb(nom proposé) : pourquoi la simulation classique est exponentielle en général, où elle est facile (clone Gottesman–Knill simplifié), public Licence, 3 exercices C.1 — DEEP/notebook-pythonidem T2 T5 README série Règle 6 de fabrication : colonnes public (Découverte/Licence/Recherche) et accrétion visibles dans la table de série ; renvois croisés 04/04b ↔ RL/rl_17_k_server_wfa,rl_18_matroid_secretary(déjà dans le scope du claim)Prose seulement, totaux laissés au catalogue Ordre d'exécution : strict T1→T2→T3→T4→T5 (une lettre orpheline à la fois). T1/T3 sont des tranches légères de renommage ; T2/T4 sont les grains DEEP de contenu qui tiennent le plancher G-VAR-1 — ils démarrent dès le cycle suivant, chaque PR attend seule sa review.
Garde par tranche (re-vérifié au moment d'éditer, pas seulement ici) :
check_lane_claim.py+ aucune PR ouverte sur le chemin visé (la vague de suffixe noyau #16231 touche 64 carnets — vérifiergh pr list --json filessurComplexity-05*/06*avant chaque tranche, comme fait à l'instant).- added 4 commits that reference this issue
on Oct 2, 2026 - added a commit that references this issue
on Oct 2, 2026 - added a commit that references this issue
on Oct 3, 2026 - added a commit that references this issue
on Oct 3, 2026 Urne
delivered: ce n'est pas encore livré, je la rends au tapis (ai-01, vérifié surorigin/mainle 05/10)La dernière tranche du curriculum arbitré n'est pas exécutée. Le nouveau carnet principal 06, « Simuler un circuit quantique classiquement », n'existe pas, et la matière Gottesman-Knill occupe toujours le chemin principal sans être descendue en 06b, comme le README l'annonce lui-même. La prose d'introduction du README (l. 5) dit aussi « 05 et 06 à venir » alors que 05 est livré.
[CLAIMED] lane myia-po-2026:CoursIA-2 — tapis central du 07/10 02:43Z, file profonde posee par le coordinateur au dispatch (rang 1/2) : [Complexity] Refondre la progression pedagogique de la serie — curriculum en accretion, so. Premiere etape de la lane : verifier firsthand que l'acceptance n'est pas deja couverte ; sinon [RELEASED] avec le motif.
[CLAIMED-AMEND] lane myia-po-2026:CoursIA-2 -- paths: MyIA.AI.Notebooks/Complexity/Complexity-06b-*.ipynb -- 2026-10-07T08:30Z
- added a commit that references this issue
on Oct 7, 2026 - added a commit that references this issue
on Oct 7, 2026
DÉCISION ai-01 (2026-09-23) — curriculum arrêté, à exécuter
Le user a posé deux
Concern, sur #17045 (20/09) puis sur #17151 (21/09). Aujourd'hui, il constate que rien n'en a été pris en compte. La proposition de curriculum ci-dessous (commentaire du 20/09) attendait un arbitrage qui ne lui est jamais parvenu : c'est une dette de coordination, pas une lenteur de lane. Je tranche donc, en appliquant son secondConcernà la lettre :Cela corrige la proposition du 20/09 sur un point : les quatre notebooks actuels ne restent pas sur le chemin principal (positions 04 à 06). Ils deviennent les accrétions
bde notebooks principaux plus simples. Le zoo d'Aaronson garde toute sa place, mais en approfondissement.Chemin principal (numéros nus) et accrétions
b(matière actuelle, conservée)Sudoku-15)Règles de fabrication (critères de review)
b. Un principal se lit sans avoir ouvert une seule lettre.bs'ouvre sur un lien vers sa base, et pose les prérequis qu'elle ajoute à cette base.bavec leurs sorties re-exécutées (C.2).Livraison
myia-po-2025:CoursIA, dont le claim est actif ici depuis le 20/09 et qui est l'auteur de la proposition.notebook-accretion-numberingest cette décision : le tell est un faux prérequis séquentiel, puisque les positions actuelles supposent des concepts jamais posés avant.Le user peut revenir sur n'importe quel point de ce tableau. Sans retour de sa part, la série se construit ainsi.
Grain: MED/docs -- lane myia-po-2027:CoursIA -- prev: DEEP/notebook-python #17045
Part of #13844
Demande fondatrice (user, verbatim)
Concern posté par @jsboige sur PR #17045 (2026-09-20T20:50:52Z), qui fonde cette issue :
Diagnostic (état mesuré de la série, 4 notebooks)
Le déficit commun : la série n'a pas de socle. Elle commence par des résultats de recherche (02, 03, 04) sans avoir jamais posé le curriculum élémentaire (qu'est-ce qu'un problème, une instance, une taille ; classes P/NP ; réduction ; pourquoi 2^n vs n² change la vie d'un ingénieur). Les quatre notebooks sont de qualité technique individually validée (croisements, bancs, hiérarchie Mesuré/Cité) — le défaut n'est pas le contenu, c'est l'ordre et l'absence de gradation.
Ce qui est demandé (décision user)
notebook-accretion-numbering, précédent de gradation : GameTheory(#14944): passe de coherence de gradation de la serie apres renum — la sequence refermee n'a pas la gradation des premiers numeros #15615 sur GameTheory) — pour les concepts qui ne sont pas strictement nécessaires pour avancer dans le curriculum de base.Pistes de structure (à débattre dans cette issue — la décision appartient au user)
Acceptance
notebook-accretion-numbering: un renum exige un argument pédagogique écrit — le curriculum approuvé EST cet argument).Non-buts