Chapitre 3
Aspects algorithmiques des treillis
P
Rocédure de calcul bien définie qui prend en
entrée une valeur ou un ensemble de valeurs, et qui donne en sortie une
valeur ou un ensemble de valeurs. Un algorithme est donc une sequence
d'étapes de calcul qui transforment l'entrée en sortie. La notion
d'algorithme est intimement liée à la notion de
complexité. En informatique, le mot compléxité recouvre en
faite deux réalités :
· La compléxité des algorithmes :
C'est l'étude de l'efficacité
comparéé des algorithmes. On mesure ainsi le temps et aussi
l'espace nécessaire à un algorithme pour resoudre un
problème.
· La compléxité des problèmes :
La compléxité des algorithmes a abouti à
une classification des problèmes en fonction des performances
des meilleurs algorithmes connus qui les resolvent. Ils en existent de trois
sortes :
* La classe P se compose des problèmes qui
sont résolubles en temps polynomial. Plus précisement, il existe
des problèmes qui peuvent être résolus en temps O(n')
pour une certaine constante k(n est la taille des
données en entrée).
* La classe NP se compose des problèmes qui
sont vérifiables en temps polynomial. Cela signifie : si l'on nous donne
d'une façon ou d'une autre une solution certifiée, nous pouvons
vérifier que cette solution est correcte en un temps qui est polynomial
par rapport à la taille de l'entrée.
* La classe NPC encore appelée Classe NP-
Complet. Un problème est dans la classe NPC s'il
appartient à NP et s'il est aussi difficile que n'importe quel autre
problème de NP.[8][10]
Les calculs à effectuer pour évaluer les temps
d'exécution d'un algorithme peuvent parfois être longs et
pénibles. Ainsi on aura recours à une approximation de ce temps
de calcul, représentée par la notation
O(·).
Soient f et g deux fonctions positives d'une
même variable entière n. Avec n, la taille des
données à traiter.
la fonction f est dite avoir un ordre de grandeur au
plus égal à celui de la fonction g s'il existe un entier
strictement positif k et un entier N tels que,
- Pour tout n = N, on ait |f(n)| =
k|g(n)| c'est-à-dire que f(·)
est toujours dominée par la fonction g(·),
à une constante multiplicative fixée près;
- On écrira f = O(g) (notation de
Landau).[9]
20
Dans ce chapitre, nous vous présenterons les quelques
aspects algorithmiques qu'ils soient. En effet, il existe deux familles
d'algorithmes de génération ou de contruction des treillis.
* Algorithmes incrémentaux Ce sont des algorithmes qui
contruisent le treillis au fur et à mesure qu'on a connaissances des
objets.
* Algorithmes non incrémentaux ce sont des algorithmes
qui contruisent le treillis une fois que tous les objets sont connus.
3.1 Algorithme de construction du graphe de couverture
d'un treillis
Nourine et Raynaud sont les concepteurs de cet algorithme non
incrémental. Il a été conçu pour la construction et
le calcul du graphe de couverture d'un treillis; il utilise une approche en
deux étapes :[1]
* Génére la famille F
représentée dans un arbre lexicographique.
* Calcule les relation de couverture des
éléments de F
Première étape : L'algorithme calcule l'arbre
lexicographique représenté par la famille F
générée par la base B.
Soit X un ensemble, P un ordre total sur
X et B une base composée par l'ensemble des parties de
X. Désignons par F la famille
générée par l'union des éléments de la
base B, avec;
U
F = {b, b E I/I ? B}
on dit aussi que B est un générateur de
la famille F. Chaque élément de F est
représenté par un couple (f, ã(f)) où;
ã(f) = {b E B/b ?
f}
Il faut voir chaque constituant comme un mot de l'alphabet
X ordonné dans l'ordre croissant.
Montrons maintenant comment construire cet arbre
lexicographique à partir d'une base;
B = {b1,b2,...,bm}
* La racine correspond à F0
qui est un ensemble vide;
* A l'etape j c'est le calcul de la famille
F fermée par l'union. Ce calcul se fait à partir de
F -1 en utilisant la formule suivante :
F = F -1 u {f u b /f
E F -1}; avec B =
{b1,b2,...,b }
Ainsi l'algorithme de construction du graphe de couverture d'un
treillis et le sui-
vant :[5]
Algorithme 1 Graphe de couverture d'un treillis;
Donnée : La base B
Résultat : Arbre lexicographique TF de
F
Début F = {ø}; {La racine de TF};
ã(F) = {ø}
Pour chaque b E B faire
Pour f E F faire
f' = f u b
f» = f ? {b/b ? 0(f», f)} = f'
21
Si f' ?6 F
alors
F = F ? {f'}
ã(f') = ã(f) ? b
ã(F) = ã(F) ? ã(f')
Fin si
Fin pour
Fin pour
Fin
Théorème 3.1 L'algorithme 1
calcule l'arbre lexicographique de la famille F générée
par la base B en O((|X| + |B|) * |B| * |F|) étapes.
Preuve La première instruction dans la
deuxième boucle Pour ainsi que la deuxième
instruction dans Si...alors
sont faites en O(|X|+|B|) étapes; l'instruction
Si...alors
vérifie si f' est dans l'arbre ; sinon
elle l'insère( première instruction du test). Elle
est donc implémentée en O(|F|). Ainsi la
compléxité de la deuxième boucle Pour
vaut O((|X| + |B|) * |F|).
Il s'en suit que la première boucle Pour
se répète |B| fois.D'où le résultat
obtenu.
Deuxième étape Cette étape
consiste à calculer le graphe de couverture G = (F, ?)
à partir de l'arbre lexicographique de la famille F
générée par la base B ; et cela en
utilisant le théorème de couverture suivant :
Théorème 3.2 On définit
;
0(f', f) =
ã(f')\ã(f);
et on note par ? la relation de couverture. Soient f et
f' ? F tels que f ? f' alors :
f ? f' ? ?(b1, b2) ?
0(f', f), b1\f' =
b2\f. Preuve Soient f et f' ? F
tels que f ? f' alors f' peut s'ecrire
:
f' = f ? {b/b ? 0(f',f)}
(1) Supposons que f soit couvert par f',
montrons que pour tous les (b1, b2) ?
0(f', f) ; nous avons :
b1\f' = b2\f.
Supposons que b1\f' ?6
b2\f ; il vient que : f ? b1 = f» ? f'
= f ? {b/b ? 0(f', f)} . Par conséquent
:
f ? f» ? f'.
ce qui est en contradiction avec l'hypothèse selon
laquelle f est couvert par f' ainsi :
b1\f' ? b2\f
De même b1\f' ? b2\f
en utilisant le même raisonnement.
(2) Inversement, supposons que pour tout (b1,
b2) ? 0(f', f) on a : b1\f'
= b2\f. Soit f» ? F tel que f ? f» ? f'
ce qui implique que ;
ã(f) ? ã(f») ? ã(f')
ainsi donc ;
22
ce qui implique que :
ã(f»)\ã(f) ?
ã(f')\ã(f) = Ä(f', f)
Le corollaire suivant est une conséquence du
théorème précédent : Corollaire 3.1
Soient f et f' ? F tels que ;
f ? f';
alors :
f ? f' ? ?f' = f ? b pour
tout Ä(f', f);
Decrivons maintenant comment calculer le graphe de couverture
G = (F, ?). Consi-derons la famille F
généré par la base B utilisée dans
l'algorithme 1. La strategie de cet algorithme consiste à
calculer l'ensemble des éléments de couverture noté par
Imsucc(f) pour chaque élément de la famille F.
En clair f' ? F est candidat si f ? f' et
f' peut être calculé par f' = f ? b
pour certains b ? B\ã(f).
Posons ;
S(f) = {f ? b/b ?
B\ã(f)}
Cet ensemble de candidats S(f) pour la couverture
f, peut avoir des éléments redon-
dants, l'algorithme explore cet ensemble et décide que
f' ? S est une couverture de
f si f' est trouvé |Ä(f',
f)| fois dans S(f). Pour ce faire, nous calculons l'ensemble
S(f) en maintenant le nombre d'occurences de chaque
élément f' dans le compteur
count(f'), ensuite pour chaque élément
f' ? S, on vérifie si |Ä(f', f)| =
count(f')
alors f' couvre f.
L'algorithme suivant construira le graphe de couverture de G
= (F, ?), étant donné
l'arbre lexicographique TF de la famille F
générée par la base B.[5]
Algorithme 2 Graphe de couverture de G = (F,
?)
Donnée Arbre lexicographique de F
et de ã(F)
Résultat Listes d'adjacence des
Imsucc du graphe de couverture du treillis (F,
?).
Début
Initialiser count(f) à 0 pour tout f
? F
Pour f ? F
faire
S(f) = {f ? b/b ?
B\ã(f)}
Pour b ? B\ã(f)
faire
f' = f ? b
count(f') = count(f) + 1
Si |ã(f')| = count(f') +
|ã(f)| faire
Imsucc(f) = Imsucc(f) ? {f'}
Fin si
Fin pour
réinitialiser count(f')
Fin pour
Fin
Théorème 3.3 L'algorithme 2
calcule les listes d'adjancence des Imsucc du graphe
de couverture pour le treillis (F, ?) en
O((|X| + |B|)|B| *
|F|) étapes.
Preuve L'algorithme 2 calcule le graphe
de couverture du treillis (F, ?) par corol-
laire 3.1
Le calcul de |ã(f)| et |ã(f')|
(l'instruction Si...alors) se fait en
O(|X| + |B|) en
utilisant la recherche dans l'arbre lexicographique ; d'où
la compléxité de la boucle
23
interne Pour est de O((|X| + |B|) *
|B|).
Reinitialiser count pour tous les
éléments calculés par la première et la
deuxième instruction de la boucle interne Pour qui se fait en
O(|F|). Il s'en suit que la compléxité de l'algorithme 2
est de O((|X| + |B|)|B| *
|F|).[13]
Exemple 1
Soit X = {1, 2, 3, 4,
5} un ensemble et B une base composée par quelques
parties
de X.
On désigne par F la famille
générée par l'union des éléments de la base
B, tel que
F = {UbEB /I C B}. Par abus
d'écriture, on pose {1, ..., 5} = {12345}. On définit
B={x=245,y=1234,z=15}.
Appliquons l'algorithme 1 afin de générée la
famille F représentée dans un arbre
lexicographique.
On pose ã(f) = {b ? B/b
? f}
1.F = {0} ; (la racine de l'arbre TF ) ;
ã(F) = {0} ;
(a) Pour b = {245} et f = 0 ;
f'=fUb=0U{245}={245} ?6F ;
F = F U {f'} = {0} U {{245}} =
{0,{245}};
ã(f') = ã(f) U
b = {245} = x;
ã(F) = {0, {x}} ;
2.F = {0, {245}}, ã(F)
= {0, {x}};
(a) Pour b = {1234} et f = 0 ; f' =
f U b = {1234} ?6F ; F = {0,
{245}, {1234}} ; ã(f') =
ã(f) U b = {1234} = y ;
ã(F) = {0, {x},
{y}} ;
(b) Pour b = {1234} et f = {245} ;
f' = f U b = {12345} ?6F ;
F = {0, {245}, {1234},
{12345}} ;
ã(f') = ã(f) U
b = {12345} = xyz ;
ã(F) = {0, {x},
{y}, {xyz}} ;
3.F = {0,
{245},{1234},{12345}},ã(F) =
{0, {x}, {y}, {xyz}};
(a) Pour b = {15} et f = 0 ;
f' = f U b = {15} ?6F ;
F = {0, {245}, {1234},
{12345}, {15}} ;
ã(f') = ã(f) U
b = {15} = z ;
ã(F) = {0, {x},
{y}, {xyz}, {z}} ;
(b) Pour b = {15} et f = {245} ;
f' = f U b = {1245} ?6F ;
F = {0, {245}, {1234},
{12345}, {15}, {1245}} ;
ã(f') = ã(f) U
b = {1245} = xz ;
ã(F) = {0, {x},
{y}, {xyz}, {z},
{xz}} ;
(c) Pour b = {15} et f = {1234} ; f'
= f U b = {12345} ? F ;
(d) Pour b = {15} et f = {12345} ;
f' = f U b = {12345} ? F ;
Finalement à partir de la base B = {x =
245, y = 1234, z = 15}, on obtient :
F = {0, {245}, {1234},
{12345}, {15}, {1245}}
24
FIGURE 3.1 - Arbre lexicographique de la famille F
`y(F)
= {0, {x}, {y},
{xyz}, {z},
{xz}};
Ainsi nous obtenons l'arbre lexicographique de F
présenté à la figure 3.1. Appliquons
maintenant l'algorithme 2 qui consiste à calculer le graphe de
couverture à partir de l'arbre lexicographique des familles ;
F = {0, {245},
{1234}, {12345}, {15},
{1245}}
et
`y(F) = {0, {x},
{y}, {xyz}, {z},
{xz}};
générée par la base ;
B={x=245,y=1234,z=15}.
Cet algorithme donne les listes d'adjacence des successeurs
immédiats du graphe de couverture du treillis (F,
Ç). Ainsi on démarre l'algorithme 2 par ;
count(f) = 0 ; pour tout f E F, on
calcule ;
8(f) = {f U b/b E
B\`y(f)};
1. f = 0; 8(f) = 8(0) = {0 U
{245}, 0 U {1234}, 0 U {15}} =
{{245}, {1234}, {15}} ;
calcule de count(f') pour f' E 8(f)
(a) Pour f' = {245},
count(f') = count({245}) = 1;
A(f',f) = `y(f') \ `y(f) = {x} \ 0
= {x};
|A(f',f)| = 1 = |A(f',f)| =
count(f') = 1;
(f, f') = (0, {245}) est une
couverture ;
Imsucc(f) = Imsucc(0) = {{245}} ;
(b) Pour f' = {1234},
count(f') = count({1234}) = 1 ;
A(f', f) = `y(f') \ `y(f) = {y} \ 0
= {y} ;
|A(f', f)| = 1 = |A(f', f)| =
count(f') = 1;
(f, f') = (0, {1234}) est
une couverture ;
Imsucc(f) = Imsucc(0) = {{245},
{1234}} ;
(c) Pour f' = {15},
count(f') = count({15}) = 1; A(f', f) = `y(f')
\ `y(f) = {z} \ 0 = {z} ;
|A(f',f)| = 1 = |A(f',f)| =
count(f') = 1;
25
(f, f') = (0, {15}) est une couverture;
Imsucc(f) = {{245}, {1234}, {15}} ;
count(f') = 0;
2. f = {245}; S(f) = S({245})
= {{245} U {1234}, {245} U {15}} = {{12345},{1245}}; calcule
de count(f') pour f' E S(f)
(a) Pour f' = {12345}, count(f') =
count({12345}) = 1 + 1 = 2;
Ä(f', f) = -y(f') \
-y(f) = {xyz} \ {x} = {yz} ;
|Ä(f', f)| = 2 = |Ä(f', f)| =
count(f') ;
(f, f') = ({245}, {12345}) est une
couverture;
(b) Pour f' = {1245}, count(f') =
count({1245}) = 2 ;
Ä(f', f) = -y(f') \
-y(f) = {xz} \ {x} = {z} ;
|Ä(f', f)| = 1 = |Ä(f', f)| =6
count(f') ;
(f, f') = ({245}, {1245}) n'est pas une
couverture;
Imsucc(f) = Imsucc({245}) = {{1245}} ;
count(f') = 0;
3. f = {1234}; S(f) = {{1234} U
{245}, {1234} U {15}} = {12345} ;
calcule de count(f') pour f' E
S(f)
(a) Pour f' = {12345},
count(f') = count({12345}) = 2 ;
Ä(f', f) = -y(f') \
-y(f) = {xyz} \ {y} = {xz} ;
|Ä(f',f)| = 2 = |Ä(f',f)| =
count(f') = 2;
(f, f') = ({1234}, {12345}) est une
couverture;
Imsucc(f) = Imsucc({1234}) = {{12345}}
;
count(f') = 0;
4. f = {12345}; S(f) =
S({12345}) = 0; count(f') = 0
5. f = {15}; S(f) = S({15}) =
{{15} U {245}, {15} U {1234}} = {{1245}, {12345}} ; calcule
de count(f') pour f' E S(f)
(a) Pour f' = {1245}, count(f') =
count({1245}) = 2 ;
Ä(f', f) = -y(f') \
-y(f) = {xz} \ {z} = {x} ;
|Ä(f', f)| = 1 = |Ä(f', f)| =
count(f') = 1;
(f, f') = ({15}, {1245}) n'est pas une
couverture;
(b) Pour f' = {12345}, count(f') =
count({12345}) = 2 ;
Ä(f', f) = -y(f') \
-y(f) = {xyz} \ {z} = {xy} ;
|Ä(f', f)| = 2 = |Ä(f', f)| =
count(f') ; (f, f') = ({15}, {12345}) est
une couverture; Imsucc(f) = Imsucc({15}) = {{12345}}
;
count(f') = 0;
6. f = {1245}; S(f) =
S({1245}) = {{1245} U {1234}} = {{12345}} ;
calcule de count(f') pour f' E
S(f)
(a) Pour f' = {12345},
count(f') = count({12345}) = 2 + 1 = 3;
Ä(f', f) = -y(f') \
-y(f) = {xyz} \ {xz} = {y} ;
|Ä(f', f)| = 1 = |Ä(f', f)| =
count(f') = 1;
(f, f') = ({1245}, {12345}) n'est pas une
couverture;
On va récupèrer toutes les informations necessaires
pour pouvoir déssiner le graphe
de couverture G = (F,=) du treillis.
Les couvertures (f, f') ou successeurs immédiats
sont les suivants :
1.(0, {245}) est une couverture;
Imsucc(0) = {{245}};
2.(0, {1234}) est une couverture;
Imsucc(0) = {{245}, {1234}};
3.(0, {15}) est une couverture;
Imsucc(0) = {{245}, {1234}, {15}};
26
FIGURE 3.2 - le graphe de couverture G = (F,
Ç)
4. ({245}, {12345}) est une couverture;
Imsucc({245}) = {{12345}};
5. ({1234}, {1245}) est une couverture;
Imsucc({1234}) = {{1245}};
6. ({15}, {1245}) est une couverture;
Imsucc({15}) = {{12345}};
7. ({12345}, {1245}) est une couverture;
Imsucc({1245}) = {{12345}}; On récupère aussi F
et ã(F) tels que :
F = {ø, {245}, {1234},
{12345}, {15}, {1245}}
et
ã(F) = {ø,
{x}, {y}, {xyz},
{z}, {xz}};
Ainsi nous obtenons le graphe de couverture G = (F,
Ç) presenté à la figure 3.2.
| 
