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 !



Retour à l'index des documents


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 :

  • On appelle les  26 fils potentiels de chaque sommet F(indice_du_fils)[sommet] indicés de 0 à 25

  • Si les fils n'existent pas, la valeur NONE leur sera attribuée.

  • Toute ligne précédée de “\\” ou en italique est un commentaire n’intervenant pas dans l'algorithme.

  • On va tout d’abord créer un algorithme convertissant les mots en une file de lettres, de type Last in First Out, on supposera que les opérations de dépilage et empilage sont des procédures connues.

  • L’algorithme global intégrera deux sous-procédures, et deux affectations indépendantes de ces dernières.



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 :



  • On réutilisera FileDeLettres() ici

  • Trois sous-procédures seront donc nécessaire à l’insertion de mots dans notre arbre lexicographique



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))







Retour à l'index des documents