IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algo sur les ABR


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    327
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2008
    Messages : 327
    Points : 114
    Points
    114
    Par défaut Algo sur les ABR
    Bonsoir,

    Alors voila un petit moment que j'essaie de trouver deux algorithmes sur les ABR, l'un qui dit si un ABR est contenu dans un autre (tout les éléments de A sont contenus dans B, A et B étant deux ABR) et le second qui dit si un ABR est de domaine plus petit qu'un autre (le plus petit élément de A est supérieur ou égal au plus petit élément de B et le plus grand élément de A est inférieur ou égal au plus grand élément de B). Les algos que j'ai fais ne marchent apparemment pas.
    Le premier:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    Contenu (A: arbre, B: arbre):booleen
    val:Entier
    début
           si vide?(A) ET vide?(B) alors
                 renvoyer vrai
           val <- A.noeud
           sinon si non(app?(val, B)) alors
                 renvoyer faux
           fin si
           contenu(A.sag, B.sag)
           contenu(A.sad, B.sad)
    fin
    Le deuxième:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    domaine (A: arbre, B: arbre):booleen
    val_minA, val_minB, val_maxA, val_maxB:Entier
    début
           si vide?(A) ET vide?(B) alors
              renvoyer vrai
           sinon si vide?(A) OU vide?(B) alors
              renvoyer faux
           fin si
           val_minA <- min(A)
           val_minB <- min(B)
           val_maxA <- max(A)
           val_maxB <- max(B)
           si val_minB <= val_minA ET val_maxA <= val_maxB alors
               renvoyer vrai
           sinon
               renvoyer faux
           fin si
    fin
    Merci de l'aide que vous pourrez m'apporter

  2. #2
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Voyons, supposons que mes arbres binaires soient définis ainsi :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    data Tree a = Leaf | Node (Tree a) a (Tree a)
    Commençons par faire la liste des éléments d'un arbre :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    flatten :: Tree a -> [a]
    flatten Leaf = []
    flatten (Node fg a fd) = flatten fg ++ (a : flatten fd)
    On est bien d'accord que l'invariant pour un arbre binaire de recherche est le suivant :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    prop_searchTree :: (Ord a) => Tree a -> Bool
    prop_searchTree Leaf = True
    prop_searchTree (Node fg a fd) = 
        prop_searchTree fg && prop_searchTree fd && 
        all (< a) (flatten fg) && all (> a) (flatten fd)
    Ce qui signifie qu'on peut écrire une procédure de recherche qui nous dit si tel élément est dans un arbre ou non :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    contains :: (Ord a) => Tree a -> a -> Bool
    contains Leaf _ = False
    contains (Node fg a fd) b
        | a == b     = True
        | a < b      = contains fd b
        | otherwise  = contains fg b
    A partir de là, une méthode naïve pour vérifier si a est un sous-ensemble de b est :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    subsetOf :: (Ord a) => Tree a -> Tree a -> Bool
    subsetOf tA tB = all (contains tB) (flatten tA)
    et on peut utiliser cela pour tester l'égalité :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    equal :: (Ord a) => Tree a -> Tree a -> Bool
    equal tA tB = subsetOf tA tB && subsetOf tB tA
    Bien sûr on peut améliorer ces méthodes, mais je te laisse le soin de le faire.

    --
    Jedaï

  3. #3
    Membre régulier
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    327
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2008
    Messages : 327
    Points : 114
    Points
    114
    Par défaut
    Alors je ne critique aucunement ce que tu as fait mais le seul soucis est que je ne comprend pas du tout la syntaxe du langage d'algo que tu as utilisé

  4. #4
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    C'est du Haskell (langage de haut niveau, purement fonctionnel et à évaluation paresseuse).

    Quant à tes algorithmes, le second est correct (il correspond exactement à ta description en tout cas), le premier est incorrect, le début marche mais :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    contenu(A.sag, B.sag)
    contenu(A.sad, B.sad)
    ne marche pas du tout, d'une part tu ne renvoies rien, quelque soit le résultat de ces fonctions, d'autre part, A.sag n'est pas forcément contenu par B.sag même si B contient A.sag .

    --
    Jedaï

  5. #5
    Membre régulier
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    327
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2008
    Messages : 327
    Points : 114
    Points
    114
    Par défaut
    Ok alors pour les second si il est bon j'ai du me tromper quelque part dans mon implémentation alors par contre pour le premier je vois à peut près ce que tu veux dire, et je suppose que tu m'en donne les détails dans ta réponse précédente je vais donc tenté de comprendre ce que tu as écrit dans ton langage si j'y arrive

  6. #6
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Pour le second, il y a juste un petit problème si l'un est vide et l'autre non, tu ne traite pas ce cas, non plus que tu ne traites le cas où A est vide dans le premier.

    --
    Jedaï

  7. #7
    Membre régulier
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    327
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2008
    Messages : 327
    Points : 114
    Points
    114
    Par défaut
    Voila en effet pour le second cela devait être la raison pour laquelle cela ne marchait pas sinon pour le premier je suis toujours dans le flou, je n'arrive décidément pas à comprendre ce que tu as marqué mais je continu

  8. #8
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 76
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    La structure de liste générale (récursive) permet de représenter tous les types d'arbres (binaires ou non).
    Voici un petit programme en python qui teste si tous les éléments d'une première liste sont inclus dans une autre liste, quel que soit le niveau d'imbrication des deux listes.
    Je pense que les idées sont les mêmes que dans la proposition de Jedaï, simplment la syntaxe python est plus proche du pseudocode.
    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    def inclatom(X,L2): # teste si un atome est inclus dans une liste aplatie
        if L2==[]: 
            return False # aucun atome dans la liste vide
        A=L2[0] # A est la tete de liste (car en lisp)
        B=L2[1:] # B la queue (cdr en lisp)
        if X==A: # si X est A OK!
            return True
        else:
            return inclatom (X,B) # sinon tester si l'atome est dans la queue 
     
    def flat (L): # aplatit la liste en ne gardant que les atomes au plus bas niveau
        if L==[]:
            return L
        A=L[0]
        B=L[1:]
        if A.__class__!=list:
            return [A]+flat(B)
        else:
            return flat(A)+flat(B)
     
     
    def inclist (L1,L2): # teste si tous les elements de la liste L1 se retrouvent dans la liste L2
        P=flat(L1)
        Q=flat(L2)
        return all ([inclatom(X,Q) for X in P])
     
     
    #programme principal
    print inclist ([[1, 2],3],[ 4, 1, [5, 2, 3]])
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  9. #9
    Membre régulier
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    327
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2008
    Messages : 327
    Points : 114
    Points
    114
    Par défaut
    En effet je comprend mieux le principe avec le code python, car déjà c'est un langage que je connais et donc que je peux mieux comprendre que le Haskell que je ne connait vraiment pas et dont j'ignorais même jusqu'à l'existence

  10. #10
    Membre régulier
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    327
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2008
    Messages : 327
    Points : 114
    Points
    114
    Par défaut
    Voila j'ai essayé de faire un algo non récursif, mais je le transformerai en récursif si il est correct. Cet algo test seulement si A est contenu dans B. Le voici:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    contenu (A: arbre, B: arbre):booleen
    tmp : Arbre
    test : Entier
    début
        tmp <- A
        si (vide?(A) ET vide?(B)) OU (vide?(A) ET non vide?(B)) alors
           renvoyer vrai
        sinon si non vide?(A) ET vide?(B) alors
           renvoyer faux
        fin si
        tant que non vide?(A) faire
           si recherche (A.val, B) alors
              test <- 1
           sinon
              test <- 0
           fin si
           A <- A.sad
        fin tant que
        A <- tmp
        tant que non vide?(A) faire
           si recherche (A.val, B) alors
              test <- 1
           sinon
              test <- 0
           fin si
           A <- A.sag
        fin tant que
        si test = 1 alors
           renvoyer vrai
        sinon
           renvoyer faux
        fin si
    fin

  11. #11
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Une bonne part de la différence tient au fait que Python est impératif alors que Haskell est fonctionnel. D'autre part les listes de Python ne sont pas aussi fortement typées donc on peut y mettre des éléments de types différents. L'approche d'Haskell est plus fortement typé (et nettement plus performante au final).

    Par ailleurs, il y a d'autres différences, par exemple le test d'appartenance inclatom() travaille sur la version aplatie de l'arbre et a une complexité moins bonne que le test d'appartenance contains() d'Haskell qui travaille directement sur l'arbre et utilise sa nature d'arbre binaire de recherche.

    De plus flat() et flatten() ne renvoie pas la même liste : flatten() renvoie les éléments dans l'ordre tandis que flat() dépend de la structure de l'arbre et les renvoie dans l'ordre d'un parcours infixe.

    Ta solution itérative est incorrecte, elle n'explore que les chaines extrèmes de A (la plus à gauche et la plus à droite). Pour les ABR, il est vraiment préférable de travailler récursivement.

    Je rappelle quel est l'équivalent de contenu() dans mon code :
    Code Haskell : Sélectionner tout - Visualiser dans une fenêtre à part
    subsetOf tA tB = all (contains tB) (flatten tA)

    Si on intègre également les fonctions que tu n'as probablement pas dans ta librairie (contains() correspond à ton app?()) :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    flatten Leaf = []
    flatten (Node fg a fd) = flatten fg ++ (a : flatten fd)
     
    -- Fait partie de la bibliothèque standard de Haskell :
    all p [] = True
    all p (x:xs) = p x && all p xs
    --
    Jedaï

  12. #12
    Membre régulier
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    327
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2008
    Messages : 327
    Points : 114
    Points
    114
    Par défaut
    Ok et bien je ne connaissais pas du tout ce langage fonctionnel, le seul que je connaisse est Lisp (ou Scheme).

    Sinon en effet mon algo est incorrect je l'ai d'ailleurs réalisé juste un peu après l'avoir posté. Apparemment mon soucis est que je n'arrive pas à voir quand effectuer la récursion sur les noeuds

    Et je suis vraiment désolé mais je suis vraiment paumer avec ce langage je ne comprend pas à quoi correspond cette syntaxe

  13. #13
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    subsetOf tA tB = all (contains tB) (flatten tA)
    définit une fonction "subsetOf" qui prend deux arguments tA et tB. Elle retourne le résultat de l'expression "all (contains tB) (flatten tA)" qui est un appel à la fonction "all" sur les arguments "contains tB" et "flatten tA". "contains tB" est une application partielle de la fonction contains qui renvoie donc une fonction anonyme qui teste si son argument appartient à tB, "all" applique cette fonction anonyme à tous les éléments de la liste renvoyée par "flatten tA" qui contient tous les éléments de tA, "all (contains tB) (flatten tA)" vérifie donc que tous les éléments de tA appartiennent à tB.

    --
    Jedaï

  14. #14
    Membre régulier
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    327
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2008
    Messages : 327
    Points : 114
    Points
    114
    Par défaut
    donc si j'ai bien compris c'est comme si j'écrivais:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    contenu (A: arbre, B: arbre):booleen
    début
          renvoyer app?(A.val, B) (mais pour toute les valeur de A)
    fin
    Si c'est pas ça j'ai toujours rien compris

  15. #15
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Tout à fait, et tu es bien d'accord que c'est ce que tu veux faire, n'est-ce pas ? Ton problème est dans ce "(mais pour toutes les valeurs de A)".

    En fait tu as deux approches : soit tu construit quelque chose qui te permet de parcourir un arbre et tu fais :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    contenu (A: arbre, B: arbre):booleen
    début
       for val in A
          si non app?(val, B)
             renvoyer faux
       fin
       renvoyer vrai
    fin
    Soit tu ne construit pas cette abstraction intermédiaire et tu utilise une récursion directe :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    contenu?(A: arbre, B: arbre):booleen
    début
      renvoyer vide?(A) OU (app?(A.val, B) ET contenu?(A.sag, B) ET contenu?(A.sad, B))
    fin
    --
    Jedaï

  16. #16
    Membre régulier
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    327
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2008
    Messages : 327
    Points : 114
    Points
    114
    Par défaut
    Oui c'est bien ce que je veux. Donc si je fais:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    contenu (A: arbre, B: arbre):booleen
    début
         si non app?(parcours(A), B) alors
             renvoyer faux
         fin si
         renvoyer vrai
    fin
    la fonction parcours est:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    parcours (A: arbre):entier
    début
         si non vide?(A) alors
            renvoyer A.val
            parcours (A.sag)
            parcours (A.sad)
         fin si
    fin

  17. #17
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Que renvoie parcours() ? A priori tu ne testes toujours que la racine, et tu plantes si A est vide.

    J'ai mis un petit addendum à mon message précédent, je pense que ça te suffira.

    --
    Jedaï

  18. #18
    Membre régulier
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    327
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2008
    Messages : 327
    Points : 114
    Points
    114
    Par défaut
    Je n'ai rien dit ma fonction ne marcherait pas car "parcours" renverrai toujours la même valeur.

    Sinon oui en effet je comprend mieux maintenant avec ce que tu as marqué avant je préfère d'ailleurs la version récursive

    Merci beaucoup de ton aide précieuse

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. probleme Exo sur les ABR
    Par benjy13 dans le forum Autres SGBD
    Réponses: 0
    Dernier message: 17/06/2009, 20h21
  2. Petit algo sur les combinaisons
    Par Blaede dans le forum Mathématiques
    Réponses: 5
    Dernier message: 03/03/2008, 00h51
  3. Algo sur les graphes
    Par BatuBou dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 27/12/2007, 19h33
  4. Algo sur les factoriels
    Par Panaméen dans le forum Mathématiques
    Réponses: 13
    Dernier message: 04/11/2007, 16h08
  5. Réponses: 24
    Dernier message: 27/09/2005, 22h16

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo