{"id":461,"date":"2022-06-22T15:10:14","date_gmt":"2022-06-22T15:10:14","guid":{"rendered":"https:\/\/9h15.net\/activ\/?p=461"},"modified":"2022-06-22T15:12:29","modified_gmt":"2022-06-22T15:12:29","slug":"prolog-etape-b-entrainement","status":"publish","type":"post","link":"https:\/\/9h15.net\/activ\/prolog-etape-b-entrainement\/","title":{"rendered":"PROLOG : \u00e9tape B &#8211; entrainement"},"content":{"rendered":"\n<div class=\"wp-block-jetpack-markdown\"><p><code>Par O. Bailleux, Ma\u00eetre de conf\u00e9rences HDR \u00e0 l'universit\u00e9 de Bourgogne.<\/code><\/p>\n<h1>R\u00e8gles complexes &#8211; entrainement<\/h1>\n<p>Les <strong>activit\u00e9s d&rsquo;entrainement<\/strong> consistent \u00e0 traiter des <strong>exercices d&rsquo;entra\u00eenement<\/strong>. Vous devez d&rsquo;abord tenter de traiter ces exercices sans d\u00e9voiler d&rsquo;indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de d\u00e9couverte ou d&rsquo;entra\u00eenement pr\u00e9c\u00e9demment trait\u00e9s. Si vous avez besoin d&rsquo;indices ou si vos solutions sont erron\u00e9es, analysez les causes de vos erreurs &#8211; au besoin, demandez des explications \u00e0 une personne qualifi\u00e9e &#8211; et refaites les exercices concern\u00e9s apr\u00e8s un d\u00e9lai d&rsquo;au moins une journ\u00e9e et au plus quelques jours.<\/p>\n<h2>Activit\u00e9 d&rsquo;entra\u00eenement B.ent<\/h2>\n<h3>B.ent1<\/h3>\n<p>On travaille avec une base de connaissances repr\u00e9sentant trois types de plats utilisables dans des menus.<\/p>\n<pre><code class=\"language-Prolog\">plat(entree, &quot;p\u00e2t\u00e9&quot;, 200, 6).\nplat(entree, &quot;salade&quot;, 120, 1).\nplat(princ, &quot;poulet frites&quot;, 360, 35).\nplat(princ,&quot; couscous&quot;, 280, 18).\nplat(dessert, &quot;sorbet&quot;, 180, 0).\nplat(dessert, &quot;cake&quot;, 150, 4).\n<\/code><\/pre>\n<p>Les slots du pr\u00e9dicat <code>plat<\/code> repr\u00e9sentent respectivement :<\/p>\n<ul>\n<li>Le type d&rsquo;un plat : <code>entree<\/code> pour une entr\u00e9e, <code>princ<\/code> pour un plat principal, et <code>dessert<\/code> pour un dessert.<\/li>\n<li>Son nom.<\/li>\n<li>Son apport \u00e9nerg\u00e9tique en kilocalories.<\/li>\n<li>Son apport en prot\u00e9ines, exprim\u00e9 en grammes.<\/li>\n<\/ul>\n<p>Vous devez d\u00e9finir un pr\u00e9dicat <code>repas<\/code> permettant de composer un repas avec un nombre maximum donn\u00e9 de kilocalories et une quantit\u00e9 minimum donn\u00e9e de prot\u00e9ines.<\/p>\n<p>Par exemple, le but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">repas(700, 30, E, P, D).\n<\/code><\/pre>\n<p>&#8230;doit produire tous les repas constitu\u00e9s d&rsquo;une entr\u00e9e <code>E<\/code>, d&rsquo;un plat principal <code>P<\/code> et d&rsquo;un dessert <code>D<\/code>, ayant un apport \u00e9nerg\u00e9tique inf\u00e9rieur ou \u00e9gal \u00e0 700 kilocalories et comportant au moins 30 grammes de prot\u00e9ines.<\/p>\n<p>Pour chaque r\u00e9sultat du but, le nom de l&rsquo;entr\u00e9e doit remonter dans la variable de sortie <code>E<\/code>, le nom du plat principal doit remonter dans la variable de sortie <code>P<\/code> et le nom du dessert doit remonter dans la variable de sortie <code>D<\/code>.<\/p>\n<p>Les r\u00e9ponses produites par l&rsquo;\u00e9valuation du but donn\u00e9 en exemple doivent \u00eatre :<\/p>\n<pre><code>D = &quot;sorbet&quot;, E = &quot;salade&quot;, P = &quot;poulet frites&quot;\nD = &quot;cake&quot;, E = &quot;salade&quot;, P = &quot;poulet frites&quot;\n<\/code><\/pre>\n<p>Remarque : pour exprimer que <code>A<\/code> est inf\u00e9rieur ou \u00e9gal \u00e0 <code>B<\/code>, on \u00e9crit <code>A=&lt;B<\/code> et non <code>A&lt;=B<\/code>. Cette syntaxe a pour but d&rsquo;\u00e9viter de confondre l&rsquo;op\u00e9rateur de comparaison avec le symbole d&rsquo;implication logique (bien que ce symbole s&rsquo;\u00e9crive <code>:-<\/code> et non <code>&lt;=<\/code>).<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Ce pr\u00e9dicat peut s&rsquo;\u00e9crire avec une seule clause. Voici une solution partielle \u00e0 compl\u00e9ter :<\/p>\n<pre><code class=\"language-Prolog\">repas(CalMax, ProtMin, E, P, D) :-\n    plat(entree, E, Cal1, Prot1),\n    % \u00c0 compl\u00e9ter\n<\/code><\/pre>\n<p>Le premier but de la clause dit que Le plat de nom <code>E<\/code> est une entr\u00e9e qui apporte <code>Cal1<\/code> kilocalories et <code>Prot1<\/code> grammes de prot\u00e9ines.<\/p>\n<p>Il reste \u00e0 exprimer les deux plat restant (plat principal et dessert), et leurs apports en prot\u00e9ines et kilocalories, puis calculer l&rsquo;apport total en \u00e9nergie et prot\u00e9ines, puis exprimer les contraintes sur la quantit\u00e9 d&rsquo;\u00e9nergie de de calories.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">repas(CalMax, ProtMin, E, P, D) :-\n    plat(entree, E, Cal1, Prot1),\n    plat(princ, P, Cal2, Prot2),\n    plat(dessert, D, Cal3, Prot3),\n    Cal is ....., Prot is .....,\n    % \u00c0 compl\u00e9ter\n<\/code><\/pre>\n<p>Les variables <code>Cal<\/code> et <code>Prot<\/code> permettent de r\u00e9cup\u00e9rer le nombre total de kilocalories et la quantit\u00e9 totale de prot\u00e9ines.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">repas(CalMax, ProtMin, E, P, D) :-\n    plat(entree, E, Cal1, Prot1),\n    plat(princ, P, Cal2, Prot2),\n    plat(dessert, D, Cal3, Prot3),\n    Cal is Cal1+Cal2+Cal3, Prot is Prot1+Prot2+Prot3,\n    Cal=&lt;CalMax, Prot&gt;=ProtMin.\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3>B.ent2<\/h3>\n<p>Le graphe suivant repr\u00e9sente les liens de parent\u00e9 entre plusieurs personnes dont les noms ont \u00e9t\u00e9 remplac\u00e9s par des num\u00e9ros pour des raisons de protection des donn\u00e9es personnelles (RGPD). Une fl\u00e8che d&rsquo;un sommet $A$ vers un sommet $B$ indique que $A$ est le p\u00e8re biologique ou la m\u00e8re biologique de $B$.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/06\/pB3.png\" alt=\"pB3\"><\/p>\n<p>Ces liens de parent\u00e9 directs sont mod\u00e9lis\u00e9s par le pr\u00e9dicat <code>parent<\/code>.<\/p>\n<pre><code class=\"language-Prolog\">parent(1,4). parent(1,5). parent(2,4). parent(2,5).\nparent(3,8). parent(3,9). parent(4,8). parent(4,9).\nparent(5,10). parent(6,10). parent(6,11). parent(7,11).\nparent(8,12). parent(10,12). parent(9,13). parent(11,13).\n<\/code><\/pre>\n<h4>Question 1<\/h4>\n<p>On d\u00e9finit le pr\u00e9dicat <code>siblings<\/code> tel que <code>siblings(A,B)<\/code> est satisfait si et seulement si <code>A<\/code> est le fr\u00e8re ou la soeur de <code>B<\/code> dans le sens o\u00f9 :<\/p>\n<ol>\n<li>il existe deux personnes distinctes qui sont toutes les deux parents directs de <code>A<\/code> et de <code>B<\/code>,<\/li>\n<li><code>A<\/code> et <code>B<\/code> sont deux personnes distinctes (on ne consid\u00e8re pas qu&rsquo;une personne est son propre fr\u00e8re ou sa propre soeur.<\/li>\n<\/ol>\n<pre><code class=\"language-Prolog\">siblings(A,B) :-\n    parent(P1,A), % une personne P1 est p\u00e8re ou m\u00e8re de A\n    parent(P2,B), % une personne P2 est p\u00e8re ou m\u00e8re de B\n    P1\\==P2,      % P1 et P2 sont deux personnes distinctes\n    A\\==B,        % A et B sont deux personnes distinctes\n    parent(P1,B), % P1 est le p\u00e8re ou la m\u00e8re de B\n    parent(P2,A). % P2 est le p\u00e8re ou la m\u00e8re de B \n<\/code><\/pre>\n<p>L&rsquo;ordre dans lequel sont plac\u00e9 les but de la clause peut paraitre \u00e9trange. Il se justifie par les deux crit\u00e8res suivant :<\/p>\n<ol>\n<li>Une condition telle que <code>X\\==Y<\/code> \u00e9choue si au moins l&rsquo;un des deux termes compar\u00e9s est une variable non instanci\u00e9e (n&rsquo;ayant pas de valeur). Pour qu&rsquo;une telle condition soit pertinente, il faut donc qu&rsquo;au moment o\u00f9 elle est \u00e9valu\u00e9e, les deux valeurs \u00e0 comparer soient connues.<\/li>\n<li>Pour des raisons d&rsquo;efficacit\u00e9, on a int\u00e9r\u00eat \u00e0 placer ce genre de condition le plus t\u00f4t possible dans l&rsquo;ordre des buts d&rsquo;une clause car cela limitera la combinatoire de la recherche de solutions.<\/li>\n<\/ol>\n<p>Mais il y a un probl\u00e8me avec ce pr\u00e9dicat. Si on \u00e9value le but&#8230;<\/p>\n<pre><code>siblings(8,S).\n<\/code><\/pre>\n<p>&#8230;on obtient deux fois la m\u00eame r\u00e9ponse :<\/p>\n<pre><code>S = 9\nS = 9\n<\/code><\/pre>\n<p>&#8230;car les deux variable P1 et P2 sont en quelque sorte interchangeables. Le but a \u00e9t\u00e9 satisfait deux fois :<\/p>\n<ul>\n<li>Une fois avec <code>P1=3<\/code> et <code>P2=4<\/code>.<\/li>\n<li>Une fois avec <code>P1=4<\/code> et <code>P2=3<\/code>.<\/li>\n<\/ul>\n<p>Cherchez un moyen d&rsquo;\u00e9viter ce petit probl\u00e8me en modifiant la d\u00e9finition du pr\u00e9dicat. N&rsquo;h\u00e9sitez pas \u00e0 faire des essais sur machine.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>On peut modifier la condition <code>P1\\==P2<\/code> en la rempla\u00e7ant par une autre, plus restrictive, sachant que les valeurs P1 et P2 sont des entiers.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>On remplace <code>P1\\==P2<\/code> par <code>P1&lt;P2<\/code>.<\/p>\n<pre><code class=\"language-Prolog\">siblings(A,B) :-\n    parent(P1,A), parent(P2,A), P1&lt;P2,   \n    parent(P1,B), parent(P2,B), A\\=B.  \n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Question 2<\/h4>\n<p>On \u00e9value le but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">siblings(X,Y).\n<\/code><\/pre>\n<p>&#8230;et on obtient le r\u00e9sultat :<\/p>\n<pre><code>X = 4, Y = 5\nX = 5, Y = 4\nX = 8, Y = 9\nX = 9, Y = 8\n<\/code><\/pre>\n<p>Pourquoi obtient-on deux fois chacune des deux fratries ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Parce-que les r\u00f4les des variables <code>A<\/code> et <code>B<\/code> sont interchangeables et qu&rsquo;il y a donc deux mani\u00e8res de satisfaire le but pour chaque fratrie.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Comment pourrait-on \u00e9viter cette redondance en modifiant le but, sans changer la d\u00e9finition du pr\u00e9dicat ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">siblings(X,Y), X&gt;Y.\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Si on incorporait la nouvelle condition dans la d\u00e9finition du pr\u00e9dicat, cela pourrait-il poser probl\u00e8me pour certains buts ? Donnez un exemple.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Si on remplace <code>A\\==B<\/code> par <code>A&lt;B<\/code> dans la clause qui d\u00e9finit le pr\u00e9dicat <code>siblings<\/code>, comme ceci&#8230;<\/p>\n<pre><code class=\"language-Prolog\">siblings(A,B) :-\n    parent(P1,A), parent(P2,B),\n    P1&lt;P2, A&lt;B,\n    parent(P1,B), parent(P2,A).\n<\/code><\/pre>\n<p>&#8230;alors le fonctionnement avec un but tel que&#8230;<\/p>\n<pre><code class=\"language-Prolog\">siblings(X,Y).\n<\/code><\/pre>\n<p>&#8230;sera correct, mais par exemple le but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">siblings(9,S).\n<\/code><\/pre>\n<p>&#8230;va \u00e9chouer car la condition <code>A&lt;B<\/code> impose que la valeur <code>S<\/code> soit le plus petite que 9.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Question 3<\/h4>\n<p>Une personne <code>A<\/code> est un <strong>anc\u00eatre<\/strong> d&rsquo;une personne <code>B<\/code> si et seulement si une des deux propositions suivantes est vraie :<\/p>\n<ol>\n<li><code>A<\/code> est parent direct de <code>B<\/code>.<\/li>\n<li><code>A<\/code> est anc\u00eatre d&rsquo;un parent direct de <code>B<\/code>.<\/li>\n<\/ol>\n<p>D\u00e9finissez le pr\u00e9dicat <code>ancetre<\/code> tel que <code>ancetre(A,B)<\/code> soit satisfait si et seulement si <code>A<\/code> est une personne anc\u00eatre de <code>B<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Il faut deux clauses :<\/p>\n<ul>\n<li>Une clause qui concerne la cas o\u00f9 l&rsquo;anc\u00eatre est un parent direct.<\/li>\n<li>Une clause r\u00e9cursive qui concerne l&rsquo;autre cas.<\/li>\n<\/ul>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">ancetre(A,B) :- parent(A,B).\nancetre(A,B) :- parent(..... , .....), ancetre(..... , .....).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">ancetre(A,B) :- parent(A,B).\nancetre(A,B) :- parent(P,B), ancetre(A,P).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Donnez le but permettant de rechercher tous les anc\u00eatre de la personne num\u00e9ro 12.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">ancetre(A,12).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Donnez un but permettant de rechercher une personne dont les deux parents biologiques ont au moins un anc\u00eatre commun.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">ancetre(A,P1), ancetre(A,P2), P1&lt;P2, parent(P1,X), parent(P2,X).\n<\/code><\/pre>\n<p>C&rsquo;est la valeur de <code>X<\/code> qui nous int\u00e9resse dans les r\u00e9sultats, qui sont :<\/p>\n<pre><code>A = 1, P1 = 8,  P2 = 10, X = 12\nA = 2, P1 = 8,  P2 = 10, X = 12\n<\/code><\/pre>\n<p>Le r\u00e9sultat r\u00e9v\u00e8le que les deux parents de la personne 12 ont deux anc\u00eatres communs, qui sont les personnes 1 et 2.<\/p>\n<p>En utilisant la condition <code>P1\\==P2<\/code> au lieu de <code>P1&lt;P2<\/code>, on obtient 4 r\u00e9sultats qui d\u00e9signent tous (de mani\u00e8re redondante) que la personne 12 a deux parents directs ayant les m\u00eames anc\u00eatres, \u00e0 savoir les personnes 1 et 2.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Question 4<\/h4>\n<p>On d\u00e9finit ainsi la notion d&rsquo;anc\u00eatre de rang $r$ d&rsquo;une personne <code>X<\/code> :<\/p>\n<ul>\n<li>Les anc\u00eatres de rang 1 de <code>X<\/code> sont ses parents biologiques.<\/li>\n<li>Pour tout $r&gt;1$, toute personne <code>P<\/code> est anc\u00eatre de rang $r$ de <code>X<\/code> si et seulement si elle est anc\u00eatre de rang $r-1$ d&rsquo;un parent direct de <code>X<\/code>.<\/li>\n<\/ul>\n<p>Quels sont les anc\u00eatres de rang 2 de la personne num\u00e9ro 13 ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Les personnes 3, 4, 6 et 7.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>D\u00e9finissez le pr\u00e9dicat <code>ancetre<\/code> tel que le but <code>ancetre(A_out,R_out,B_in)<\/code> permette de rechercher tous les anc\u00eatres d&rsquo;une personne <code>B_in<\/code> donn\u00e9e. Ce pr\u00e9dicat doit \u00eatre utilisable avec son dernier slot en entr\u00e9e. Les deux autres slots, utilis\u00e9s en sortie, permettent de r\u00e9cup\u00e9rer le num\u00e9ro et le rang d&rsquo;un anc\u00eatre de <code>B_in<\/code>.<\/p>\n<p>Par exemple, le but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">ancetre(A,Rang,9).\n<\/code><\/pre>\n<p>&#8230;doit produire la r\u00e9ponse&#8230;<\/p>\n<pre><code>A = 3, Rang = 1\nA = 4, Rang = 1\nA = 1, Rang = 2\nA = 2, Rang = 2\n<\/code><\/pre>\n<p>&#8230;qui donne les quatre anc\u00eatres connus de la personne num\u00e9ro 9 et les rangs correspondants. La personne 3 est anc\u00eatre de rang 1 de la personne 9, etc.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Le pr\u00e9dicat s&rsquo;\u00e9crit en deux clauses :<\/p>\n<ul>\n<li>La premi\u00e8re clause indique simplement qu&rsquo;un anc\u00eatre de rang 1 est un parent direct.<\/li>\n<li>La deuxi\u00e8me dit que <strong>si<\/strong> une certaine personne <code>P<\/code> est anc\u00eatre de rang <code>N<\/code> d&rsquo;un parent direct d&rsquo;une personne <code>B<\/code>, <strong>alors<\/strong> elle est anc\u00eatre de rang <code>N+1<\/code> de <code>B<\/code>.<\/li>\n<\/ul>\n<pre><code>ancetre(A,1,B) :- parent(A,B).\nancetre(A,R,B) :- .......... .\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>D\u00e9taillons la structure de la deuxi\u00e8me clause :<\/p>\n<pre><code>ancetre(A,R,B) :- % Conclusion\n    .......... ,  % Pr\u00e9misse 1\n    .......... ,  % Pr\u00e9misse 2\n    .......... .  % Pr\u00e9misse 2\n<\/code><\/pre>\n<blockquote>\n<p><strong>Si<\/strong>  <code>P<\/code> est un parent direct de <code>B<\/code>  (Pr\u00e9misse 1)<\/p>\n<p><strong>et si<\/strong> <code>A<\/code> est un anc\u00eatre de rang <code>N<\/code> de <code>P<\/code>  (Pr\u00e9misse 2)<\/p>\n<p><strong>et si<\/strong> <code>R<\/code> vaut <code>N+1<\/code> (Pr\u00e9misse 3)<\/p>\n<p><strong>alors<\/strong> <code>A<\/code> est un anc\u00eatre de rang <code>R<\/code> de <code>B<\/code>. (Conclusion)<\/p>\n<\/blockquote>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">ancetre(A,R,B) :-   % Conclusion\n    parent(P,B),    % Pr\u00e9misse 1\n    ancetre(A,N,P), % Pr\u00e9misse 2\n    R is N+1.       % Pr\u00e9misse 2\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Question 5<\/h4>\n<p>Donnez un but permettant de rechercher tous les anc\u00eatres de rang au moins \u00e9gal \u00e0 deux de la personne 12. Ce but peut comporter plusieurs sous-buts.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">ancetre(A,N,12), N&gt;=2.\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Donnez le but permettant de rechercher toutes les personnes ayant pour anc\u00eatre la personne 4 et les rangs auxquels ses personnes sont anc\u00eatres de la personne 4. La r\u00e9ponse attendue est :<\/p>\n<pre><code>B = 8, Rang = 1\nB = 9, Rang = 1\nB = 12, Rang = 2\nB = 13, Rang = 2\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">ancetre(4,Rang,B).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Question 6<\/h4>\n<p>Comme pour les questions pr\u00e9c\u00e9dentes, on consid\u00e8re uniquement la base de connaissances suivante :<\/p>\n<pre><code class=\"language-Prolog\">parent(1,4). parent(1,5). parent(2,4). parent(2,5).\nparent(3,8). parent(3,9). parent(4,8). parent(4,9).\nparent(5,10). parent(6,10). parent(6,11). parent(7,11).\nparent(8,12). parent(10,12). parent(9,13). parent(11,13).\n<\/code><\/pre>\n<p>Donnez un but permettant de rechercher toutes les personnes apparaissant dans cette base de connaissance qui n&rsquo;ont aucun enfant.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">parent(_,X), not(parent(X,_)).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h2>Pr\u00eat pour la suite ?<\/h2>\n<p>Les notions qui ont \u00e9t\u00e9 introduites dans cette \u00e9tape permettent de r\u00e9aliser des choses int\u00e9ressantes, mais c&rsquo;est \u00e0 l&rsquo;\u00e9tape suivante (\u00c9tape C) que toute la puissance de Prolog va \u00eatre r\u00e9v\u00e9l\u00e9e.<\/p>\n<p>Si vous avez eu des difficult\u00e9s \u00e0 traiter certains exercices, si certaines de vos solutions ne correspondaient pas \u00e0 celles donn\u00e9es, je vous conseille de traiter \u00e0 nouveau ces exercices apr\u00e8s au moins une nuit de sommeil et au plus quelques jours.<\/p>\n<p>Si certains points ne sont pas limpides, posez des questions aussi pr\u00e9cises que possible \u00e0 une personne maitrisant parfaitement les notions concern\u00e9es.<\/p>\n<hr>\n<h2>Un petit challenge ?<\/h2>\n<p>Je pr\u00e9f\u00e8re r\u00e9server les challenges aux parties suivantes, dans lesquelles nous pourrons utiliser des structures de donn\u00e9es telles que des listes et des arbres. Voici toutefois deux probl\u00e8mes int\u00e9ressants qui peuvent vous aider \u00e0 d\u00e9velopper votre &quot;pens\u00e9e Prolog&quot;.<\/p>\n<p>Ne traitez ces probl\u00e8me que si vous avez une certaine aisance avec les comp\u00e9tences entrain\u00e9es dans la section <strong>B.ent<\/strong> et que vous souhaitez approfondir ces comp\u00e9tences. Dans le cas contraire, je vous conseille de passer directement \u00e0 l&rsquo;<strong>\u00e9tape C<\/strong>.<\/p>\n<p>Les solutions ne sont pas donn\u00e9es. Faites des essais sur machine jusqu&rsquo;\u00e0 ce que vous parveniez \u00e0 les trouver vous-m\u00eame.<\/p>\n<h3>B.top1<\/h3>\n<p>Vous devez d\u00e9finir un pr\u00e9dicat <code>range<\/code> permettant de produire les entiers compris entre deux bornes.<\/p>\n<p>Par exemple, le but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">range(3,6,X).\n<\/code><\/pre>\n<p>&#8230;doit produire le r\u00e9sultat :<\/p>\n<pre><code>X = 3\nX = 4\nX = 5\nX = 6\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Un nombre $x$ appartient \u00e0 l&rsquo;intervalle $[\\text{min}..\\text{max}]$ si et seulement si une des deux conditions suivantes est satisfaite :<\/p>\n<ol>\n<li>$x = \\text{min}$<\/li>\n<li>$\\text{max}&gt;\\text{min}$ et $x$ appartient \u00e0 l&rsquo;intervalle $[\\text{min+1}..\\text{max}]$<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<h3>B.top2<\/h3>\n<p>On rappelle que les termes de rang 0 et 1 de la suite de Fibonacci ont la valeur 1 et qu&rsquo;ensuite chaque terme est la somme des deux pr\u00e9c\u00e9dents.<\/p>\n<table>\n<thead>\n<tr>\n<th>rang<\/th>\n<th>0<\/th>\n<th>1<\/th>\n<th>2<\/th>\n<th>3<\/th>\n<th>4<\/th>\n<th>5<\/th>\n<th>6<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>valeur<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>2<\/td>\n<td>3<\/td>\n<td>5<\/td>\n<td>8<\/td>\n<td>13<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Un des exercices de d\u00e9couverte consistait \u00e0 d\u00e9finir le pr\u00e9dicat <code>fibo<\/code> permettant de calculer le terme d&rsquo;un rang <code>N<\/code> donn\u00e9 de la suite de Fibonacci.<\/p>\n<pre><code class=\"language-Prolog\">fibo(0,1).\nfibo(1,1).\nfibo(N,F) :- N&gt;1, N1 is N-1, N2 is N-2, \n    fibo(N1,F1), fibo(N2,F2), F is F1+F2.\n<\/code><\/pre>\n<p>Ce pr\u00e9dicat est peu efficace car il comporte deux invocations r\u00e9cursives. Par exemple, lors du calcul du terme de rang 7, le calcul du terme de rang 2 est r\u00e9alis\u00e9 8 fois, ce qui n&rsquo;est pas tr\u00e8s raisonnable.<\/p>\n<p>Votre mission, si vous l&rsquo;acceptez, est de d\u00e9finir un pr\u00e9dicat <code>fibo<\/code> permettant de calculer, pour un entier $n$ donn\u00e9 en entr\u00e9e,  les termes de rangs $n$ et $n-1$ de la suite de Fibonacci. Par exemple, le but..<\/p>\n<pre><code class=\"language-Prolog\">fibo(6, P, N)\n<\/code><\/pre>\n<p>&#8230;doit produire le r\u00e9sultat&#8230;<\/p>\n<pre><code>N = 13, P = 8\n<\/code><\/pre>\n<p>&#8230;parce que le terme de rang 6 est 13 et que le terme pr\u00e9c\u00e9dent est 8.<\/p>\n<p>La d\u00e9finition de ce pr\u00e9dicat doit comporter <strong>une seule invocation r\u00e9cursive<\/strong> et non deux comme la variante trait\u00e9e en exercice de d\u00e9couverte.<\/p>\n<hr>\n<\/div>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[6],"tags":[],"class_list":["post-461","post","type-post","status-publish","format-standard","hentry","category-prolog","entry"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/461","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/comments?post=461"}],"version-history":[{"count":2,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/461\/revisions"}],"predecessor-version":[{"id":463,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/461\/revisions\/463"}],"wp:attachment":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/media?parent=461"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/categories?post=461"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/tags?post=461"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}