Algorithmique et Programmation TD n Arbres suite Divers

Description

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

Sujets

• Arbre binaire de recherche
• Implication
• Variable
• Clause

Informations

• Publié par: pefav
• Nombre de lectures: 95
• Langue: Français

Extrait

Algorithmique et Programmation
TD n 5 : Arbres (suite) + Divers
Ecole normale superieure
Departement d’informatique
[e-mail]
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 stoc