4.1.3.3 La suppression d'un service
Un pair hébergeant un service a la possibilité
de le supprimer, pour cela une requête xml de suppression doit être
envoyée à l'arbre local du pair concerné. Ensuite la
requête est routée sur d'autres machines si le service y est
répliqué. Une recherche de ce service doit être
effectuée au préalable afin de le localiser. La suppression d'un
service fils unique entraine la suppression de son service pair.
Notre algorithme de suppression est le suivant il prend en
paramètre, le système d'exploitation, la licence, le langage, le
nom du service, l'adresse IP. Une fois le service trouvé, la fonction
detruire(nc) est appelée où nc est le noeud
courant.
Marie Hélène Wassa Mballo Page
81
[Tapez le titre du document]
ALGORITHME DE SUPPRESSION
METHODE supprimer
ENTREE syst :chaine, lic
:chaine, lang :chaine, A :arbre, nomser :chaine, @IP :nombre
nfilsg : Noeud //noeud fils
gauche
nfrdrt : Noeud //noeud frère
droit
nc(-A.racine //nc noeud courant
nc(-nfilsg
Tant que nc?null et nc.valeur?syst
et nc.valeur<syst nc(-nfrdrt
fin tant que
si nc=null ou
nc.valeur>syst
exit
fin si
si nc.valeur=syst
nc(-nfilsg
tant que nc?null et nc.valeur?lic
et nc.valeur<lic
nc(-nfrdrt
Fin tant que
Si nc=null ou
nc.valeur>lic
Exit
Fin si
Si nc.valeur=lic
Marie Hélène Wassa Mballo Page
82
[Tapez le titre du document]
nc(-nfilsg
Tant que nc?null et nc?lang et
nc.valeur<lang nc(-nfrdrt
Fin tant que
Marie Hélène Wassa Mballo Page
83
Si nc=null ou
nc.valeur>lang
Exit
Fin si
Si nc.valeur=lang
nc(-nfilsg
Tant que nc?null et
nc.valeur.nomserv?nomserv et
nc.valeur.adIP ?nc.valeur.adIP et
nc.valeur.nomserv<nomserv
nc(-nfrdrt
fin tant que
si nc.valeur.nomserv=nomserv et
nc.valeur.adIP =nc.valeur.adIP
detruire(nc)
fin si
Fin si
Fin si
Fin si
Fin supprimer
Etude de la complexité de l'algorithme de
suppression
Nous rappelons que la complexité de l'opération
detruire(n) a une complexité de 1
Le calcul de la complexité à partir de
l'algorithme de suppression donne les éléments suivants :
· L'instruction 1 s'effectue en O(nsyst),
puisque nous cherchons l'existence du système d'exploitation dans
l'arbre, ce qui signifie que les noeuds du niveau 1 sont parcourus nsyst fois
dans le pire des cas.
·
Marie Hélène Wassa Mballo Page 84
L'instruction du bloc 4-6 est une constante qui s'effectue en
O(1) puisque un test Si est effectué. La complexité de ce bloc
est inférieure à celle du bloc 7-35 donc nous ne comptabiliserons
que cette dernière
· L'instruction du bloc 7-35 regroupe plusieurs
instructions. Ainsi nous allons voir la complexité de chacune d'elles
o L'instruction 9 s'effectue en O(2), le nombre
d'itérations est de nlic.
o L'instruction 12 se fait en O(1), car un test Si est
effectué pour voir si le programme s'arrête à ce niveau ou
bien s'il continue.
o L'instruction du bloc 15-34 est composée de
plusieurs instructions dont nous allons étudier la complexité
· L'instruction 17 s'effectue en O(nlang), car
cette complexité dépend du nombre de noeuds du niveau 3.
· L'instruction du bloc 20 se fait en O(1), un test Si
est effectué. La complexité de cette instruction est
inférieure au bloc 23-33, donc la complexité du bloc 20 n'est pas
comptabilisée.
· L'instruction 25 se fait en O(nserv), le
nombre d'itérations dans le pire des cas est de nserv
fois.
· L'instruction 30 se fait en O(2), car un test Si est
d'abord effectué pour ensuite faire un appel de la fonction
detruire(nc)
· La complexité totale du bloc 23-33 est
égale à la somme des complexités de ses différentes
instructions O(2)+O(nserv)= O(nserv)
o La complexité du bloc 15-34 est égale à
la somme des différentes instructions qui la composent : O(nlang)+
O(nserv)
· Le bloc 7-35 a pour compléxité donc :
O(2)+O(1)+O(nlang)+ O(nserv)= O(nlang)+ O(nserv)
· Ainsi notre algorithme de suppression a une
complexité qui est égale à la somme des complexités
des différentes instructions, soient :
O(nsyst) +O(nlang) + O(nserv)
Marie Hélène Wassa Mballo Page 85
Les trois algorithmes présentent une complexité
linéaire, car cette dernière croit en fonction des modifications
de services dans l'arbre, cette modification est liée à l'ajout
et la suppression de services. L'arbre de services comme dit dans la
partie 4.1.2, a une hauteur fixe, donc elle ne grandit qu'en
largeur. Cette croissance en largeur se fait surtout sentir au niveau des
feuilles, car pour les systèmes d'exploitation, les plus utilisés
sont Unix, Windows xp ce qui entraine donc que le nombre
noeuds que nous pouvons avoir au niveau 1 est très réduit.
| 
