Concentré de savoir : les arbres

Parce qu'il faut bien faire pousser les agrumes

a marqué ce sujet comme résolu.

@Richou D. Degene :

Je comptais parler des arbres rouges et noirs en fonctionnel. Mon problème actuellement, c'est justement les prérequis. Il m'est impossible de parler des arbres rouges et noirs sans parler des arbres binaires.

Du coup, je serai favorable à un tel tutoriel qui m'éviterait une grosse digressions sur les arbres binaires.

@Holosmos : tu as un lien ? Car intuitivement, j'ai du mal à voir comment tu exhibes ta bijection.

+1 -0

@Saroupille : J'ai étudié les arbres binaires l'année dernière, donc avec mes souvenirs et un peu de Wikipédia, je devrais pouvoir écrire quelque chose de bien. :) J'aimerais beaucoup voir ton article, parce que j'essaye désespérément de me mettre au fonctionnel, mais mon cerveau refuse de percuter. :(

@Holosmos: Je rejoins Saroupille, je demande à voir :)

+0 -0

Saroupille> Comme je le disais ici, si c_pages présente l'induction, tu n'as pas beaucoup de travail à fournir : il suffit à mon avis de dire que les arbres qu'il aura définis s'implémentent facilement dans un langage de programmation (surtout avec les types de ML), mais que par défaut ils fournissent une structure de données assez inefficace (insère ici un petit exemple). Ça ne me paraît pas énorme.

+0 -0

En fait tu fais ta bijection à partir de la fonction :

$$ f(x) = \frac{1}{1+ 2\lfloor x \rfloor - x }$$
où $\lfloor x\rfloor$ est la partie entière de $x$.

On peut montrer que la suite $(f^n(0))_{n\in\mathbf{N}}$ avec $f^n$ au sens de la composition est une suite qui atteint chaque rationnel positif une et unique fois.

On a dans les faits la séquence :

$$ 0\mapsto \frac{1}{1}\mapsto \frac{1}{2}\mapsto \frac{2}{1}\mapsto \frac{1}{3}\mapsto\frac{3}{2} \mapsto \frac{2}{3}\mapsto \frac{3}{1} \mapsto \frac{1}{4}\mapsto \frac{4}{3} \mapsto \ldots$$

+0 -0

Mais je t'ai dit que je comptais parler des arbres binaires dans mon article/tuto sur les arbres. :)

c_pages

Il faut voir ce que ça donne. La définition d'un arbre et d'un arbre binaire dont on a parlé en MP @c_pages n'a pas l'air (car tu ne m'as pas donné plus de précision) de correspondre à la définition d'un arbre binaire en fonctionnel :

1
type 'a arbre_binaire = Leaf | Node of arbre_gauche * 'a * Node of arbre_droit

Bref à voir, j'ai du mal à juger les notions qui sont acquises par la majorité des lecteurs.

+0 -0

Comme promis, je vais tenter un article sur les arbres phylogénétiques. Au menu : génétique, évolution et heuristique. Je vais sans doute demander un feed back assez tôt parce que j'ai peur de faire un truc trop technique et assez peu digeste alors qu'en soi c'est un sujet qui peut être passionnant et pas si compliqué.

+2 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte