Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.
Règles complexes – entrainement
Les activités d’entrainement consistent à traiter des exercices d’entraînement. Vous devez d’abord tenter de traiter ces exercices sans dévoiler d’indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de découverte ou d’entraînement précédemment traités. Si vous avez besoin d’indices ou si vos solutions sont erronées, analysez les causes de vos erreurs – au besoin, demandez des explications à une personne qualifiée – et refaites les exercices concernés après un délai d’au moins une journée et au plus quelques jours.
Activité d’entraînement B.ent
B.ent1
On travaille avec une base de connaissances représentant trois types de plats utilisables dans des menus.
plat(entree, "pâté", 200, 6).
plat(entree, "salade", 120, 1).
plat(princ, "poulet frites", 360, 35).
plat(princ," couscous", 280, 18).
plat(dessert, "sorbet", 180, 0).
plat(dessert, "cake", 150, 4).
Les slots du prédicat plat représentent respectivement :
- Le type d’un plat :
entreepour une entrée,princpour un plat principal, etdessertpour un dessert. - Son nom.
- Son apport énergétique en kilocalories.
- Son apport en protéines, exprimé en grammes.
Vous devez définir un prédicat repas permettant de composer un repas avec un nombre maximum donné de kilocalories et une quantité minimum donnée de protéines.
Par exemple, le but…
repas(700, 30, E, P, D).
…doit produire tous les repas constitués d’une entrée E, d’un plat principal P et d’un dessert D, ayant un apport énergétique inférieur ou égal à 700 kilocalories et comportant au moins 30 grammes de protéines.
Pour chaque résultat du but, le nom de l’entrée doit remonter dans la variable de sortie E, le nom du plat principal doit remonter dans la variable de sortie P et le nom du dessert doit remonter dans la variable de sortie D.
Les réponses produites par l’évaluation du but donné en exemple doivent être :
D = "sorbet", E = "salade", P = "poulet frites"
D = "cake", E = "salade", P = "poulet frites"
Remarque : pour exprimer que A est inférieur ou égal à B, on écrit A=<B et non A<=B. Cette syntaxe a pour but d’éviter de confondre l’opérateur de comparaison avec le symbole d’implication logique (bien que ce symbole s’écrive :- et non <=).
Ce prédicat peut s’écrire avec une seule clause. Voici une solution partielle à compléter :
repas(CalMax, ProtMin, E, P, D) :-
plat(entree, E, Cal1, Prot1),
% À compléter
Le premier but de la clause dit que Le plat de nom E est une entrée qui apporte Cal1 kilocalories et Prot1 grammes de protéines.
Il reste à exprimer les deux plat restant (plat principal et dessert), et leurs apports en protéines et kilocalories, puis calculer l’apport total en énergie et protéines, puis exprimer les contraintes sur la quantité d’énergie de de calories.
repas(CalMax, ProtMin, E, P, D) :-
plat(entree, E, Cal1, Prot1),
plat(princ, P, Cal2, Prot2),
plat(dessert, D, Cal3, Prot3),
Cal is ....., Prot is .....,
% À compléter
Les variables Cal et Prot permettent de récupérer le nombre total de kilocalories et la quantité totale de protéines.
repas(CalMax, ProtMin, E, P, D) :-
plat(entree, E, Cal1, Prot1),
plat(princ, P, Cal2, Prot2),
plat(dessert, D, Cal3, Prot3),
Cal is Cal1+Cal2+Cal3, Prot is Prot1+Prot2+Prot3,
Cal=<CalMax, Prot>=ProtMin.
B.ent2
Le graphe suivant représente les liens de parenté entre plusieurs personnes dont les noms ont été remplacés par des numéros pour des raisons de protection des données personnelles (RGPD). Une flèche d’un sommet $A$ vers un sommet $B$ indique que $A$ est le père biologique ou la mère biologique de $B$.

Ces liens de parenté directs sont modélisés par le prédicat parent.
parent(1,4). parent(1,5). parent(2,4). parent(2,5).
parent(3,8). parent(3,9). parent(4,8). parent(4,9).
parent(5,10). parent(6,10). parent(6,11). parent(7,11).
parent(8,12). parent(10,12). parent(9,13). parent(11,13).
Question 1
On définit le prédicat siblings tel que siblings(A,B) est satisfait si et seulement si A est le frère ou la soeur de B dans le sens où :
- il existe deux personnes distinctes qui sont toutes les deux parents directs de
Aet deB, AetBsont deux personnes distinctes (on ne considère pas qu’une personne est son propre frère ou sa propre soeur.
siblings(A,B) :-
parent(P1,A), % une personne P1 est père ou mère de A
parent(P2,B), % une personne P2 est père ou mère de B
P1\==P2, % P1 et P2 sont deux personnes distinctes
A\==B, % A et B sont deux personnes distinctes
parent(P1,B), % P1 est le père ou la mère de B
parent(P2,A). % P2 est le père ou la mère de B
L’ordre dans lequel sont placé les but de la clause peut paraitre étrange. Il se justifie par les deux critères suivant :
- Une condition telle que
X\==Yéchoue si au moins l’un des deux termes comparés est une variable non instanciée (n’ayant pas de valeur). Pour qu’une telle condition soit pertinente, il faut donc qu’au moment où elle est évaluée, les deux valeurs à comparer soient connues. - Pour des raisons d’efficacité, on a intérêt à placer ce genre de condition le plus tôt possible dans l’ordre des buts d’une clause car cela limitera la combinatoire de la recherche de solutions.
Mais il y a un problème avec ce prédicat. Si on évalue le but…
siblings(8,S).
…on obtient deux fois la même réponse :
S = 9
S = 9
…car les deux variable P1 et P2 sont en quelque sorte interchangeables. Le but a été satisfait deux fois :
- Une fois avec
P1=3etP2=4. - Une fois avec
P1=4etP2=3.
Cherchez un moyen d’éviter ce petit problème en modifiant la définition du prédicat. N’hésitez pas à faire des essais sur machine.
On peut modifier la condition P1\==P2 en la remplaçant par une autre, plus restrictive, sachant que les valeurs P1 et P2 sont des entiers.
On remplace P1\==P2 par P1<P2.
siblings(A,B) :-
parent(P1,A), parent(P2,A), P1<P2,
parent(P1,B), parent(P2,B), A\=B.
Question 2
On évalue le but…
siblings(X,Y).
…et on obtient le résultat :
X = 4, Y = 5
X = 5, Y = 4
X = 8, Y = 9
X = 9, Y = 8
Pourquoi obtient-on deux fois chacune des deux fratries ?
Parce-que les rôles des variables A et B sont interchangeables et qu’il y a donc deux manières de satisfaire le but pour chaque fratrie.
Comment pourrait-on éviter cette redondance en modifiant le but, sans changer la définition du prédicat ?
siblings(X,Y), X>Y.
Si on incorporait la nouvelle condition dans la définition du prédicat, cela pourrait-il poser problème pour certains buts ? Donnez un exemple.
Si on remplace A\==B par A<B dans la clause qui définit le prédicat siblings, comme ceci…
siblings(A,B) :-
parent(P1,A), parent(P2,B),
P1<P2, A<B,
parent(P1,B), parent(P2,A).
…alors le fonctionnement avec un but tel que…
siblings(X,Y).
…sera correct, mais par exemple le but…
siblings(9,S).
…va échouer car la condition A<B impose que la valeur S soit le plus petite que 9.
Question 3
Une personne A est un ancêtre d’une personne B si et seulement si une des deux propositions suivantes est vraie :
Aest parent direct deB.Aest ancêtre d’un parent direct deB.
Définissez le prédicat ancetre tel que ancetre(A,B) soit satisfait si et seulement si A est une personne ancêtre de B.
Il faut deux clauses :
- Une clause qui concerne la cas où l’ancêtre est un parent direct.
- Une clause récursive qui concerne l’autre cas.
ancetre(A,B) :- parent(A,B).
ancetre(A,B) :- parent(..... , .....), ancetre(..... , .....).
ancetre(A,B) :- parent(A,B).
ancetre(A,B) :- parent(P,B), ancetre(A,P).
Donnez le but permettant de rechercher tous les ancêtre de la personne numéro 12.
ancetre(A,12).
Donnez un but permettant de rechercher une personne dont les deux parents biologiques ont au moins un ancêtre commun.
ancetre(A,P1), ancetre(A,P2), P1<P2, parent(P1,X), parent(P2,X).
C’est la valeur de X qui nous intéresse dans les résultats, qui sont :
A = 1, P1 = 8, P2 = 10, X = 12
A = 2, P1 = 8, P2 = 10, X = 12
Le résultat révèle que les deux parents de la personne 12 ont deux ancêtres communs, qui sont les personnes 1 et 2.
En utilisant la condition P1\==P2 au lieu de P1<P2, on obtient 4 résultats qui désignent tous (de manière redondante) que la personne 12 a deux parents directs ayant les mêmes ancêtres, à savoir les personnes 1 et 2.
Question 4
On définit ainsi la notion d’ancêtre de rang $r$ d’une personne X :
- Les ancêtres de rang 1 de
Xsont ses parents biologiques. - Pour tout $r>1$, toute personne
Pest ancêtre de rang $r$ deXsi et seulement si elle est ancêtre de rang $r-1$ d’un parent direct deX.
Quels sont les ancêtres de rang 2 de la personne numéro 13 ?
Les personnes 3, 4, 6 et 7.
Définissez le prédicat ancetre tel que le but ancetre(A_out,R_out,B_in) permette de rechercher tous les ancêtres d’une personne B_in donnée. Ce prédicat doit être utilisable avec son dernier slot en entrée. Les deux autres slots, utilisés en sortie, permettent de récupérer le numéro et le rang d’un ancêtre de B_in.
Par exemple, le but…
ancetre(A,Rang,9).
…doit produire la réponse…
A = 3, Rang = 1
A = 4, Rang = 1
A = 1, Rang = 2
A = 2, Rang = 2
…qui donne les quatre ancêtres connus de la personne numéro 9 et les rangs correspondants. La personne 3 est ancêtre de rang 1 de la personne 9, etc.
Le prédicat s’écrit en deux clauses :
- La première clause indique simplement qu’un ancêtre de rang 1 est un parent direct.
- La deuxième dit que si une certaine personne
Pest ancêtre de rangNd’un parent direct d’une personneB, alors elle est ancêtre de rangN+1deB.
ancetre(A,1,B) :- parent(A,B).
ancetre(A,R,B) :- .......... .
Détaillons la structure de la deuxième clause :
ancetre(A,R,B) :- % Conclusion
.......... , % Prémisse 1
.......... , % Prémisse 2
.......... . % Prémisse 2
Si
Pest un parent direct deB(Prémisse 1)et si
Aest un ancêtre de rangNdeP(Prémisse 2)et si
RvautN+1(Prémisse 3)alors
Aest un ancêtre de rangRdeB. (Conclusion)
ancetre(A,R,B) :- % Conclusion
parent(P,B), % Prémisse 1
ancetre(A,N,P), % Prémisse 2
R is N+1. % Prémisse 2
Question 5
Donnez un but permettant de rechercher tous les ancêtres de rang au moins égal à deux de la personne 12. Ce but peut comporter plusieurs sous-buts.
ancetre(A,N,12), N>=2.
Donnez le but permettant de rechercher toutes les personnes ayant pour ancêtre la personne 4 et les rangs auxquels ses personnes sont ancêtres de la personne 4. La réponse attendue est :
B = 8, Rang = 1
B = 9, Rang = 1
B = 12, Rang = 2
B = 13, Rang = 2
ancetre(4,Rang,B).
Question 6
Comme pour les questions précédentes, on considère uniquement la base de connaissances suivante :
parent(1,4). parent(1,5). parent(2,4). parent(2,5).
parent(3,8). parent(3,9). parent(4,8). parent(4,9).
parent(5,10). parent(6,10). parent(6,11). parent(7,11).
parent(8,12). parent(10,12). parent(9,13). parent(11,13).
Donnez un but permettant de rechercher toutes les personnes apparaissant dans cette base de connaissance qui n’ont aucun enfant.
parent(_,X), not(parent(X,_)).
Prêt pour la suite ?
Les notions qui ont été introduites dans cette étape permettent de réaliser des choses intéressantes, mais c’est à l’étape suivante (Étape C) que toute la puissance de Prolog va être révélée.
Si vous avez eu des difficultés à traiter certains exercices, si certaines de vos solutions ne correspondaient pas à celles données, je vous conseille de traiter à nouveau ces exercices après au moins une nuit de sommeil et au plus quelques jours.
Si certains points ne sont pas limpides, posez des questions aussi précises que possible à une personne maitrisant parfaitement les notions concernées.
Un petit challenge ?
Je préfère réserver les challenges aux parties suivantes, dans lesquelles nous pourrons utiliser des structures de données telles que des listes et des arbres. Voici toutefois deux problèmes intéressants qui peuvent vous aider à développer votre "pensée Prolog".
Ne traitez ces problème que si vous avez une certaine aisance avec les compétences entrainées dans la section B.ent et que vous souhaitez approfondir ces compétences. Dans le cas contraire, je vous conseille de passer directement à l’étape C.
Les solutions ne sont pas données. Faites des essais sur machine jusqu’à ce que vous parveniez à les trouver vous-même.
B.top1
Vous devez définir un prédicat range permettant de produire les entiers compris entre deux bornes.
Par exemple, le but…
range(3,6,X).
…doit produire le résultat :
X = 3
X = 4
X = 5
X = 6
Un nombre $x$ appartient à l’intervalle $[\text{min}..\text{max}]$ si et seulement si une des deux conditions suivantes est satisfaite :
- $x = \text{min}$
- $\text{max}>\text{min}$ et $x$ appartient à l’intervalle $[\text{min+1}..\text{max}]$
B.top2
On rappelle que les termes de rang 0 et 1 de la suite de Fibonacci ont la valeur 1 et qu’ensuite chaque terme est la somme des deux précédents.
| rang | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| valeur | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
Un des exercices de découverte consistait à définir le prédicat fibo permettant de calculer le terme d’un rang N donné de la suite de Fibonacci.
fibo(0,1).
fibo(1,1).
fibo(N,F) :- N>1, N1 is N-1, N2 is N-2,
fibo(N1,F1), fibo(N2,F2), F is F1+F2.
Ce prédicat est peu efficace car il comporte deux invocations récursives. Par exemple, lors du calcul du terme de rang 7, le calcul du terme de rang 2 est réalisé 8 fois, ce qui n’est pas très raisonnable.
Votre mission, si vous l’acceptez, est de définir un prédicat fibo permettant de calculer, pour un entier $n$ donné en entrée, les termes de rangs $n$ et $n-1$ de la suite de Fibonacci. Par exemple, le but..
fibo(6, P, N)
…doit produire le résultat…
N = 13, P = 8
…parce que le terme de rang 6 est 13 et que le terme précédent est 8.
La définition de ce prédicat doit comporter une seule invocation récursive et non deux comme la variante traitée en exercice de découverte.