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

Prolog Discussion :

Comment définir une relation d'équivalence ?


Sujet :

Prolog

  1. #1
    Futur Membre du Club
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 5
    Points : 5
    Points
    5
    Par défaut Comment définir une relation d'équivalence ?
    Bonjour à tous !

    Je souhaiterait implémenter une relation d'équivalence dans un programme ProLog, mais étant encore débutant dans ce langage l'une de mes règles génère systématiquement des erreurs.

    Définition d'une relation d'équivalence (en mathématique) :
    R est une relation d'équivalence si et seulement si :


    • R est réflexive (pour tout x on a xRx)
    • R est transitive (si on a xRy et yRz alors on a xRz)
    • R est symétrique (si on a xRy alors on a yRx)



    Je sais coder les deux premières propriétés :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    % réflexivité :
    r(X,X).
     
    % transitivité :
    r(X,Z) :- r(X,_) , r(_,Z).
    Mais je ne sais pas coder la propriété de symétrie, j'ai naïvement essayé ceci :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    % symétrie :
    r(X,Y) :- r(Y,X).
    Mais cette ligne de code provoque un dépassement systématique de la pile...

    Pouvez-vous m'aidez svp ?

  2. #2
    Membre confirmé Avatar de billynirvana
    Homme Profil pro
    Architecte technique
    Inscrit en
    Décembre 2004
    Messages
    472
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Architecte technique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Décembre 2004
    Messages : 472
    Points : 552
    Points
    552
    Par défaut
    Il suffit juste de coder ce qui est écrit dans l'énoncé... Voici dans le vrai langage ProLog (à adapter avec la version Edimbourg):

    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
    % Définition d'une relation d'équivalence (en mathématique) :
    % R est une relation d'équivalence si et seulement si :
    % * R est réflexive (pour tout x on a xRx)
    % * R est transitive (si on a xRy et yRz alors on a xRz)
    % * R est symétrique (si on a xRy alors on a yRx)
    
    rel(x,y)->
    	eq(x,y); % Voici ze relation. A modifier pour les tests!!
    
    equivalence->
    	reflexive
    	transitive
    	symetrie;
    
    reflexive->
    	rel(x,x);
    
    transitive->
    	rel(x,y)
    	rel(y,z)
    	rel(x,z);
    
    symetrie->
    	rel(x,y)
    	rel(y,x);

    eq(x,y) est une fonction prédéfinie pour interpreter l'égalité. Le but equivalence me rend vrai.
    dif(x,y) est une fonction prédéfinie pour interpreter l'inégalité. Le but equivalence me rend faux.


    Cordialement,


    Billy

  3. #3
    Membre expert

    Profil pro
    imposteur
    Inscrit en
    Avril 2003
    Messages
    3 308
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : imposteur

    Informations forums :
    Inscription : Avril 2003
    Messages : 3 308
    Points : 3 377
    Points
    3 377
    Par défaut
    Citation Envoyé par billynirvana
    Il suffit juste de coder ce qui est écrit dans l'énoncé... Voici dans le vrai langage ProLog (à adapter avec la version Edimbourg):

    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
    % Définition d'une relation d'équivalence (en mathématique) :
    % R est une relation d'équivalence si et seulement si :
    % * R est réflexive (pour tout x on a xRx)
    % * R est transitive (si on a xRy et yRz alors on a xRz)
    % * R est symétrique (si on a xRy alors on a yRx)
    
    rel(x,y)->
    	eq(x,y); % Voici ze relation. A modifier pour les tests!!
    
    equivalence->
    	reflexive
    	transitive
    	symetrie;
    
    reflexive->
    	rel(x,x);
    
    transitive->
    	rel(x,y)
    	rel(y,z)
    	rel(x,z);
    
    symetrie->
    	rel(x,y)
    	rel(y,x);

    eq(x,y) est une fonction prédéfinie pour interpreter l'égalité. Le but equivalence me rend vrai.
    dif(x,y) est une fonction prédéfinie pour interpreter l'inégalité. Le but equivalence me rend faux.


    Cordialement,


    Billy
    C'est du prolog "standard" ça ? Je suis pas un spécialiste, mais ça a une drôle de tête quand même... Sans doute des tas de trucs que je connais pas...

  4. #4
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    Citation Envoyé par Eusebius
    C'est du prolog "standard" ça ?
    C'est du Prolog avec la syntaxe de Marseille (celle utilisée par Alain Colmerauer, l'inventeur de Prolog, et que billynirvana utilise), par opposition à la syntaxe d'Edimburgh, qu'on est nombreux à utiliser ici.
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

  5. #5
    Membre expert

    Profil pro
    imposteur
    Inscrit en
    Avril 2003
    Messages
    3 308
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : imposteur

    Informations forums :
    Inscription : Avril 2003
    Messages : 3 308
    Points : 3 377
    Points
    3 377
    Par défaut
    Citation Envoyé par pcaboche
    C'est du Prolog avec la syntaxe de Marseille (celle utilisée par Alain Colmerauer, l'inventeur de Prolog, et que billynirvana utilise), par opposition à la syntaxe d'Edimburgh, qu'on est nombreux à utiliser ici.
    OK, merci de la précision.

  6. #6
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    Maintenant, si on a;
    • r : E |-> E
    • E est un ensemble dénombrable
    On peut prouver que r est une relation d'équivalence de la façon suivante:

    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
    34
    35
    36
    rel_equiv :-
      reflexive,
      transitive,
      symetrique.
     
     
     
    reflexive :-
      forall(
         r(X, _)
      ,
         r(X, X)
      ).
     
     
     
    transitive :-
      forall(
        (
          r(X, Y),
          r(Y, Z)
        )
      ,
         r(X, Z)
      ).
     
     
     
     
     
    symetrique :-
      forall(
         r(X, Y)
      ,
         r(Y, X)
      ).
    Maintenant, si E n'est pas dénombrable, c'est plus difficile...
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

  7. #7
    Futur Membre du Club
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 5
    Points : 5
    Points
    5
    Par défaut
    Je vous remercie pour vos réponses rapides qui sont très intéressantes, mais j'ai du mal poser ma question : ce que je voulais savoir, ce n'était pas comment prouver qu'une relation est une relation d'équivalence (bien que cela me servira surement), mais sachant qu'une relation est d'équivalence, fabriquer des règles pour que ProLog puisse trouver de nouveaux faits à partir de faits connus.

    exemple des colocataires :
    Julie, Solange et Sophie sont colocataires et habite donc sous le même toit.

    Soit la base de fait suivante :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    meme_toit(julie,solange).
    meme_toit(solange,sophie).
     
    meme_toit(romain,jeff).
    meme_toit(romain,grégoire).
    Je souhaite programmer des règles pour que ProLog soit capable de déduire les faits suivants :
    Julie habite sous le même toit que Julie (propriété de réflexivité)
    Julie habite sous le même toit que Sophie (propriété de transitivité)
    Solange habite sous le même toit que Julie (propriété de symétrie)

    ce qui en code donne :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    meme_toit(julie,julie).
    meme_toit(julie,sophie).
    meme_toit(solange,julie).
    Bien que j'arrive à programmer la relation de reflexivité :
    Les relations de transitivité et de symétrie génèrent des erreurs lors de l'éxécution :

    programme :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    % transitivité :
    meme_toit(X,Z) :- meme_toit(X,Y) , meme_toit(Y,Z).
    % symétrie :
    meme_toit(X,Y) :- meme_toit(Y,X).
    Lors de l'exécution voici les erreurs générés :
    pour la transitivité :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    5 ?- meme_toit(julie,sophie).
    ERROR: Out of local stack
       Exception: (14,514) meme_toit(julie, sophie) ?
    pour la symétrie :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    6 ?- meme_toit(solange,sophie).
    ERROR: Out of local stack
       Exception: (59,743) meme_toit(solange, sophie) ?

    J'imagine qu'il manque un certain nombre de choses importantes dans mes règles, mais je n'arrive pas à trouver quoi. Pouvez me mettre sur la piste svp ?

  8. #8
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    Citation Envoyé par Amon-Râ
    mais sachant qu'une relation est d'équivalence, fabriquer des règles pour que ProLog puisse trouver de nouveaux faits à partir de faits connus.
    Dans ce cas là, le plus simple est de définir un prédicat meme_toit1/2 qui définit tes faits et d'écrire le prédicat meme_toit/2 à partir de cette relation.

    Après, ça demande un peu de réflexion pour avoir toutes les relations 1 et 1 seule fois (et sans boucle).
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

  9. #9
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    Voici le programme qui retournera les relations d'équivalence que l'ont peut déduire à partir du prédicat meme_toit1/2. En plus, les relations d'équivalence n'apparaissent qu'une fois chacune et sont triées dans l'ordre alphabétique :



    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
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    :- dynamic( meme_toit1/2 ).
     
    meme_toit1(julie,solange).
    meme_toit1(solange,sophie).
     
    meme_toit1(romain,jeff).
    meme_toit1(romain,grégoire).
     
     
     
    ensemble(E) :-
      findall(
        X
      ,
        (meme_toit1(X,_) ; meme_toit1(_,X))
      ,
        L
      ),
     
      sort(L, E).
     
     
     
     
    trans(L1, [], L2) :- 
      !,
      sort(L1, L2).
     
     
    trans(L1, L2, R) :-
     
      findall(Y
      ,
        ( 
          member(X, L2),
          (meme_toit1(X,Y) ; meme_toit1(Y,X)),
          \+memberchk(Y,L1),
          \+memberchk(Y,L2)
        )
      ,
        L3
      ),
     
      append(L1, L2, L4),
      trans(L4, L3, R).
     
     
     
     
    combi(L, X, Y) :-
      member(X, L),
      member(Y, L).
     
     
     
     
    meme_toit(X,Y) :-
      ensemble(E),
      meme_toit(E, [], X, Y).
     
     
    meme_toit([Elem|Q], Visited, X, Y) :-
      \+memberchk(Elem, Visited),
      !,
      trans([], [Elem], L),
      (
        combi(L, X, Y)
      ;
        (
          union(Visited, L, S),
          meme_toit(Q, S, X, Y)
        )
      ).
     
     
    meme_toit([_|Q], Visited, X, Y) :-
      meme_toit(Q, Visited, X, Y).
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

  10. #10
    Futur Membre du Club
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 5
    Points : 5
    Points
    5
    Par défaut
    Génial !Cà correspond tout à fait à ce que je voulais.

    En fait si j'ai bien compris le fonctionnement de ton programme :

    On donne une liste composé d'un élément en deuxième argumant à la fonction trans, et celle-ci renvoie la liste de tous les éléments de sa classe d'équivalence (c'est à dire tous les colocataires vivant sous le même toit), puis on regarde si les deux objets X et Y appartiennent à la même classe. Si oui, alors on a fini, sinon on recommence avec le terme suivant dans la liste (si il n'appartient pas déjà à une classe d'équivalence déjà écrite : c'est le rôle de la liste Visited) jusqu'à ce qu'on ait regardé tous les éléments.

    Merci beaucoup !

  11. #11
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    Citation Envoyé par Amon-Râ
    On donne une liste composé d'un élément en deuxième argumant à la fonction trans, et celle-ci renvoie la liste de tous les éléments de sa classe d'équivalence (c'est à dire tous les colocataires vivant sous le même toit),
    Tout à fait. En théorie des graphes, on appelle ça une "clique" (un sous-graphe complet).

    Il m'a semblé, de prime abord, logique de procéder ainsi:
    - 1er argument: les points déjà visités
    - 2ème argument: les points à visiter
    - 3ème argument: le résultat (l'ensemble des gens habitant sous le même toit, trié)

    Mais on peut changer l'ordre des arguments (ce que j'ai fait pour meme_toit/4).


    Citation Envoyé par Amon-Râ
    puis on regarde si les deux objets X et Y appartiennent à la même classe.
    Pas tout à fait. En fait, le prédicat member/2 permet d'énumérer les éléments d'une liste (pour vérifier l'appartenance, on utilise plutôt memberchk/2). Le prédicat combi/3 énumère tous les couples X,Y possibles avec X et Y appartenant tous deux à L. C'est ainsi qu'on énumère les relations d'équivalence.


    Citation Envoyé par Amon-Râ
    Si oui, alors on a fini, sinon on recommence avec le terme suivant dans la liste (si il n'appartient pas déjà à une classe d'équivalence déjà écrite : c'est le rôle de la liste Visited) jusqu'à ce qu'on ait regardé tous les éléments.
    Quand on a fini d'énumérer toutes les relations possibles à partir d'un terme donné (grâce à combi/3) on essaye d'en trouver d'autres à partir d'un autre terme, en prennant gare à ne pas énumérer 2 fois la même solution (d'où l'utilisation de la liste Visited, en effet).


    Citation Envoyé par Amon-Râ
    Merci beaucoup !
    De rien. C'était un exercice vraiment sympa, je trouve.
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

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

Discussions similaires

  1. Réponses: 2
    Dernier message: 29/06/2006, 14h58
  2. [ADO.NET]Comment réaliser une relation sur plusieurs champs?
    Par kleomas dans le forum Accès aux données
    Réponses: 3
    Dernier message: 13/03/2006, 13h40
  3. Comment comment définir une clef primaire dans une table??
    Par nek_kro_kvlt dans le forum Bases de données
    Réponses: 4
    Dernier message: 07/02/2005, 22h06
  4. Réponses: 8
    Dernier message: 20/12/2004, 16h14

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