Algorithmique et Programmation TD n Arbres suite Divers

Publié par

Algorithmique et Programmation TD n? 5 : Arbres (suite) + Divers Ecole normale superieure Departement d'informatique 2011-2012 1 Petits Rappels Le but de cet exercice est d'etudier un type d'arbre binaire de recherche qui a de bonnes proprietes amorties en autorisant des modifications de l'arbre aussi pendant la recherche d'un element. Graphes Un graphe (non-oriente) G = (V,E) est la donnee d'un ensemble de sommets V (pour “verti- ces”, pluriel irregulier de “vertex”), et d'un ensemble d'aretes E ? V 2 reliant certains sommets. En gros, x? y dans G ssi (x, y) ? E. Logique Une variable booleenne prend comme valeur “vrai” (>) ou “faux” (?). L'ensemble des formules booleennes contient les variables, ?, >, et il est ferme pour la negation (?), le ET (? ? ?) ainsi que le OU (? ? ?). Une formule est satisfiable s'il existe une assignation des variables qui la rend vraie. Sinon, elle est insatisfiable. Un litteral est soit une variable, soit la negation d'une variable. Une formule booleenne est en forme normale conjonctive Si elle peut s'ecrire ? = ? i ? j ij ou ij est un litteral.

  • arbre binaire de recherche

  • algorithme en temps lineaire

  • implication

  • variable

  • formules d'entree

  • methode du potentiel

  • interpretation courante

  • clause

  • x0 x1


Publié le : mardi 19 juin 2012
Lecture(s) : 92
Source : di.ens.fr
Nombre de pages : 7
Voir plus Voir moins

