Page Perso de Justin CANO |
|||
Documents relatifs à l’algorithmie |
|||
|
|
|
|
SEMESTRE 5 |
|||
LES TP : |
|
|
|
|
|
|
|
|
TP 0 : Cliquez ici |
|
|
|
|
|
|
|
TP 1 : Cliquez ici |
|
|
|
|
|
|
|
TP 2 : Cliquez ici |
|
|
|
|
|
|
|
TP 3 : Cliquez ici |
|
|
|
|
|
|
|
TP 4 : Cliquez ici |
|
|
|
|
|
|
|
|
|
|
Résumé en PDF → Cliquez ici !
|
|||
|
|
||
Bonus : comment gérer un arbre lexicographique ? à la sauce Bartholet, Argentier, Bera et Cano. TD 5 , Groupe ARGENTIER, BARTHOLET, BERA & CANO.
Algorithmique > Mardi 25 Novembre 2014 Arbres lexicographiques :
I - Algorithme de Recherche :
Hypothèses & Notations :
Algorithme : def FileDeLettres(mot) n = (nombre de lettres du mot) créer une file LIFO de taille n nommée L pour i allant de 1 à n enfiler i ème lettre du mot retourner L
noeud courant = racine \\ On fait débuter la recherche par la racine RI = -1 \\ RI = Nombre de recherches infructueuses, comme il n’y en a pas encore eu, on lui affecte une valeur aberrante.
def Recherche(L, noeud_courant) si L est vide: retourner VRAI \\ cela signifie qu’il n’y a plus rien à chercher sinon: x= défilage(L) \\ La file sera alors allégée de son élément le plus ancien. si valeur(noeud_courant) = x: RI=0 pour j allant de 0 à 26 faire Recherche(L,F(j)[noeud_courant]) \\ on recherche le second élément de la liste dans chacun des fils du noeud initial sinon: RI = RI + 1 \\ RI = Nombre de recherches infructueuses incrémenté si RI == 26: retourner FAUX \\ Si tous les fils ont été balayés, la recherche est infructueuse. si RI == 0: retourner FAUX \\ Ce cas est en fait celui d’une racine différente de la première lettre. RI vaut au moins 1 dans tous les autres cas.
Complexité de l'algorithme : Si on note n la taille (nombre de lettre du mot) et qu’on ne comptabilise pas l’algorithme de conversion dans le calcul, la complexité de l’algorithme précédent sera : O( Log26(n))
II - Algorithme d’insertion :
Commentaires généraux :
Algorithme :
Soit M le mot qu’il faut insérer
[Initialisation] Noeud_Courant = racine; Sommet_Y=NONE; Rang_Lettre = 1;
FileDeLettres(M): RI = 0; def CréationSommet( Valeur_Utile, Père): si recherche( Valeur_Utile ,père) == FAUX: \\ Pour qu’il y ait création, il faut que le sommet fils ait une valeur différente de ses “frères” ; si tel est le cas au moins un des fils (ou plutôt un des emplacements potentiels) aura une valeur égale à NONE (il est pour l’instant inexistant) k =0; tant que (Z != NONE) & (k<26) \\ On recherche un des emplacement encore non afféctés, avec une condition qui permet d’éviter une boucle infinie. Z=Valeur( F(k)[Père] ) k = k+1 Valeur_Utile = Valeur( F(k)[Père] ) \\ On crée le sommet fils en affectant la Valeur Utile choisie (lettre) à l’emplacement libre. Retourner Noeud_Crée = F(k)[père]
def RechercheLettre(Lettre, Noeud_courant) pour i allant de 0 à 25 \\ On ne recherche la lettre en question parmi les fils du noeud indiqué si Valeur( F(i)[Sommet_Y] ) = Lettre Sommet_Y = F(i)[Noeud_courant] Retourner Sommet_Y sinon Sommet_Y = NONE Retourner Sommet_Y
def insertion(L,Noeud_courant) si L est non vide: y = défilage(L) Sommet_Y=RechercheLettre(y,noeud_courant) si Sommet_Y != NONE faire insertion(L,Sommet_Y) sinon: faire CréationSommet(y, Noeud_courant) faire insertion(L,Noeud_Crée)
Complexité : O( Log26(n))
|
|||
|
|
|
|
|
|