Correspondance de Łukasiewicz
😀 On considère ici des arbres non étiquetés et ordonnés.
Dessin et représentation d'arbres ordonnés et non étiquetés
représenté en interne avec [[[], []], [[]], []]
représenté en interne avec [[[]], [[], []], []]
Les deux arbres ci-dessus sont différents, d'où la qualification ordonné.
représenté en interne avec [[], [[], [[], []], [], [], []], []]
Correspondance de Łukasiewicz
Pour chaque arbre, on note \(n\) le nombre de nœuds. On rappelle qu'ici « arbre » désigne arbre enraciné, ainsi \(n>0\).
1] On construit d'abord une liste nb_sous_arbres :
- qui commence avec le nombre de sous-arbres de la racine,
- que l'on complète récursivement avec le contenu des listes
nb_sous_arbresde chaque sous arbre. - Pour un feuille, cette liste est
[0]; il y a \(0\) sous-arbre, et donc rien à ajouter.
Exemple :
, la racine possède \(3\) sous arbres, ainsi la liste sera de la forme [3, ...a..., ...b..., ...c...]
-
Le sous-arbre
aest une feuille, on remplace donc...a...par0, il y a \(0\) nœud et on n'a pas de sous arbres à évoquer. -
Le sous-arbre
bpossède \(5\) nœuds, on remplace donc...b...par5, 0, ..., 0, 0, 0; il y avait 4 feuilles, on a déjà placé les0, reste à compléter par le dernier morceau qui possède 2 feuilles, donc2, 0, 0 -
Le sous-arbre
cest une feuille, on remplace...c...par0
On obtient la liste [3, 0, 5, 0, 2, 0, 0, 0, 0, 0, 0]
Propriétés :
- Cette liste est de longueur \(n\) et de somme égale à \(n-1\).
- Cette liste se termine toujours par un \(0\), qui représente la feuille la plus à droite de l'arbre.
- La somme des \(i\) premiers termes est toujours supérieure ou égale à \(i\) pour tout \(i\) de \(0\) à \(n\).
2] On construit une liste chemin à partir de cette liste, en ôtant \(1\) à chaque nombre de la liste, et enlevant le dernier nombre de cette liste.
Propriétés :
- Cette liste
cheminest de longueur \(n-1\) et de somme nulle. - La somme des \(i\) premiers termes est toujours positive pour tout \(i\) de \(0\) à \(n-1\).
Exemple, à partir de la liste [3, 0, 5, 0, 2, 0, 0, 0, 0, 0, 0], on construit
[2, -1, 4, -1, 1, -1, -1, -1, -1, -1, -1]
On obtient donc une modélisation d'un chemin de \((0, 0)\) à \((n-1, 0)\) situé dans le quadrant en haut à droite (abscisses et ordonnées positives), dont les étapes sont de la forme \((1, k)\) avec \(k=-1\) ou \(k\in \mathbb N\). On appelle un tel chemin un « chemin de Łukasiewicz ».
Avec l'exemple précédent, on obtient
🥚 easter egg
Si vous résolvez cet exercice, vous aurez accès à un exercice caché : reconstruire un arbre avec le procédé inverse ; c'est bien plus délicat à implémenter.
Exercice
Coder une fonction arbre_vers_chemin qui implémente une partie de la correspondance de Łukasiewicz.
représenté en interne avec [[], []], donne un chemin
qui correspond à la liste [1, -1]
>>> arbre_vers_chemin([[], []])
[1, -1]
représenté en interne avec [[], [], [[], []]], donne un chemin
qui correspond à la liste [2, -1, -1, 1, -1]
>>> arbre_vers_chemin([[], [], [[], []]])
[2, -1, -1, 1, -1]
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)