Algorithmique et Programmation
TD n 5 : Arbres (suite) + Divers
Ecole normale superieure
Departement d’informatique
td-algo@di.ens.fr
2011-2012
1 Petits Rappels
Le but de cet exercice est d’etudier un type d’arbre binaire de recherche qui a de bonnes proprietes
amorties en autorisant des modi cations de l’arbre aussi pendant la recherche d’un element.
Graphes Un graphe (non-oriente) G = (V;E) est la donnee d’un ensemble de sommets V (pour \verti-
2ces", pluriel irregulier de \vertex"), et d’un ensemble d’ar^etes EV reliant certains sommets. En
gros, x$y dans G ssi (x;y)2E.
Logique Une variable booleenne prend comme valeur \vrai" (>) ou \faux" (?). L’ensemble des formules
booleennes contient les variables,?,>, et il est ferme pour la negation ( ), le ET (^ ) ainsi
que le OU (_ ). Une formule est satis able s’il existe une assignation des variables qui la rend
vraie. Sinon, elle est insatis able . Un litteral est soit une variable, soit la negation d’une variable.
Une formule booleenne est en forme normale conjonctive Si elle peut s’ecrire
^_
= ‘ij
i j
ou ‘ est un litteral.ij
Exercice 1 (??) : Horn-SAT. Une clause de Horn est une formule logique en forme normale conjonctive
ou chaque clause contient au maximum un seul litteral positif. En d’autres termes une clause de Horn
est ou bien une implication :
X ^X ^^X )X ;1 2 k k+1
ou les X sont des variables propositionnelles, ou bien une clause purement negative :i
X _X __X1 2 k
Notez qu’une implication aveck = 0 revient a a rmer que la variable propositionnelle a droite du signe )
est vraie de fa con inconditionnelle (c’est un fait).
1. Donnez un algorithme pour la satis abilite (de la conjonction) d’un ensemble de clauses de Horn
(on ne demande pas une preuve formelle de correction).
2. Expliquez comment l’implementer en temps lineaire en la taille de son entree.
Exercice 2 (???) : Splay Trees. Les arbres binaires de recherche supportent typiquement les operations
suivantes :
1. Find(T;x) renvoie vrai ou faux selon que la cle x est presente dans T .
2. Insert(T;x;y) ajoute la cle x a T (en supposant qu’elle n’y est pas dea)j
3. Delete(T;x) retire la cle x de T
4. Split(T;x) renvoie les deux arbres qui contiennent les cles plus petites et plus grandes que x,
respectivement.
5. Join(T ;T ) combine les deux arbresT etT , et renvoie l’arbre resultant. Cette operation suppose1 2 1 2
que les clefs presentes dans T sont toutes plus petites que celles presentes dans T .1 2
1Les Splay Trees ont ete inventes en 1985 par Sleator et Tarjan. Un splay tree est un arbre binaire de
recherche qui supporte une nouvelle operation, splay (litteralement, \evaser"). Dans un arbre binaire de
recherche, une operation Splay(T;x) deplace un noeud arbitraire x dans l’arbre jusqua’ la racine par
une sequence de doubles rotations (qui se termine eventuellement par une simple rotation a la n si la
profondeur de x etait impaire). Les operations qui peuvent avoir lieu sont illustrees ici :
y x
rotation simple yx C A
A B B C
z x
y zig-zag y zD
xA A B C D
B C
z x
y yD ARoller-Coaster
x zC B
A B C D
L’idee est qu’un arbre binaire de recherche qui subit frequemment l’operation Splay reste a peu pres
equilibre, alors qu’aucune donnee supplementaire n’est stockee, contrairement aux arbres AVL, rouges-
noirs, etc. En plus, les noeuds auxquels on accede frequemment sont pres de la racine. En particulier,
apres chaque operation Find(T;x), Insert(T;x), Delete(T;x), . . ., on remonte x vers la racine par
un splay. L’arbre peut donc ^etre modie par Find, ce qui est inhabituel. On impose que si Find(T;x)
renvoie \false", alors l’operation splay est appliquee au dernier noeud visite.
1. Quel est l’e et d’appliquer l’operation splay aux noeuds du bas d’un peigne de hauteur n ?
2. En supposant que l’operation splay est deja programmee, decrivez les manieres les plus simples
possible d’implementer les autres operations.
Pour estimer la complexite des operations sur les splay trees, on observe que la descente dans l’arbre est
toujours moins cou^teuse que l’operation splay, et donc il est su sant d’avoir une bonne borne sur le cout^
de cette operation. On va faire une analyse amortie en utilisant la methode du potentiel.
On rappelle que dans une analyse amortie avec la methode du potentiel, on de nit une fonction
potentiel pour la structure de donnee qui initialement vaut = 0 et reste toujours positive. Le cou^t0
amorti d’une operation est son cout^ reel plus la dierence de potentiel : a =c + . Il est facilei i i i 1
de voir que le cout^ total de toute suite de m operations est inferieur a son cou^t total amorti :
m m m mX X X X
a = (c + ) = + c ci i i i 1 m i i
i=1 i=1 i=1 i=1
Tout le probleme est de de nir une bonne fonction de potentiel. On de nit le rang d’un noeud v
par Rang(v) = log Taille(v), ou Taille(v) designe le nombre de sommets du sous-arbre enracine2
en v (y compris v). De la sorte, le rang est toujours positif. On de nit aussi le potentiel de l’arbre parP 0
= Rang(v), et par de nition, le potentiel est toujours positif. On notera Rang(v) et Rang (v)v
les rang avant et apres une rotation (simple ou double), respectivement.
3. Donnez l’ordre de grandeur asymptotique du potentiel pour un arbre parfaitement equilibre (resp.
desequilibre)
4. Montrer que le cout^ amorti d’une simple rotation qui vise a faire monter un noeud x est au plus :
01 +Rang (x) Rang(x)
25. Montrer que le cou^t amorti d’un Zig-Zag qui fait monter le noeud x (comme sur le dessin) est au
0plus 2Rang (x) 2Rang(x).
6. Montrer que le cou^t amorti d’un Roller-Coaster qui fait monter le noeud x (comme sur le dessin)
0
est au plus 3Rang (x) 3Rang(x).
7. En deduire le cout^ amorti d’une operation splay.
Exercice 3 (???) : Sommets jumeaux dans un graphe.
Dans un graphe non-oriente G = (V;E), dont les sommets sont les elements de V , et dont les ar^etes
sont les pairesfu;vg2E, on note ( x) l’ensemble des sommets adjacents au sommet x :
n o
( x) = y2V jfx;yg2E
Dans un graphe, deux sommetsu etv sont de vrais jumeaux (resp. faux jumeaux) si ( x) = ( y) (resp.
( x)[fxg = ( y)[fyg). Donnez un algorithme de complexiteO (jVj +jEj) qui determine la liste des
paires de sommets jumeaux.
32 Solutions
Solution de l’exercice 1
On denote par X les variables propositionnelles (on va dire qu’il y en a n) et par C les clauses dei i
Horn (il y en a m).
L’idee generale est de garder les variables a \faux" tant qu’on est pas force de les faire passer a \vrai"
(dans un sens, on est \glouton", ou plus exactement, \radin").
On part donc d’une interpretation qui met toutes les variables a faux. Tant qu’il existe une implication
insatisfaite, on force la variable de droite a \vrai". Une fois que la procedure est stabilisee, on verie si
les clauses purement negatives sont toutes satisfaites. Si oui, on a trouve une interpretation des variables
qui satisfait les formules. Si non, on repond \insatis able".
Il reste a demontrer que cet algorithme est correct et qu’il peut ^etre implemente en temps lineaire.
Correction. L’argument de correction est relativement intuitif, mais pas completement evident a
rendre formel... Quand l’algorithme renvoie une interpretation, il n’est pas di cile de se convaincre
qu’elle satisfait veritablement l’ensemble des clauses. Ce qui est plus complique, c’est de se convaincre
que l’algorithme a raison lorsqu’il renvoie \insatis able". Pour cela, on considere une fonction f qui
prend un ensemble de variables propositionnelles et renvoie un sur-ensemble de son argument, qu’on
construit a partir des clauses. Si les premisses d’une implication appartiennent a X, alors la conclusion
de l’implication appartient a f(X).
Nous a rmons que les interpretations satisfaisant l’ensemble des clauses sont necessairement des
points xes def. Je ne fais pas la preuve complete, mais en gros si une interpretation n’est pas un point
xe, alors elle viole une des implications.
De la m^eme maniere, nous a rmons que f est croissante :
XY =)f(X)f(Y ):
Je ne le demontre pas, mais ca n’est pas di cile.
Lemme 1. l’algorithme calcule le plus petit point xe de f (au sens de l’inclusion des ensembles).
Demonstration. Si on pose u =X et u =f(u ), alors l’algorithme calcule la limite de la suite (u ),0 i+1 i n
qui est croissante et bornee donc convergente. Il est evident que la limite est un point xe, et on va la
1noter f (X).
Considerons maintenant un point xe arbitraire V . On a alors u V , et comme f est croissante0
et V est un point xe, une recurrence triviale donne que pour tout i 0, u V . On en deduit quei
1f (X)V .
L’interpretation renvoyee par l’algorithme est donc la \plus petite", en le sens que n’importe quelle
interpretation qui satisferait l’ensemble des clauses contiendrait celle renvoyee par l’algorithme. On en
conclut que si l’interpretation minimale viole les clauses purement negative, alors aucune autre interpre-
tation satisfaisant toutes les implications peut satisfaire aussi les clauses purement negatives. CQFD.
Complexite. Il faut un peu d’astuce pour implementer l’algorithme en temps lineaire en la taille
des formules d’entree. On stocke les implications dans une liste doublement cha^nee, et on stocke a part
les clauses purement negatives dans une liste cha^nee. Pour chaque implication, on stocke a part la
conclusion et les premisses. Les premisses sont representees sous la forme d’une liste doublement cha^nee.
On initialise en plus un tableau qui associe a chaque variable la liste des pointeurs vers ses occurrences
dans les premisses des implications (cf. gure). L’interpretation courante est, elle, un tableau contenant
un booleen par variable. Les clauses purement negatives sont representees par une liste doublement
cha^nee des variables.
41: function HornSat(clauses)
2: Construire les structures de donnees.
3: Cur l’interpretation courante (initialement, la liste vide)
4: P une pile vide
5: for each variable x forcee par un fait do Push(P;x)
6: while P =; do
7: x Pop(P )
8: if x2= Cur then
9: Cur Cur[fxg
10: for all implication X ^^X )X telle que X =x do1 k k+1 i
11: retirer x des premisses
12: if les premisses sont vides then Push(P;X )k+1
13: end for
14: for all clause purement negative X __X telle que X =x do1 k i
15: retirer x de la clause
16: if la clause est vide then return \insatis able"
17: end for
18: end if
19: end while
20: return Cur
21: end function
:::X X X X X0 k+1 0 1 2 k
1
:::X X X X X2 k+1 0 1 2 k
3
4
5
:::X X X X X6 k+1 0 1 2 k
7
:::X X X X X8 k+1 0 1 2 k
L’operation d’enumerer les clauses contenant une variable donnee se fait en tempsO (1) par clause
enumeree, grac^ e au tableau de pointeurs. Retirer une variable des premisses se fait en tempsO (1) (listes
doublement cha^nees). Tester si les premisses sont vide se fait en tempsO (1). De plus, le nombre total de
suppression d’une variable, le nombre de test du vide des premisses, est borne par la taille d’entree des
clauses (puisque chaque variable ne peut ^etre retiree qu’une seule fois). Le nombre de \push" est borne
par le nombre de clauses. La m^eme variable peut a priori ^etre empilee plusieurs fois (par exemple s’il y
a deux implications identiques), mais elle ne sera traitee qu’une seule fois. Tester l’appartenance a Cur
se fait en tempsO (1), puisque c’est un tableau.
Misc. L’algorithme lineaire a ete decrit pour la premiere fois par Downling et Gallier en 1984. Le
probleme Horn-Sat est P-complet : si on savait le resoudre en temps logarithmique, on saurait transformer
tous les algorithmes polynomiaux en algorithmes logarithmiques.
Solution de l’exercice 2
1. Il su t de faire un dessin. Mais a peu de chose pres ca divise la hauteur de l’arbre par deux.
5
62. { Find(T;x) ne pose pas trop de probleme. Il su t d’appliquer splay au noeud x s’il est trouve,
ou bien au dernier noeud visite pendant la descente.
{ Pour e ectuer Split(T;x), on commence par e ectuer Find(T;x). Apres, ou bien x est a la
racine et c’est tres facile, ou bien le plus petit noeud plus grand que x (resp. le plus grand plus
petit que x) se retrouve a la racine, et c’est encore assez facile.
{ PourJoin(T ;T ), on descend dansT en allant systematiquement a droite, donc on tombe sur1 2 1
le plus grand element. On le splay, ce qui l’amene a la racine, sans ls droit. On peut alors
brancher T dessus.2
{ l’insertion et la suppression sont faciles a faire avec Split(T;x) et Join(T ;T )1 2
3. Prenons un arbre binaire complet de hauteur n. Un noeud de hauteur i est la racine d’un sous-
i+1 n iarbre qui compte 2 1 noeuds. Un sommet de hauteur i est donc de rang i, et il y a 2
sommets de hauteur i (les feuilles sont de hauteur 0). Le potentiel est donc :
n +1X X
n i n i n+1 = i 2 2 i 2 = 2 :
i=0 i=0
Il appara^t donc que dans un arbre equilibre, le potentiel est sensiblement du m^eme ordre de
grandeur que le nombre de noeuds.
Prenons ensuite un peigne de hauteur n. Sur la \colonne vertebrale", le noeud de hauteur i est la
racine d’un sous-arbre de 1 + 2i noeuds. Tous les autres noeuds sont des feuilles, de rang zero. Le
potentiel est donc
nX
= log (1 + 2i)2
i=0
et on peut demontrer (ce n’est pas di cile) que cette somme est de l’ordre de n logn.
4. Le cout^ reel d’une rotation est 1. Reste a contr^oler la variation du potentiel. On peut se reporter
a la gure pour les notations. Les rangs des sommets contenus dans les sous-arbres A, B et C ne
changent pas. Par contre, les rangs de x et y vont changer a priori, et on a :
0 0 0
=Rang (x) +Rang (y) Rang(x) Rang(y)
En fait, dans la rotation, le rang de y ne peut que diminuer, puisqu’il se retrouve avec moins
d’enfants qu’avant. Il s’ensuit que le cout^ amorti est :
0 01 + 1 +Rang (x) Rang(x)
5. Dans les deux types de doubles rotation, le cou^t reel est 2. Pour obtenir le resultat, il faut absorber
cette constante dans la variation du potentiel. En e et, il serait assez facile de montrer (par des
0arguments de monotonie) que le cou^t amorti d’une double rotation est inferieur a 2+3Rang (x)
3Rang(x). Seulement, a cause du \2", cette borne est trop grande pour ^etre utilisable (cf.
question suivante pour une explication plus detaillee). On va donc chercher a se debarrasser de
cette constante. L’expression du cout^ amorti est :
0 0 0 02 + = 2 +Rang (x) +Rang (y) +Rang (z) Rang(x) Rang(y) Rang(z)
0Il est clair queRang (x) =Rang(z) (vu que ce sont les racines d’arbres qui contiennent le m^eme
nombre de sommets). Par consequent :
0 002 + = 2 +Rang (y) +Rang (z) Rang(x) Rang(y)
Ensuite, si on regarde bien les con

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.