Concernant la gestion des services, nous définissons
trois algorithmes qui sont : l'insertion, la recherche et la suppression.
Ensuite nous étudions la complexité des différents
algorithmes en considérant les paramètres suivants :
A : correspond au nombre de noeuds logiques du
niveau 1 qui peut varier de 1 à nsyst
B : correspond au nombre de fils maximum que
peut avoir un noeud du niveau 1, et ce paramètre varie de 1 à
nlic . Comme nous l'avons écrit dans la
partie 4.1.2, la licence ne peut être que deux types soit libre ou
propriétaire, donc nlic=2.
C : représente le nombre de fils
maximum que peut avoir un noeud du niveau 2. Ce nombre varie de 1 à
nlang.
D : représente le nombre de fils que
peut avoir un noeud du niveau 3. Cette variable est comprise entre 1 et
nserv.
Dans notre mémoire nous allons calculer la
complexité dans le pire des cas, c'est-à-dire nous allons
considérer que les valeurs maximales des paramètres cités
ci-dessus. Nous déterminons la complexité temporelle dans ce
mémoire, puisque ce qui est le plus important dans un algorithme c'est
d'exécuter des calculs dans des délais raisonnables.
Un service hébergé par un serveur doit se
trouver dans l'arbre de services, dont l'évolution dépend des
arrivées et des départs des services.
Un noeud pair, voulant hébergeant un service, lance
une requête xml d'insertion au niveau de son arbre. Cette requête
prend comme paramètre le système d'exploitation,
la licence, le langage, le nom du
service, l'emplacement physique et la
description.
Lors de ce processus d'insertion, une recherche est
effectuée d'abord pour savoir si le noeud logique à
insérer ne se trouve pas déjà dans l'arbre.
Dans notre algorithme, l'opération de création
de noeuds est faite lorsque le noeud logique ne se trouve pas dans l'arbre.
Cette opération utilise deux fonctions : CreerNoeud(v),
ou v représente la valeur à insérer dans le
noeud logique et CreerNoeudfils(v) qui permet la
création des fils du nouveau noeud logique.
METHODE inserer
ENTREE A :arbre, syst :chaine,
lic :chaine ,lang :chaine, nomserv :chaine, @IP :nombre, description
:chaine
nfilsg :Noeud //noeud fils gauche du noeud courant
nfrdt :Noeud //noeud frère droit du noeud courant
nc :Noeud //nc est le noeud courant
nc(-A.racine
nc(-nfilsg
[Marie Hélène Wassa Mballo] Page
72
Tant que nc?null et nc.valeur?syst
et nc.valeur<syst //parcours du niveau 1
nc(-nfrdrt //nc.valeur=valeur contenue dans le noeud
courant
Fin tant que
Si nc=null ou
nc.valeur>syst
CreerNoeud(syst) //création d'un noeud
contenant la valeur du système
CreerNoeudfils(lic)//création du noeud fils
contenant la licence
CreerNoeudfils(lang)//création du noeuf fils
contenant le langage
CreerNoeudfils(nomserv,@IP,description)
Fin si
Si nc.valeur=syst
nc(-nfilsg
Tant que nc?null et nc.valeur?lic
et nc.valeur<lic /parcours du niveau 2
nc(-nfrdrt
Fin tant que
Si nc=null ou
nc.valeur>lic
CreerNoeud(lic)
CreerNoeudfils(lang)
CreerNoeudfils(nomserv,@IP,description)
Fin si
Si nc.valeur=lic
nc(-nfilsg
Tant que nc?null et nc.valeur?lang
et nc.valeur<lang /parcours du niveau 3
nc(-nfrdrt
Fin tant que
Si nc=null ou
nc.valeur>lang
CreerNoeud(lang)
CreerNoeudfils(nomserv,@IP,description)
Fin si
Si nc.valeur=lang
CreerNoeudfils(nomserv,@IP,description)
Fin si
Fin si
Fin si
Fin inserer
Etude de la complexité de l'algorithme
d'insertion
[Marie Hélène Wassa Mballo] Page
73
[Marie Hélène Wassa Mballo] Page 74
Nous rappelons que les opérations de création de
noeud dans l'arbre ont une complexité égale à 1. Pour
déterminer la complexité, nous avons les éléments
suivants :
· L'instruction 1 de l'algorithme d'insertion s'effectue
en O(nsyst), puisque nous cherchons l'existence du système
d'exploitation dans l'arbre avant de créer un nouveau noeud logique.
· L'instruction du bloc 4-9 de cet algorithme est une
constante qui s'effectue en O(5), puisque nous faisons un test sur la valeur du
noeud courant et ensuite un appel de quatre fois à l'opération de
création d'un noeud logique. La complexité de ce bloc est
inférieure à celle du bloc 10-34, donc nous ne comptabiliserons
que cette dernière.
· L'instruction du bloc 10-34 regroupe plusieurs
instructions, nous allons voir la complexité de chacune d'elles
o L'instruction 12 s'effectue en O(2) puisque une comparaison
est faite entre les noeuds logiques du niveau 2 et la licence passée en
paramètre
o L'instruction du bloc 15-19 se fait en O(4) puisque nous
faisons appel trois fois à l'opération de création de
noeuds. Cette instruction est inférieure au bloc d'instruction 20-32
donc nous considérons cette dernière.
o Le bloc 20-32 est composé de plusieurs
instructions
· L'instruction 22 s'effectue en O(nlang)
puisque nous parcourons les noeuds du niveau 3 pour voir si le type de langage
à insérer n'existe pas déjà dans l'arbre de
services.
· L'instruction du bloc 25-28 se fait en O(3) car nous
ajoutons deux noeuds logiques et avant cet ajout un test Si
est effectué.
· L'instruction du bloc 29-31 se fait en O(2) car un test
Si est effectué suivi de la création d'un noeud logique.
o La complexité totale du bloc 20-32 est égale
à la somme des complexités des différentes instructions
qui la composent, ce qui donne donc : O(nlang)+O(3)+O(2)=
O(nlang)
· La complexité du bloc 10-34 est égale
à O(2)+O(nlang)= O(nlang)
· En résumé, en parcourant toutes les
étapes de l'algorithme d'insertion nous voyons qu'il a une
complexité dans l'ordre de :
O(nlang)+ O(nsyst)
