3.4 Modélisations par des structures arborescentes
95
Remarque 3.15 Les variantes de tri radix ne sont adaptées qu’à certains types de
données (voir par exemple la discussion dans [231]). De plus, nous l’avons déjà
mentionné pour le tri rapide, dans une implantation d’une méthode de tri (quelle
qu’elle soit), dès que la taille du tableau à trier devient petite, nous avons recours à
une technique de tri plus adaptée (qui est souvent le tri par insertion en pratique).
3.4 Modélisations par des structures arborescentes
Les structures arborescentes, notamment digitales, interviennent fréquemment dans
la modélisation puis l’analyse de divers algorithmes ; nous en donnons quelques
exemples ci-dessous.
3.4.1 Arbres d’expressions booléennes
La logique quantitative étudie et compare divers formalismes de la logique propositionnelle, sous l’angle des lois de probabilité qu’ils induisent sur l’ensemble
des fonctions booléennes, puis des liens avec la complexité de ces fonctions, i.e.,
avec la taille mémoire minimale nécessaire pour les représenter, enfin de leur
capacité à représenter un ensemble de formules logiques (pouvoir d’expression).
Cette approche, initiée par Paris et al. [203], a été reprise et développée d’abord par
Lefmann et Savický [164], puis par plusieurs auteurs dont Woods [38, 115, 228,
229, 252]. La représentation des expressions sous forme arborescente et l’approche
de la combinatoire analytique pour dénombrer diverses classes d’arbres y jouent un
rôle fondamental.
Considérons par exemple la logique propositionnelle construite sur k variables
booléennes et leurs négations, et sur les deux connecteurs ∧ et ∨ que nous
prenons ici binaires et non commutatifs (il est possible de s’affranchir de cette
restriction). Les expressions ainsi construites sont identifiées aux arbres binaires
non commutatifs, que nous avons appelés « arbres de Catalan » en section 1.1.2,
dont les nœuds internes sont étiquetés par les connecteurs ∧ et ∨, et les feuilles
par les 2k littéraux. Ces arbres sont ce que nous appelons des arbres ET-OU. Une
expression booléenne de cette logique est par exemple (x ∨ y) ∧ (z ∨ (x ∨ t)) ;
l’arbre binaire la représentant est donné en figure 3.22.
Fig. 3.22 Arbre ET-OU pour
l’expression booléenne
(x ∨ y) ∧ (z ∨ (x ∨ t)) dans la
logique à deux connecteurs
binaires non commutatifs ∧
(ET) et ∨ (OU)
95
Remarque 3.15 Les variantes de tri radix ne sont adaptées qu’à certains types de
données (voir par exemple la discussion dans [231]). De plus, nous l’avons déjà
mentionné pour le tri rapide, dans une implantation d’une méthode de tri (quelle
qu’elle soit), dès que la taille du tableau à trier devient petite, nous avons recours à
une technique de tri plus adaptée (qui est souvent le tri par insertion en pratique).
3.4 Modélisations par des structures arborescentes
Les structures arborescentes, notamment digitales, interviennent fréquemment dans
la modélisation puis l’analyse de divers algorithmes ; nous en donnons quelques
exemples ci-dessous.
3.4.1 Arbres d’expressions booléennes
La logique quantitative étudie et compare divers formalismes de la logique propositionnelle, sous l’angle des lois de probabilité qu’ils induisent sur l’ensemble
des fonctions booléennes, puis des liens avec la complexité de ces fonctions, i.e.,
avec la taille mémoire minimale nécessaire pour les représenter, enfin de leur
capacité à représenter un ensemble de formules logiques (pouvoir d’expression).
Cette approche, initiée par Paris et al. [203], a été reprise et développée d’abord par
Lefmann et Savický [164], puis par plusieurs auteurs dont Woods [38, 115, 228,
229, 252]. La représentation des expressions sous forme arborescente et l’approche
de la combinatoire analytique pour dénombrer diverses classes d’arbres y jouent un
rôle fondamental.
Considérons par exemple la logique propositionnelle construite sur k variables
booléennes et leurs négations, et sur les deux connecteurs ∧ et ∨ que nous
prenons ici binaires et non commutatifs (il est possible de s’affranchir de cette
restriction). Les expressions ainsi construites sont identifiées aux arbres binaires
non commutatifs, que nous avons appelés « arbres de Catalan » en section 1.1.2,
dont les nœuds internes sont étiquetés par les connecteurs ∧ et ∨, et les feuilles
par les 2k littéraux. Ces arbres sont ce que nous appelons des arbres ET-OU. Une
expression booléenne de cette logique est par exemple (x ∨ y) ∧ (z ∨ (x ∨ t)) ;
l’arbre binaire la représentant est donné en figure 3.22.
Fig. 3.22 Arbre ET-OU pour
l’expression booléenne
(x ∨ y) ∧ (z ∨ (x ∨ t)) dans la
logique à deux connecteurs
binaires non commutatifs ∧
(ET) et ∨ (OU)