Arbres de calcul

On veut évaluer l'expression (5+1)². Pour cela on peut la considérer, soit comme (5+1)×(5+1), soit comme la forme développée 52+2×5+1.

I/ Forme factorisée

Comme un carré est un produit, l'arbre syntaxique a pour racine le symbole * qui désigne la multiplication :

Comme on le voit ci-dessus, les expressions déjà évaluées (les nombres) sont en forme de rectangle, les cercles étant réservés aux opérations.

1) Première simplification

La première somme porte sur deux opérandes (5 et 1) et on peut la remplacer par la somme des deux opérandes, ce qui modifie la forme du sommet (c'est un nombre, pas une opération, donc on le met en rectangle) :

2) Seconde simplification

On fait pareil pour la seconde somme :

3) fin du calcul

On n'a plus qu'un produit à calculer (celui de 6 et 6) donc on effectue ce produit pour finir d'évaluer l'expression :

II/ Forme développée

L'arbre de l'expression développée 52+2×5+1 est a priori un arbre ternaire puisque la somme comporte trois termes. Mais on peut le ramener à un arbre binaire avec (5*5) + (2*5+1) :

1) Première simplification

Le produit partiel le plus bas dans l'arbre est 2×5, on peut donc déjà effectuer ce calcul :

2) Seconde simplification

Ensuite on peut effectuer l'autre produit :

3) Troisième simplification

Puis une des additions :

4) Fin du calcul

Finalement en exécutant l'addition 25+11 on obtient

soit le même résultat qu'avec l'autre méthode. Ceci veut dire que 52+2×5+1 = (5+1)2.

III/ Comparaison entre les méthodes

Le premier arbre de calcul nécessitait une multiplication et deux additions, le second nécessitait deux multiplications et deux additions. Comme il faut en général nettement plus de temps pour effectuer une multiplication qu'une addition, on peut se demander quel est l'intérêt de la seconde méthode.

1) Avec une racine carrée

Si au lieu de 5 on a √5 la première méthode ne peut donner qu'une valeur approchée et non exacte : le calcul de √5+1 ne donne rien d'autre qu'une valeur approchée, et ensuite on élève au carré une valeur approchée ce qui ne peut donner qu'une valeur approchée.

La seconde méthode par contre donne pour le premier produit, √5×√5 = 5 qui est exact. Le calcul se termine alors par 5+2×√5+1 = 6+2√5. Les calculatrices récentes des marques Ti, Casio, hp et Numworks font cela. On appelle cela le calcul exact. Citons cet article d'Émilie Feral :

Or, écrire l'arbre sous forme développée, permet d'obtenir la valeur exacte s'il y a des racines carrées.

Il semble donc que la calculatrice Numworks transforme les expressions en les développant pour ensuite faciliter le calcul s'il y a besoin de la valeur exacte. Mais pas toujours :

2) Avec l'infini

a) +∞

Si, au lieu de 5, on a ∞,

• La première méthode évalue l'expression à (∞+1)2=∞2=∞,
• et la seconde méthode évalue l'expression à ∞2+2×∞+1=∞+∞+1=∞+1=∞.

b) -∞

Si, au lieu de 5 on a -∞, par contre,

• La première méthode évalue l'expression à (-∞+1)2=(-∞)2=∞,
• mais la seconde méthode donne (-∞)2+2×(-∞)+1=∞-2×∞+1=∞-∞+1 qui est indéterminé.

La forme développée n'est donc pas toujours la meilleure.

3) Avec une variable indéterminée

Autrefois, avec la Numworks, lorsque la variable x n'était pas affectée, le calcul de (x+1)2 donnait x2+2×x+1. Ceci a été rétabli sur le firmware tiers omega puis sur son descendant khi.

IV/ Effet de la curryfication sur les arbres

La curryfication consiste à ne pas regarder l'opération comme portant sur deux opérandes mais comme une fonction. Par exemple sur l'arbre de la multiplication 6×6 :

On regarde la partie coloriée comme un tout (une fonction à appliquer au reste de l'arbre) :

La partie coloriée (multiplier par 6 le reste de l'arbre) correspond au mot sextuple et donc la curryfication donne « le sextuple de 6 ». On peut donc dire que la curryfication aplanit les arbres de calcul, en les rendant linéaires.

Cela se voit mieux avec un parcours suffixe de l'arbre, où on peut effectuer des regroupements que la curryfication rend visibles.

Les exemples suivants sont écrits dans le langage de programmation Postscript qui est basé sur la notation polonaise inverse (lecture suffixe des expressions)

1) Définition du carré

Pour simplifier les notations par la suite, on définit une fonction carré qui élève un nombre au carré. Pour cela, on duplique (dup) le nombre puis on effectue une multiplication (mul) ce qui a bien pour effet de multiplier le nombre par lui-même, c'est-à-dire de l'élever au carré :

2) Version factorisée

Alors (5+1)×(5+1) = (5+1)2 s'écrit ainsi en Postscript 

La curryfication isole une partie :

Il est d'ailleurs possible de nommer la partie surlignée :

Alors l'expression devient plus simple :

Le carré du successeur de 5 : la structure linéaire (et non arborescente) est devenue flagrante.

3) Version développée

Pour la version développée 52+2×5+1, c'est plus compliqué, ne serait-ce que parce que le nombre 5 intervient plusieurs fois (élevé au carré, puis plus tard multiplié par 2). on doit donc le dupliquer (dup), puis après avoir élevé au carré une des deux copies, échanger (exch) celles-ci pour opérer sur celui des deux 5 qui n'a pas été élevé au carré, et ensuite multiplier (mul) cette copie par 2, puis additionner (add) 1, et enfin additionner le tout :

Mail là aussi, la curryfication aide à isoler des fonctions (d'arité 1) :

En fait il n'y avait pas besoin d'aplanir l'arbre par une lecture suffixe, pour isoler ces fonctions :

Et là encore, les nommer permet de mieux décrire l'expression développée :

L'expression devient alors

Le carré de 5, additionné avec le successeur de son double.