Dans le cahier préparé pour son livre privé, Sophie donne quatre tableaux de nombres à Luc. Il voudrait les combiner sans changer le résultat, mais choisir une préparation qui demande moins de travail. Sophie lui demande aussi combien de cases nouvelles doivent rester présentes pendant cette préparation. Un produit peut coûter peu de multiplications et conserver plusieurs tableaux à la fois. Les tableaux, valeurs et conventions sont créés pour notre page ; nous ne mesurons aucun programme, appareil, temps de calcul ou mémoire réelle. Les deux comptes devront accompagner une suite effectivement réalisable dans les conventions posées.
La notice 350001 du Met classe l’objet parmi les livres.
La notice 350002 du Met indique également cette catégorie.
La notice 350003 du Met indique aussi un livre.
Ces notices attestent des catégories seulement. Tableaux et règles sont créés ; aucun procédé des ouvrages ne les détermine.
A possède deux lignes et deux colonnes, B aussi ; C possède deux lignes et cinq colonnes, D cinq lignes et trois colonnes. Le produit d’un tableau à r lignes et s colonnes par un tableau à s lignes et t colonnes donne r lignes et t colonnes. Chaque case du résultat est une somme de s produits. Notre compte de travail donne donc r fois s fois t multiplications, même si certaines valeurs sont nulles. Les additions ne sont pas comptées. L’ordre des quatre facteurs reste A, B, C, D ; seules les parenthèses peuvent changer dans la première commande.
Pour le second compte, les tableaux d’entrée restent présents et ne sont jamais écrasés. Ils occupent au total trente-trois cases permanentes. Nous comptons séparément les cases des tableaux nouvellement produits. Un nouveau tableau complet est réservé avant sa multiplication ; les produits intermédiaires qui lui servent d’entrées restent présents jusqu’à sa fin et sont ensuite libérés. Aucun résultat ne peut être transmis case par case à son parent, ni calculé à nouveau après suppression. Les accumulateurs scalaires et les indices ne font pas partie de ce compte conventionnel. Le maximum cherché concerne ces cases de tableaux nouveaux, pas une mesure universelle de mémoire nécessaire.
Le prix d’un produit dépend de ses trois dimensions
Sophie calcule d’abord AB. Deux lignes, deux positions dans la somme et deux colonnes donnent huit multiplications ; le résultat possède quatre cases. CD demande deux fois cinq fois trois, soit trente multiplications, et produit six cases. Multiplier ensuite AB par CD demande deux fois deux fois trois, soit douze. La préparation (AB)(CD) coûte donc cinquante multiplications. Luc avait proposé de compter seulement quatre plus six cases intermédiaires ; ce nombre ne décrit pas les produits scalaires effectués pour les obtenir. Sophie écrit huit, trente et douze près des trois opérations, puis leur somme cinquante sur la fiche de travail.
Une autre préparation commence également par CD, puis le multiplie à gauche par B. Cette deuxième opération demande deux fois deux fois trois, soit douze multiplications, et donne encore un tableau de six cases. A multiplie ce résultat à gauche pour douze autres. A(B(CD)) coûte donc trente plus douze plus douze, cinquante-quatre. Le résultat final possède toujours deux lignes et trois colonnes. Sophie conserve la différence de quatre multiplications : l’égalité des dimensions finales ne rend pas identiques les dimensions utilisées dans toutes les opérations intermédiaires. Elle ne remplace pas le prix du deuxième calcul par cinquante en se fondant sur son même format de sortie.
Nous remplissons les tableaux pour vérifier aussi leurs valeurs. A a les lignes (1,2) puis (0,1), B les lignes (1,0) puis (1,1). C a les lignes (1,0,1,0,1) puis (0,1,0,1,0). D a cinq lignes : (1,0,0), (0,1,0), (0,0,1), (1,1,0), (0,1,1). AB donne (3,2) puis (1,1). CD donne (1,1,2) puis (1,2,0). Leur produit donne (5,7,6) puis (2,3,2). Dans l’autre préparation, B(CD) donne (1,1,2) puis (2,3,2), puis A retrouve les mêmes deux lignes finales. Le compte de multiplications change alors que la remise chiffrée demeure la même.
L’égalité de ces deux résultats s’explique pour des valeurs exactes, pas seulement pour les lignes choisies. Dans une case d’un produit de trois tableaux, on additionne les termes formés par une entrée du premier, une du deuxième et une du troisième, avec les deux indices intérieurs. Parenthéser à gauche ou à droite groupe les mêmes sommes finies de produits. L’addition et la multiplication exactes permettent de les regrouper. Nous conservons cette portée : aucun arrondi intermédiaire n’appartient à notre règle. Sophie n’attribue donc pas à un calcul réel arrondi la garantie de valeurs identiques qui vient de notre arithmétique exacte.
Elle garde également la différence entre parenthéser et changer l’ordre. Si elle remplaçait AB par BA avec nos nombres, BA donnerait (1,2) puis (1,3). Le produit de BA par CD donnerait (3,5,2) puis (4,7,2), et non la page remise. Les dimensions sont encore compatibles et le compte de multiplications de cette branche pourrait ressembler à celui d’AB ; ses valeurs ne répondent plus à la commande A-B-C-D. Sophie retire donc cette permutation avant de comparer les prix des parenthèses autorisées. Elle ne traite pas un tableau différent comme un moyen moins coûteux d’obtenir celui qui était demandé.
Cinq préparations ferment la comparaison du travail
Quatre facteurs dans leur ordre admettent cinq parenthésages complets. A(B(CD)) coûte cinquante-quatre. A((BC)D) commence par BC à vingt, puis son produit par D à trente, puis celui par A à douze : soixante-deux. (AB)(CD) donne le cinquante déjà rempli. (A(BC))D coûte vingt pour BC, vingt pour A(BC), puis trente avec D : soixante-dix. ((AB)C)D coûte huit, vingt, trente : cinquante-huit. Chaque multiplication porte sur deux tableaux dont le nombre de colonnes du premier est celui des lignes du second. Sophie garde la décomposition de chaque prix avec son expression, sans choisir un morceau avantageux dans une autre ligne.
La comparaison des cinq prix donne cinquante comme minimum pour ces facteurs et cette règle dense. Elle ne signifie pas que toute chaîne de quatre facteurs devrait recevoir les mêmes parenthèses. Nos dimensions interviennent dans chacun des prix ; une autre chaîne demanderait une autre comparaison. Sophie retient (AB)(CD) sur sa feuille présente et garde A(B(CD)) comme préparation distincte à cinquante-quatre. Aucune donnée sur les valeurs nulles n’a permis de raccourcir les multiplications dans cette comparaison, puisque la convention les compte toutes. Le minimum porte sur ces cinq expressions autorisées, pas sur toutes les méthodes imaginables pour produire les nombres finaux.
Pour une liste plus longue, on pourrait choisir la coupure du dernier produit, comparer les deux portions contiguës puis ajouter le prix de ce dernier produit. Ici ce prix dépend des dimensions aux deux bouts et à la coupure : il n’est pas le nombre de noms du morceau ni une somme de fréquences de noms. Sophie conserve cet élément dans sa préparation, mais notre comparaison reste remplie par les cinq prix précédents. Nous ne donnons pas un crédit supplémentaire à la seule forme d’une recherche par morceaux, déjà utile dans d’autres pages du cahier. La décision présente devra maintenant répondre aussi à la présence des tableaux, que ces prix seuls n’ont pas comptée.
Un petit résultat ne peut pas effacer ses deux entrées trop tôt
Dans (AB)(CD), Sophie peut produire AB d’abord. Ses quatre cases restent présentes pendant la production des six cases de CD. Avant le dernier produit, elle conserve donc dix cases nouvelles. Elle réserve ensuite les six cases du résultat final, alors que les quatre d’AB et les six de CD servent encore à calculer ses valeurs. Seize cases nouvelles sont présentes à cet instant. Quand le dernier produit est achevé, AB et CD sont libérés et seules ses six cases demeurent. Sophie inscrit seize comme maximum, pas six sous prétexte que le destinataire ne recevra finalement qu’un tableau de six cases.
Produire CD avant AB ne réduit pas ce maximum. Six cases restent présentes pendant la production des quatre d’AB ; le dernier produit exige de nouveau quatre plus six plus six. Les deux ordres font atteindre seize, même si les premières présences sont différentes. Luc avait proposé de libérer CD avant de réserver le résultat pour rester à dix. Sophie refuse ce geste : CD est encore une entrée du dernier produit et aucun recalcul n’est permis. La limite ne vient pas d’un nom de tableau déclaré « temporaire », mais du moment où ses valeurs ont cessé d’être nécessaires sous la règle que la feuille a acceptée.
Dans A(B(CD)), CD occupe d’abord six cases nouvelles. Le résultat de B(CD) possède six autres cases, réservées pendant que CD est encore présent : le maximum atteint douze. CD est libéré après cette multiplication. Pour le produit suivant par A, les six cases de B(CD) restent présentes avec les six cases de sortie, puis sont libérées. Le maximum reste douze. A et B sont des entrées permanentes déjà comptées séparément ; Sophie ne leur ajoute pas un second emplacement de produit intermédiaire dans cette trace. Cette préparation plus longue de quatre multiplications que la première demande donc moins de cases nouvelles simultanées.
Les autres parenthèses complètent cette comparaison. BC possède dix cases. Dans A((BC)D), ces dix restent présentes avec les six de (BC)D : seize, puis le dernier produit avec A en demande douze. Dans (A(BC))D, le résultat A(BC) possède aussi dix cases, produites avant la libération des dix de BC : vingt ; le produit final en demande ensuite seize. Dans ((AB)C)D, les quatre d’AB restent avec les dix d’(AB)C : quatorze ; les dix restent ensuite avec les six de sortie : seize. Les maxima des cinq préparations sont donc douze, seize, seize, vingt et seize, dans l’ordre où leurs prix ont été présentés.
Sophie peut désormais remplir deux demandes différentes. Le moins de multiplications choisit (AB)(CD) avec cinquante et un maximum de seize cases nouvelles. Le moins de cases nouvelles simultanées choisit A(B(CD)) avec douze et cinquante-quatre multiplications. Les deux préparations donnent les mêmes valeurs exactes, mais elles ne possèdent pas ensemble leurs deux avantages. Sophie retire la fiche « cinquante multiplications, douze cases » qui mélangeait les deux colonnes. Elle joint chaque compte à ses produits et à ses libérations. Une expression chiffrée juste ne suffisait pas à décrire les présences pendant l’autre expression.
Deux plafonds ensemble peuvent refuser les deux meilleures colonnes
Luc autorise au maximum treize cases nouvelles simultanées et cinquante et une multiplications. Le minimum de cases douze passe son premier contrôle, et le minimum de travail cinquante passe son second. Cela ne donne pourtant aucune préparation qui passe les deux ensemble. Parmi les cinq expressions, seule A(B(CD)) reste sous treize cases ; elle coûte cinquante-quatre, au-dessus de cinquante et une. (AB)(CD) reste sous le plafond de travail mais demande seize cases. Les trois autres expressions dépassent également treize cases et n’ajoutent aucune solution. Sophie refuse la commande combinée, au lieu d’accepter les minima séparés comme deux certificats du même déroulement.
Elle conserve les deux permissions qui répareraient réellement la commande. Si Luc garde treize cases et autorise cinquante-quatre multiplications, A(B(CD)) devient recevable et sa trace de libérations tient le plafond. S’il garde cinquante et une multiplications et autorise seize cases, (AB)(CD) devient recevable. La fiche retenue doit préciser lequel de ces plafonds a changé. Sophie ne garde pas treize et cinquante et une écrits auprès d’une trace qui atteint seize ou cinquante-quatre. Le résultat exact peut être remis sous plusieurs permissions, mais aucune ne corrige rétrospectivement la commande d’origine restée sans préparation autorisée.
Les cinq expressions montrent aussi que le compromis n’est pas une moyenne entre leurs comptes. Celle à cinquante-quatre et douze pourrait être exécutée, comme celle à cinquante et seize. Une paire de nombres entre les deux ne correspond pas automatiquement à une sixième expression. Sophie ne crée ni demi-tableau partagé entre les plans ni demi-multiplication pour interpoler. Les opérations et les réservations sont celles d’une expression complète. Elle garde les préparations à soixante-deux et soixante-dix dans le contrôle, mais ne leur prête pas un avantage de réserve qu’elles n’ont pas. Leur présence dans une liste ne rend pas continus les choix que cette liste permet.
Une expression fixée peut encore laisser deux ordres de production
Une préparation distincte ajoute un tableau E à trois lignes et deux colonnes après D. Les entrées permanentes possèdent désormais trente-neuf cases, comptées séparément comme auparavant. Sophie ne cherche pas d’abord le minimum parmi toutes les nouvelles parenthèses. Luc lui remet une expression fixée, (AB)(C(DE)), et veut savoir comment la produire avec au maximum quatorze cases nouvelles simultanées. Le résultat final a deux lignes et deux colonnes. Les parenthèses indiquent les produits nécessaires ; elles n’obligent pas à fabriquer la portion AB avant la portion C(DE), tant que les deux sont prêtes pour leur dernier produit.
DE possède cinq lignes et deux colonnes. Sa production demande cinq fois trois fois deux, trente multiplications, et réserve dix cases nouvelles. C(DE) demande ensuite deux fois cinq fois deux, vingt multiplications, et produit quatre cases. Pendant cette opération, les dix cases de DE restent présentes avec les quatre nouvelles : quatorze. DE est ensuite libéré. AB demande huit multiplications et produit quatre cases, puis le dernier produit de deux tableaux deux-par-deux demande huit multiplications et quatre cases de sortie. Le travail total de cette expression fixée vaut trente plus vingt plus huit plus huit, soixante-six ; l’ordre de production de ses deux grandes portions n’en modifie pas les dimensions.
Sophie commence néanmoins par AB dans son premier essai. Elle conserve ses quatre cases pendant que la portion droite est produite. DE ajoute dix cases : quatorze présentes. C(DE) ajoute ses quatre cases avant de libérer DE : dix-huit. Après cette libération, AB et C(DE) totalisent huit cases ; les quatre de sortie font atteindre douze pendant le dernier produit. Le maximum de l’essai vaut dix-huit, donc la demande de quatorze est refusée. Sophie ne remplace pas dix-huit par le maximum quatorze calculé pour la portion droite seule : celle-ci n’était pas seule dans cet essai, puisque AB attendait encore son partenaire.
Dans l’autre essai, elle produit d’abord C(DE). Cette portion atteint quatorze cases nouvelles, puis n’en conserve que quatre. AB est ensuite produit pendant que ces quatre attendent : huit cases. Le dernier produit en fait coexister quatre de gauche, quatre de droite et quatre de sortie : douze. Le maximum de l’ensemble reste donc quatorze, et l’essai satisfait la demande. Les deux traces ont les mêmes produits et leurs mêmes soixante-six multiplications. Sophie a changé le moment où quatre cases doivent être gardées pendant une autre production, sans changer l’expression ni les valeurs qu’elle remet.
Cette exécution de droite avant gauche ne transforme pas le dernier produit en C(DE) fois AB. L’ordre des facteurs reste AB puis C(DE), même lorsque le second est calculé avant le premier. Pour notre E rempli avec les lignes (1,0), (0,1), (1,1), les deux traces donnent (11,13) puis (4,5) à la fin. Sophie conserve les noms des deux entrées du dernier produit, avec leur place à gauche et à droite. Une préférence de calendrier pour produire la droite d’abord n’est pas une permission de permuter les facteurs. Les opérations peuvent ainsi partager une expression et un résultat tout en ayant des présences provisoires différentes.
Le sommet d’une trace compte aussi ce qui attend ailleurs
Pour contrôler ces deux traces, Sophie garde trois nombres auprès de chaque portion : son coût de multiplications, le nombre de cases de son résultat nouveau, et son maximum interne. Si elle produit la gauche d’abord, le maximum doit couvrir le maximum gauche seul, puis le résultat gauche gardé pendant le maximum droit, puis les deux résultats avec le nouveau résultat du parent. Pour la droite d’abord, elle inverse les deux premières phases de ce contrôle, pas les facteurs du produit. Elle compare les deux maxima permis par ces ordres et retient celui de la trace qu’elle exécute.
L’expression fixée remplit cette règle avec quatre cases de sortie à gauche et quatre à droite. La gauche seule atteint quatre ; la droite seule atteint quatorze. Produire la gauche d’abord oblige à couvrir quatre plus quatorze, dix-huit. Produire la droite d’abord couvre quatorze, puis quatre plus quatre, huit ; les deux ordres doivent encore couvrir quatre plus quatre plus quatre, douze, au dernier produit. Le calcul du maximum retrouve dix-huit et quatorze sans ajouter les maxima des deux portions comme s’ils avaient lieu ensemble. Sophie garde les phases effectivement concurrentes : un résultat en attente et une production, puis les deux entrées et leur sortie.
Elle ne transforme pas quatorze en minimum parmi toutes les parenthèses des cinq facteurs. Sa commande avait fixé (AB)(C(DE)). Le contrôle des quatorze expressions possibles montre d’autres comptes ; par exemple A(B((CD)E)) peut donner cinquante-huit multiplications et un maximum de dix cases nouvelles sous nos règles. Cette possibilité appartient à une commande où les parenthèses seraient encore libres. Sophie la conserve comme autre préparation, mais elle remet l’exécution droite-d’abord de l’expression imposée lorsqu’on lui demande de garder celle-ci. Un meilleur compte obtenu en changeant l’expression n’est pas une réparation autorisée de son ordre de production seul.
Luc voudrait ensuite permettre d’écrire directement certaines cases d’un produit dans celui qui le consomme, afin de ne plus réserver tous les tableaux complets. Sophie n’ajoute aucun compte favorable pour cette proposition : elle retire d’abord la restriction qui rendait nos traces obligatoires et ouvre un autre modèle à définir. Il faudrait préciser quelles cases restent nécessaires, dans quel ordre elles sont produites et si les recalculs sont permis. Le treize refusé ou le quatorze accepté de nos feuilles ne certifient pas cette nouvelle permission. Ils restent les comptes de tableaux complets retenus jusqu’à leur consommation, avec leurs entrées permanentes séparées.
Pour la remise choisie, Sophie conserve le résultat exact et joint sa préparation. Avec quatre facteurs et les plafonds réparés, elle remet (AB)(CD) à cinquante multiplications et seize cases nouvelles. Dans la branche où l’expression à cinq facteurs était imposée, elle remet la droite avant la gauche, à soixante-six et quatorze. Les entrées, les réservations et les libérations demeurent visibles dans chaque trace. Le cahier ne prétend pas mesurer une machine : il montre pourquoi une même page finale ne choisissait pas à elle seule le travail accompli ni les tableaux qui devaient rester présents pendant sa préparation.
Deux remises peuvent employer un produit commun
Une commande distincte demande de remettre ensemble ABCD et ABCF. F possède cinq lignes et trois colonnes comme D, mais sa première ligne est (0,1,0) au lieu de (1,0,0) ; les autres sont conservées. Le second résultat donne (2,10,6) puis (1,4,2), différent du premier. Sophie reçoit une permission nouvelle : garder un produit complet identique pour qu’il serve aux deux sorties, au lieu de le libérer après sa première consommation. Aucun morceau de produit ni raccourci fondé sur une relation numérique n’est ajouté. Les produits des facteurs contigus A-B-C peuvent ainsi être partagés, tandis que ceux contenant D ou F concernent des entrées différentes.
Calculer séparément chacune des deux sorties au minimum de cinquante coûterait cent multiplications. Si Sophie conserve seulement AB, elle le produit une fois pour huit ; chaque sortie exige ensuite trente pour CD ou CF et douze pour son dernier produit. Le total partagé vaut quatre-vingt-douze. Garder BC demanderait vingt, puis au mieux quarante-deux par sortie, soit cent quatre. Garder ABC coûte au moins vingt-huit, obtenu par AB à huit puis son produit par C à vingt ; chaque produit final par D ou F coûte trente. Le total devient quatre-vingt-huit. Ces cas ferment la comparaison : les seuls produits nouveaux communs aux deux chaînes sont AB, BC et ABC ; les autres comportent D ou F, et ne sont pas la même entrée. Conserver ABC choisit donc la préparation qui coûtait cinquante-huit pour une sortie seule, mais sa portion produite une fois sert réellement aux deux remises.
Sophie remet cette dernière trace plutôt que deux exemplaires du plan individuel à cinquante. Elle produit AB, puis ABC ; AB est libéré, mais les dix cases d’ABC restent gardées par la permission nouvelle. Elle produit les six cases d’ABCD, qu’elle doit conserver pour la remise commune. Produire ensuite les six cases d’ABCF fait coexister dix plus six plus six cases nouvelles : vingt-deux. ABC peut alors être libéré et les deux sorties restent présentes. Le gain de douze multiplications par rapport aux deux plans individuels n’a donc pas reçu le maximum de seize cases de l’une de ces anciennes traces. Sophie joint quatre-vingt-huit et vingt-deux à la préparation commune exécutée. Elle conserve cinquante et seize auprès de la commande à une sortie, sans qualifier son ancien minimum de faux ni attribuer gratuitement le même partage à une règle qui exigeait auparavant la libération après consommation.
Les notices de livres ne fournissent aucun tableau, compte ou méthode de calcul du cas. Leur catégorie reste leur seule contribution.
Les Éditions privées donnent une forme aux voix, aux archives et aux histoires que vous souhaitez transmettre.
Découvrir Codex de Maison →