Chapitre 1
Botanique
Il y a plusieurs manières de voir les arbres ; la distinction la plus fondamentale
est peut-être celle qui consiste à les considérer soit comme des structures discrètes
toujours finies – c’est le point de vue de l’algorithmique, qui ne peut (sauf artifice)
représenter que des objets finis –, soit comme des objets potentiellement infinis –
c’est le point de vue des mathématiques. Dans ce chapitre, et dans la suite de ce
livre, nous rencontrerons les deux points de vue simultanément. En anticipant sur la
suite du chapitre, nous pouvons dire que
– l’aspect « structure toujours finie » correspond à la définition d’un arbre par une
classe combinatoire ; on peut alors définir une notion de « taille » d’un arbre ;
– l’aspect « structure potentiellement infinie » correspond à la définition d’un arbre
par un ensemble de mots ; nous parlerons de taille finie ou infinie d’un arbre.
Une autre distinction vient de la différence entre arbre non marqué et arbre
marqué.
– Dans le premier cas les nœuds de l’arbre ne contiennent pas d’information. C’est
la forme de l’arbre à laquelle on s’intéresse.
– Le second cas correspond à un point de vue plus algorithmique ; il consiste à
voir un arbre comme une structure dont les nœuds contiennent des informations,
souvent appelées « données ». En informatique, ce qui est contenu dans un nœud
est nommé variable et on lui affecte une valeur dans un ensemble appelé aussi
domaine. Pour éviter les confusions sur les mots « variable » et « valeur », nous
appellerons dans la suite « marques » (« labels » en anglais), ou « clés », ce qui
est à l’intérieur d’un nœud. C’est l’objet {arbre + marques} auquel on s’intéresse.
Mathématiquement, cet objet est appelé un arbre marqué (parfois arbre étiqueté).
L’arbre non marqué obtenu en effaçant les marques d’un arbre marqué est sa
forme.
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_1
3
Botanique
Il y a plusieurs manières de voir les arbres ; la distinction la plus fondamentale
est peut-être celle qui consiste à les considérer soit comme des structures discrètes
toujours finies – c’est le point de vue de l’algorithmique, qui ne peut (sauf artifice)
représenter que des objets finis –, soit comme des objets potentiellement infinis –
c’est le point de vue des mathématiques. Dans ce chapitre, et dans la suite de ce
livre, nous rencontrerons les deux points de vue simultanément. En anticipant sur la
suite du chapitre, nous pouvons dire que
– l’aspect « structure toujours finie » correspond à la définition d’un arbre par une
classe combinatoire ; on peut alors définir une notion de « taille » d’un arbre ;
– l’aspect « structure potentiellement infinie » correspond à la définition d’un arbre
par un ensemble de mots ; nous parlerons de taille finie ou infinie d’un arbre.
Une autre distinction vient de la différence entre arbre non marqué et arbre
marqué.
– Dans le premier cas les nœuds de l’arbre ne contiennent pas d’information. C’est
la forme de l’arbre à laquelle on s’intéresse.
– Le second cas correspond à un point de vue plus algorithmique ; il consiste à
voir un arbre comme une structure dont les nœuds contiennent des informations,
souvent appelées « données ». En informatique, ce qui est contenu dans un nœud
est nommé variable et on lui affecte une valeur dans un ensemble appelé aussi
domaine. Pour éviter les confusions sur les mots « variable » et « valeur », nous
appellerons dans la suite « marques » (« labels » en anglais), ou « clés », ce qui
est à l’intérieur d’un nœud. C’est l’objet {arbre + marques} auquel on s’intéresse.
Mathématiquement, cet objet est appelé un arbre marqué (parfois arbre étiqueté).
L’arbre non marqué obtenu en effaçant les marques d’un arbre marqué est sa
forme.
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_1
3