Bonjour. J’ai besoin d’aide pour un exercice. D’abord, je pense n’avoir pas bien compris l’énoncer. Voilà l’énoncé :
Bravo, vous venez d’être embauché(e) comme détective à l’université. Votre tâche est de coffrer sans pitié les bandes d’enseignants et étudiants corrompus. L’avantage, c’est que suivant la structure de la bande, il peut suffire de capturer un petit groupe de personnes pour aussi embarquer tout le reste, par effet «avalanche». Cependant, votre carrière débute seulement et vous risquez d’avoir de nombreux groupes de personnes malhonnêtes à mettre derrière les barreaux. Aussi aimeriez vous avoir un programme qui fasse la sale besogne à votre place. Heureusement, vous avez suivi un cours de méthodes discrètes. Vous pouvez donc modéliser ces mafias comme suit. Appelons M un ensemble de personnes mal intentionnées. Afin de capturer la structure du groupe on va introduire une relation binaire A( comme «Avalanche» ) qui associe deux personnes p1,p2 de M.On notera p1Ap2 pour dire «si on attrape p1, p2 tombe aussi». Attention! A n’est pas symétrique (les lois des malfrats sont parfois impénétrables). Les énigmes à résoudre sont les suivantes:
-
Etant donné (M,A) et F ⊆ M, déterminer toutes les personnes que l’on capturera par la relation A partant de F.
-
Pour une paire (M,A) donnée, trouver les groupes de personnes minimaux par inclusion qui permettent de capturer tout le monde. Autrement dit, on veut trouver les plus petits F dont la réponse serait M dans la question précédente.
-
Calculer tous les ensembles de personnes «capturables», c’est-à-dire les F ⊆ M qui ne permettent pas d’embarquer d’autres personnes que celles de F. Autrement dit, on cherche les F ⊆ M pour lesquels la première question renvoie F.
Figure 2 text. Click triangle to expand
Votre premiere affaire concerne 5 personnes: Vincent, Aurelie, Lucas, Oscar, Yannick. On pose donc M = {v,a,l,o,y}. La relation A est illustree dans la Figure 2. Une paire (M,A) peut etre representee par un graphe dirige ou M sont les sommets et un arc(u,v) signifie uAv. Par example dans la figure, on a aAo, c’est-a-dire <Si Aurelie tombe, Oscar aussi. > Quand on choisit F = {l,y} et qu’on suit tous les chemins possibles (en vert), on capture au final {l,y,v,o} mais pas a. Un ensemble qui permetter de capture tout le monde est par exaemple f = {a,y}. Il est in plus minimial car on ne peut ni recuperer y par a, ni a par y ; on ne peut enlever ni l’un ni l’autre de F .
Dans le cas de l’exemple j’ai fais ça :
arc(a, o).
arc(a, l).
arc(l, v).
arc(v, l).
arc(y, v).
arc(y, o).
successeur(X, Y) :- arc(X, Y).
Le predicat successeur permet de repondre aux deux premières questions. Mais par exemple pour la première question F = {a, y}, il faut faire successeur(a, X) puis successeur(y, X) pour trouver toutes les solutions. Pour la deuxième question il suffit de mettre le paramètre inconni en première position . Mais c’est trop facile pour ètre la solution voulue. Mon objectif est d’écir un prédicat qui me retournerit la liste des solutions pour chacunes des 2 premières questions.
Merci d’avance…