Arbre de produits

En informatique, et plus particulièrement en calcul formel, un arbre de produits est une structure obtenue en découpant récursivement un produit d'objets tels que des entiers ou des polynômes en sous-produits équilibrés. Le produit complet ${\displaystyle p}$ est placé à la racine de l'arbre ; celle-ci a (généralement) deux fils étiquetés par des sous-produits de taille (degré ou nombre de chiffres, par exemple) comparable ${\displaystyle p_{0}}$ et ${\displaystyle p_{1}}$ tels que ${\displaystyle p=p_{0}p_{1}}$ ; et ainsi de suite jusqu'aux feuilles qui portent les éléments ${\displaystyle a_{0},a_{1},\dots a_{n-1}}$ à multiplier. Ainsi, les nœuds de l'arbre correspondent aux résultats intermédiaires dans le calcul du produit ${\displaystyle p=a_{0}a_{1}\dots a_{n-1}}$ par un algorithme diviser pour régner.

L'intérêt principal des arbres de produits est de tirer parti des algorithmes de multiplication rapide d'entiers ou de polynômes. La situation la plus simple est celle où l'on cherche à calculer le produit d'un grand nombre de « petits » entiers ou polynômes ${\displaystyle a_{0},a_{1},\dots ,a_{n-1}}$. Dans ce contexte, et pourvu que l'on dispose d'une multiplication rapide, l'algorithme diviser pour régner esquissé au paragraphe précédent pour calculer ${\displaystyle p}$ est plus efficace que la méthode consistant à former ${\displaystyle q_{1}=a_{0}a_{1}}$, ${\displaystyle q_{2}=q_{1}a_{2}}$, puis ${\displaystyle q_{3}=q_{2}a_{3}}$, et ainsi de suite. Le résultat du calcul correspond alors simplement à la racine de l'arbre.

Des arbres de produits entiers, résultats intermédiaires compris, interviennent notamment dans les algorithmes classiques d'évaluation multipoint et d'interpolation rapide de polynômes.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.