Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

1
Parcimonie de Fitch-Hartigan pour un arbre donné
La parcimonie totale est la somme des parcimonies de chaque
site ; on raisonne indépendamment sur chacun.
A chaque noeud
x
est attaché l’ensemble des valeurs possibles
C
x
a
f
réalisant la parcimonie optimale
P
x
a
f
Soit
g
x
a
f
et
d
x
a
f
les fils droit et gauche de
x
,
o
n
a
l
a
récurrence :
Si
g
x
a
f
et
d
x
a
f
,
s
i
C
g
x
C
d
x
a
f
b
g
a
f
b
g
alors
C
x
C
g
x
C
d
x
(
)
=
a
f
b
g
a
f
b
g
P
x
P
g
x
P
d
x
(
)
=
+
a
f
b
g
a
f
b
g
sinon
C
x
C
g
x
C
d
x
(
)
=
a
f
b
g
a
f
b
g
P
x
P
g
x
P
d
x
(
)
=
+
+
1
a
f
b
g
a
f
b
g
Sinon
P
x
a
f
=
0 et
C
x
x
a
f
k
p
=
valeur de
Le résultat est indépendant de la position de la racine. Le calcul
est en
O
n
s
Σ
b
g
(
n
= nombre de séquences ;
s
= nombre de sites).
Et on peut réaliser les unions et intersections au niveau bit.
Ce parcours est postorder. Un parcours preorder permet
d’assigner aux noeuds une valeur réalisant l’optimum.