La recherche de services dans notre arbre se fait de
façon dichotomique de la gauche vers la droite puisque les noeuds de
chaque niveau sont classés suivant un ordre lexicographique. Cette
recherche se fait en largeur puis en profondeur pour descendre jusqu'aux
feuilles afin de trouver le ou les services.
Nous proposons deux algorithmes de recherche : le premier
prend en entrée le système d'exploitation, la
licence, le langage et dans le second
algorithme un nouveau paramètre est ajouté (nom
du service). Ce dernier permet d'avoir des
résultats concis. Dans cette approche suivant les paramètres
donnés en entrée les algorithmes retournent le contenu des
feuilles de l'arbre.
METHODE rechercher
//première solution
ENTREE A:arbre, syst : chaine, lic
: chaine,lang :chaine //syst=système d'exploitation,
lic=licence, lang=langage SORTIE nomserv, @IP, description
nfilsg :Noeud //noeud fils gauche nfrdrt
:Noeud //noeud frère droit nc :Noeud //nc noeud
courant nc(-A.racine
nc(-nfilsg
[Marie Hélène Wassa Mballo] Page
75
1 Tant que nc?null et
nc.valeur?syst et nc.valeur<syst /parcours du niveau
1
2 nc(-nfrdrt
[Marie Hélène Wassa Mballo] Page
76
3 fin tant que
4 si nc=null ou
nc.valeur>syst
5 exit
6 fin si
7 si nc.valeur=syst
8 nc(-nfilsg
9 tant que nc?null et
nc.valeur?lic et nc.valeur<lic /parcours du niveau
2
10 nc(-nfrdrt
11 Fin tant que
12 Si nc=null ou
nc.valeur>lic
13 Exit
14 Fin si
15 Si nc.valeur=lic
16 nc(-nfilsg
17 Tant que nc?null et nc?lang
et nc.valeur<lang //parcours du niveau 3
18 nc(-nfrdrt
19 Fin tant que
20 Si nc=null ou
nc.valeur>lang
21 Exit
22 Fin si
23 Si nc.valeur=lang
24 nc(-nfilsg
25 Tant que nc?null
26 nc(-nfrdrt
27 Retourner nc.valeur
28 Fin tant que
29 Fin si
30 Fin si
31 Fin si
32 Fin rechercher
Le deuxième algorithme proposé est le suivant.
Comme nous l'avons dit précédemment cet algorithme ajoute un
nouveau paramètre qui est le nom du service
ALGORITHME DE RECHERCHE
METHODE rechercher //
deuxième solution
ENTREE A :arbre, syst :chaine,lic
:chaine,lang :chaine, nomservice : chaine SORTIE
nomserv,description,@IP
nfilsg : Noeud //noeud fils gauche nfrdrt : Noeud //noeud
frère droit nc : Noeud //noeud courant
nc(-A.racine
nc(-nfilsg
[Marie Hélène Wassa Mballo] Page
77
1 Tant que nc?null et
nc.valeur?syst et nc.valeur<syst //parcours du niveau
1
2 nc(-nfrdrt
3 fin tant que
4 si nc=null ou
nc.valeur>syst
5 exit
6 fin si
7 si nc.valeur=syst
8 nc(-nfilsg
9 tant que nc?null et
nc.valeur?lic et nc.valeur<lic //parcours du niveau
2
10 nc(-nfrdrt
11 Fin tant que
12 Si nc=null ou
nc.valeur>lic
13 Exit
14 Fin si
15 Si nc.valeur=lic
16 nc(-nfilsg
17 Tant que nc?null et nc?lang
et nc.valeur<lang //parcours du niveau 3
18 nc(-nfrdrt
19 Fin tant que
20 Si nc=null ou
nc.valeur>lang
21 Exit
22 Fin si
23 Si nc.valeur=lang
24 nc(-nfilsg
25 Tant que nc?null et
nc.valeur.nomsev?nomservice
26 nc(-nfrdrt
27 Fin tant que
[Marie Hélène Wassa Mballo] Page
78
[Marie Hélène Wassa Mballo] Page 79
28 Retourner nc.valeur
29 Fin si
30 Fin si
31 Fin si
32 Fin rechercher
Etude de la complexité de l'algorithme de
recherche
L'étude de la complexité ne concerne que le
deuxième algorithme de recherche de services ceci est dicté par
le fait que dans cet algorithme le nom du service est spécifié.
Ce qui signifie qu'une fois au niveau des feuilles une comparaison est
effectuée pour retrouver le service correspondant au nom du service
passé en paramètre.
L'étude de l'algorithme pour trouver la complexité
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, donc dans le pire des cas l'ensemble des noeuds du niveau 1 peuvent
être parcourus.
· L'instruction du bloc 4-6 est une constante qui
s'effectue en O(1), un test Si est effectué. La complexité de ce
bloc est inférieure à celle du bloc 7-32, nous ne
comptabiliserons que cette dernière
· L'instruction du bloc 7-32 regroupe plusieurs
instructions donc nous allons voir la complexité de chacune d'elles
o L'instruction 9 s'effectue en O(2) puisque le nombre
d'itération dépend du nombre maximal de noeuds au niveau 2 de
l'arbre de services, c'est une constante donc elle n'est pas
comptabilisée.
o L'instruction 12 se fait en O(1). Cette complexité
est négligée car elle intervient dans le cas où le
résultat de la recherche n'est pas trouvé.
o L'instruction du bloc 15-30 est composée de
plusieurs instructions dont nous allons étudier la complexité.
· L'instruction 17 s'effectue en O(nlang),
car le nombre d'itérations se fait nlang fois.
· L'instruction du bloc 20 se fait en O(1) un test Si
est effectué pour voir si le programme s'arrête à ce stade
ou si l'exécution continue.
· L'instruction du bloc 23-29 se fait en
O(nserv) elle ne dépend donc que de l'instruction 25 dont le
nombre d'itérations est de nserv fois.
o La complexité totale du bloc 15-30 est égale
à la somme des complexités de ces différentes instructions
O(nlang)+O(1)+O(nserv)= O(nlang)+ O(nserv)
· Ainsi notre algorithme de recherche a une
complexité qui est égale à la somme des complexités
des différentes instructions vues précédemment et nous
obtenons
O(nsyst) +O(nlang) +
O(nserv)
Cette complexité dépend du nombre de noeuds
pour le système d'exploitation, le langage et du nombre de feuilles.
