Correspondance de Łukasiewicz⚓︎

Généralités

On rappelle qu'un arbre est dit :

enraciné : s'il possède au moins un nœud ; la racine
sans étiquette : les nœuds ne portent pas ici d'identifiant ni de valeurs
ordonné : l'ordre de ses sous-arbres compte

Dans ce cas, un arbre peut être modélisé avec une liste Python :

Une feuille (un nœud externe) sera représentée par une liste vide [] ; la liste de ses sous-arbres est vide.
Un nœud interne sera représenté par la liste de ses sous-arbres donnés dans l'ordre.
Un arbre sera donné par la représentation de sa racine.

Dans cet exercice, on ne travaille qu'avec des arbres enracinés, ordonnés, sans étiquette. On pourrait cependant aussi accepter les étiquettes.

Exemples

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_arbres de 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 a est une feuille, on remplace donc ...a... par 0, il y a \(0\) nœud et on n'a pas de sous arbres à évoquer.
Le sous-arbre b possède \(5\) nœuds, on remplace donc ...b... par 5, 0, ..., 0, 0, 0 ; il y avait 4 feuilles, on a déjà placé les 0, reste à compléter par le dernier morceau qui possède 2 feuilles, donc 2, 0, 0
Le sous-arbre c est une feuille, on remplace ...c... par 0

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 chemin est 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

Réciproquement, pour tout chemin de Łukasiewicz, on pourrait reconstruire un arbre avec le procédé inverse ; c'est plus délicat à implémenter. Ce sera l'objet d'un autre exercice, plus difficile.

Écrire une fonction arbre_vers_chemin qui implémente une partie de la correspondance de Łukasiewicz.

Exemples

représenté en interne avec [[], []], donne un chemin

qui correspond à la liste [1, -1]

🐍 Console Python

>>> arbre_vers_chemin([[], []])
[1, -1]

représenté en interne avec [[], [], [[], []]], donne un chemin

qui correspond à la liste [2, -1, -1, 1, -1]

🐍 Console Python

>>> arbre_vers_chemin([[], [], [[], []]])
[2, -1, -1, 1, -1]

###

# testsbksl-nlbksl-nlassert arbrepy-undverspy-undchemin([[], []]) == [1, -1]bksl-nlbksl-nlassert arbrepy-undverspy-undchemin([[], [], [[], []]]) == [2, -1, -1, 1, -1]bksl-nlbksl-nl# autres testsbksl-nlbksl-nlassert arbrepy-undverspy-undchemin([]) == []bksl-nlassert arbrepy-undverspy-undchemin([[]]) == [0]bksl-nlassert arbrepy-undverspy-undchemin([[[[[]]]]]) == [0, 0, 0, 0]bksl-nlassert arbrepy-undverspy-undchemin([[], [], []]) == [2, -1, -1]bksl-nlassert arbrepy-undverspy-undchemin([[], [], [], [], []]) == [4, -1, -1, -1, -1]bksl-nlassert arbrepy-undverspy-undchemin([[[]], [[], [], [], [[]], []], []]) == [bksl-nl 2,bksl-nl 0,bksl-nl -1,bksl-nl 4,bksl-nl -1,bksl-nl -1,bksl-nl -1,bksl-nl 0,bksl-nl -1,bksl-nl -1,bksl-nl]bksl-nlbksl-nl ∞/∞

def arbrepy-undverspy-undchemin(arbre):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert arbrepy-undverspy-undchemin([[], []]) == [1, -1]bksl-nlassert arbrepy-undverspy-undchemin([[], [], [[], []]]) == [2, -1, -1, 1, -1]bksl-nlbksl-nldef arbrepy-undverspy-undchemin(arbre):bksl-nl def etape(arbre):bksl-nl "Fonction récursive interne"bksl-nl resultat = [len(arbre)]bksl-nl for souspy-undarbre in arbre:bksl-nl resultat.extend(etape(souspy-undarbre))bksl-nl return resultatbksl-nlbksl-nl chemin = [y - 1 for y in etape(arbre)]bksl-nl chemin.pop()bksl-nl return cheminbksl-nlbksl-nl

A

Culture⚓︎

Łukasiewicz a [...] jeté les bases de l'informatique moderne en créant la notation polonaise et en développent avec Alfred Tarski et Stefan Banach les fondations de la notation inverse, une manière d'écrire des expressions arithmétiques largement utilisées à ce jour en informatique.

Z