{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"toc": "true"
},
"source": [
"# Table of Contents\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TP 8 - Programmation pour la préparation à l'agrégation maths option info\n",
"TP 8 : Programmation logique"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- En Prolog. En fait, dans une version maison de Prolog.\n",
"- Les cellules de codes suivantes sont exécutées par un shell, ici Bash."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"## Introduction\n",
"\n",
"Je vous ai envoyé un fichier `prolog.zip`, voyons comment l'extraire et construire l'interpréteur prolog."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"-rw-r--r-- 1 lilian lilian 3,3K mars 16 17:13 \u001b[0m\u001b[38;5;40mprolog.zip\u001b[0m\n",
"Archive: prolog.zip\n",
"Zip file size: 3348 bytes, number of entries: 7\n",
"drwxr-xr-x 3.0 unx 0 bx stor 18-Mar-16 17:13 prolog/\n",
"-rw-r--r-- 3.0 unx 2668 tx defX 17-Aug-28 16:34 prolog/lib.ml\n",
"-rw-r--r-- 3.0 unx 2489 tx defX 17-Aug-28 16:34 prolog/resolution.ml\n",
"-rw-r--r-- 3.0 unx 256 tx defX 17-Aug-28 16:34 prolog/prolog.ml\n",
"-rw-r--r-- 3.0 unx 42 tx defX 17-Aug-28 16:34 prolog/pair.pl\n",
"-rw-r--r-- 3.0 unx 310 tx defX 17-Aug-28 16:34 prolog/Makefile\n",
"-rw-r--r-- 3.0 unx 223 tx defX 17-Aug-28 16:34 prolog/nat.pl\n",
"7 files, 5988 bytes uncompressed, 2234 bytes compressed: 62.7%\n"
]
}
],
"source": [
"ls -larth prolog.zip\n",
"zipinfo prolog.zip"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Archive: prolog.zip\n",
" creating: prolog/\n",
" inflating: prolog/lib.ml \n",
" inflating: prolog/resolution.ml \n",
" inflating: prolog/prolog.ml \n",
" inflating: prolog/pair.pl \n",
" inflating: prolog/Makefile \n",
" inflating: prolog/nat.pl \n"
]
}
],
"source": [
"unzip prolog.zip"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[0m\u001b[0mlib.ml\u001b[0m \u001b[38;5;155mMakefile\u001b[0m \u001b[38;5;208mnat.pl\u001b[0m \u001b[38;5;208mpair.pl\u001b[0m \u001b[0mprolog.ml\u001b[0m \u001b[0mresolution.ml\u001b[0m\n"
]
}
],
"source": [
"ls prolog/"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vous \u001b[01;31mquittez\u001b[01;37m le dossier \u001b[01;33m'/home/lilian/agreg-2017/PROG/tp8'\u001b[01;37m.\n",
"\t/!\\ Chemin \u001b[01;31mrelatif\u001b[01;37m, car le vrai est \u001b[01;34m'/home/lilian/teach/teachensren/AGREG/2017_2018/PROG/tp8'\u001b[01;37m.\n",
"\tDirection ==> \u001b[01;32mprolog/\u001b[01;37m\n"
]
}
],
"source": [
"cd prolog/"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Allons construire `prolog` :"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"rm -f *.cm[iox] *~ prolog mytop\n",
"ocamlc -pp camlp4o -c lib.ml\n",
"\u001b[0;39;49mocamlc on \u001b[4m\u001b[01;30m-pp camlp4o -c lib.ml\u001b[0;39;49m\n",
"ocamlc lib.cmo -c resolution.ml\n",
"\u001b[0;39;49mocamlc on \u001b[4m\u001b[01;30mlib.cmo -c resolution.ml\u001b[0;39;49m\n",
"\u001b[01;35m\u001b[KFile\u001b[m\u001b[K \u001b[02;34m\u001b[K\"resolution.ml\"\u001b[m\u001b[K, \u001b[05;01;31m\u001b[Kline 97\u001b[m\u001b[K, \u001b[01;31m\u001b[Kcharacters 9-14:\u001b[m\u001b[K\n",
"\u001b[05;01;33m\u001b[KWarning 52: Code should not depend on the actual values of\u001b[m\u001b[K\n",
"this constructor's arguments. They are only for information\n",
"and may change in future versions. (See manual section 8.5)\n",
"ocamlc -o prolog lib.cmo resolution.cmo prolog.ml\n",
"\u001b[0;39;49mocamlc on \u001b[4m\u001b[01;30m-o prolog lib.cmo resolution.cmo prolog.ml\u001b[0;39;49m\n",
"'lib.cmi' supprimé\n",
"'lib.cmo' supprimé\n",
"'prolog.cmi' supprimé\n",
"'prolog.cmo' supprimé\n",
"'resolution.cmi' supprimé\n",
"'resolution.cmo' supprimé\n",
"'lib.annot' supprimé\n",
"'prolog.annot' supprimé\n",
"'resolution.annot' supprimé\n"
]
}
],
"source": [
"/usr/bin/make clean\n",
"/usr/bin/make\n",
"rm -f *.cm[iox] *.annot"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Le binaire `prolog` ainsi construit est un exécutable OCaml. (pas natif, mais peu importe)"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vous \u001b[01;31mquittez\u001b[01;37m le dossier \u001b[01;33m'/home/lilian/agreg-2017/PROG/tp8/prolog'\u001b[01;37m.\n",
"\t/!\\ Chemin \u001b[01;31mrelatif\u001b[01;37m, car le vrai est \u001b[01;34m'/home/lilian/teach/teachensren/AGREG/2017_2018/PROG/tp8/prolog'\u001b[01;37m.\n",
"\tDirection ==> \u001b[01;32m..\u001b[01;37m\n",
"\u001b[0m\u001b[38;5;208;1mprolog/prolog\u001b[0m*\n",
"prolog/prolog: a /home/lilian/.opam/4.04.2/bin/ocamlrun script executable (binary data)\n"
]
}
],
"source": [
"cd ..\n",
"ls prolog/prolog\n",
"file prolog/prolog"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Je vous ai aussi envoyé `exemples.zip` :"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"-rw-rw-r-- 1 lilian lilian 1,5K mars 16 17:17 \u001b[0m\u001b[38;5;40mexemples.zip\u001b[0m\n",
"Archive: exemples.zip\n",
"Zip file size: 1525 bytes, number of entries: 5\n",
"drwxr-xr-x 3.0 unx 0 bx stor 17-Aug-28 16:39 exemples/\n",
"-rw-r--r-- 3.0 unx 539 tx defX 17-Aug-28 16:34 exemples/domino.pl\n",
"-rw-r--r-- 3.0 unx 358 tx defX 17-Aug-28 16:34 exemples/genealogie.pl\n",
"-rw-r--r-- 3.0 unx 774 tx defX 17-Aug-28 16:34 exemples/famille.pl\n",
"-rw-r--r-- 3.0 unx 250 tx defX 17-Aug-28 16:34 exemples/lapin.pl\n",
"5 files, 1921 bytes uncompressed, 693 bytes compressed: 63.9%\n"
]
}
],
"source": [
"ls -larth exemples.zip\n",
"zipinfo exemples.zip"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Archive: exemples.zip\n",
" creating: exemples/\n",
" inflating: exemples/domino.pl \n",
" inflating: exemples/genealogie.pl \n",
" inflating: exemples/famille.pl \n",
" inflating: exemples/lapin.pl \n"
]
}
],
"source": [
"unzip exemples.zip"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"-rw-r--r-- 1 lilian lilian 250 août 28 2017 \u001b[0m\u001b[38;5;208mexemples/lapin.pl\u001b[0m\n",
"-rw-r--r-- 1 lilian lilian 358 août 28 2017 \u001b[38;5;208mexemples/genealogie.pl\u001b[0m\n",
"-rw-r--r-- 1 lilian lilian 774 août 28 2017 \u001b[38;5;208mexemples/famille.pl\u001b[0m\n",
"-rw-r--r-- 1 lilian lilian 539 août 28 2017 \u001b[38;5;208mexemples/domino.pl\u001b[0m\n"
]
}
],
"source": [
"ls -larth exemples/*.pl"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Par exemple :"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"blanc(jeannot).\n",
"grandesOreilles(jeannot).\n",
"blanc(Y) <-- enfant(jeannot,Y).\n",
"enfant(X,filsAuYeuxBleus(X)) <-- grandesOreilles(X),dentsNonCaries(X).\n",
"yeuxBleus(filsAuYeuxBleus(X)) <-- grandesOreilles(X),dentsNonCaries(X).\n",
"dentsNonCaries(X) <-- blanc(X).\n",
"\n"
]
}
],
"source": [
"cat exemples/lapin.pl"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Premier exemple\n",
"\n",
"`pair.pl` définit les entiers pairs."
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vous \u001b[01;31mquittez\u001b[01;37m le dossier \u001b[01;33m'/home/lilian/agreg-2017/PROG/tp8'\u001b[01;37m.\n",
"\t/!\\ Chemin \u001b[01;31mrelatif\u001b[01;37m, car le vrai est \u001b[01;34m'/home/lilian/teach/teachensren/AGREG/2017_2018/PROG/tp8'\u001b[01;37m.\n",
"\tDirection ==> \u001b[01;32mprolog\u001b[01;37m\n"
]
}
],
"source": [
"cd prolog"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"pair(o).\n",
"pair(s(s(X))) <-- pair(X).\n",
"\n",
" \n"
]
}
],
"source": [
"cat pair.pl"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"J'ai modifié le programme `prolog` pour qu'il accepte une requête comme dernier argument après le fichier :"
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- pair(o).\n",
" { }\n"
]
}
],
"source": [
"./prolog pair.pl \"pair(o).\" # une valuation vide : c'est axiomatiquement vrai !"
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- pair(s(o)).\n"
]
}
],
"source": [
"./prolog pair.pl \"pair(s(o)).\" # aucune valuation : c'est faux !"
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- pair(s(s(o))).\n",
" { }\n"
]
}
],
"source": [
"./prolog pair.pl \"pair(s(s(o))).\" # une valuation vide : c'est vrai !"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Vous pouvez expérimenter dans votre terminal, en faisant simplement `./prolog pair.pl` et en tapant les requêtes.\n",
"Je recommande l'utilisation de [rlwrap](https://github.com/hanslub42/rlwrap) ou [ledit](https://opam.ocaml.org/packages/ledit/) pour faciliter l'édition (mais je peux pas montrer ça dans un notebook)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Second exemple"
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- infEq(s(s(o)), s(s(s(o)))).\n",
" { }\n"
]
}
],
"source": [
"./prolog nat.pl \"infEq(s(s(o)), s(s(s(o)))).\" # 2 <= 3 ? oui"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- infEq(s(s(s(s(o)))), s(s(s(o)))).\n"
]
}
],
"source": [
"./prolog nat.pl \"infEq(s(s(s(s(o)))), s(s(s(o)))).\" # 4 <= 3 ? non"
]
},
{
"cell_type": "code",
"execution_count": 81,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- plus(o,s(o),s(o)).\n",
" { }\n"
]
}
],
"source": [
"./prolog nat.pl \"plus(o,s(o),s(o)).\" # 0+1 = 1 ? Oui"
]
},
{
"cell_type": "code",
"execution_count": 79,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- plus(s(o),s(o),s(s(o))).\n",
" { }\n"
]
}
],
"source": [
"./prolog nat.pl \"plus(s(o),s(o),s(s(o))).\" # 1+1 = 2 ? Oui"
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- plus(s(o),o,s(s(o))).\n"
]
}
],
"source": [
"./prolog nat.pl \"plus(s(o),o,s(s(o))).\" # 1+1 = 1 ? Non"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"## Vos premiers programmes logiques"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Prédicat `impair`"
]
},
{
"cell_type": "code",
"execution_count": 82,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"pair(o).\n",
"pair(s(s(X))) <-- pair(X).\n"
]
}
],
"source": [
"cat pair.pl"
]
},
{
"cell_type": "code",
"execution_count": 83,
"metadata": {},
"outputs": [],
"source": [
"echo \"impair(s(o)).\" > impair.pl\n",
"echo \"impair(s(s(X))) <-- impair(X).\" >> impair"
]
},
{
"cell_type": "code",
"execution_count": 84,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- impair(o).\n",
"?- impair(s(o)).\n",
" { }\n",
"?- impair(s(s(o))).\n"
]
}
],
"source": [
"./prolog impair.pl \"impair(o).\" # faux\n",
"./prolog impair.pl \"impair(s(o)).\" # vrai\n",
"./prolog impair.pl \"impair(s(s(o))).\" # faux"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Famille"
]
},
{
"cell_type": "code",
"execution_count": 172,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"'famille.pl' supprimé\n"
]
}
],
"source": [
"rm -vf famille.pl"
]
},
{
"cell_type": "code",
"execution_count": 173,
"metadata": {},
"outputs": [],
"source": [
"echo \"parent(cyrill, renaud).\" >> famille.pl\n",
"echo \"parent(cyrill, claire).\" >> famille.pl\n",
"echo \"parent(renaud, clovis).\" >> famille.pl\n",
"echo \"parent(valentin, olivier).\" >> famille.pl\n",
"echo \"parent(claire, olivier).\" >> famille.pl\n",
"echo \"parent(renaud, claudia).\" >> famille.pl\n",
"echo \"parent(claire, gaelle).\" >> famille.pl"
]
},
{
"cell_type": "code",
"execution_count": 174,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- parent(cyrill, renaud).\n",
" { }\n",
"?- parent(claire, renaud).\n"
]
}
],
"source": [
"./prolog famille.pl \"parent(cyrill, renaud).\" # vrai\n",
"./prolog famille.pl \"parent(claire, renaud).\" # faux"
]
},
{
"cell_type": "code",
"execution_count": 175,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- parent(X, renaud).\n",
" { X = cyrill }\n",
"?- parent(X, gaelle).\n",
" { X = claire }\n",
"?- parent(X, olivier).\n",
" { X = valentin }\n",
" { X = claire }\n",
"?- parent(renaud, X).\n",
" { X = clovis }\n",
" { X = claudia }\n",
"?- parent(gaelle, X).\n",
"?- parent(olivier, X).\n"
]
}
],
"source": [
"./prolog famille.pl \"parent(X, renaud).\" # cyrill\n",
"./prolog famille.pl \"parent(X, gaelle).\" # claire\n",
"./prolog famille.pl \"parent(X, olivier).\" # claire, valentin\n",
"\n",
"./prolog famille.pl \"parent(renaud, X).\" # clovis, claudia\n",
"./prolog famille.pl \"parent(gaelle, X).\" # {}\n",
"./prolog famille.pl \"parent(olivier, X).\" # {}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On définit les frères et sœurs comme ayant un parent en commun, et les cousin-es comme ayant un grand-parent en commun :"
]
},
{
"cell_type": "code",
"execution_count": 176,
"metadata": {},
"outputs": [],
"source": [
"echo \"freresoeur(X,Y) <-- parent(Z,X), parent(Z,Y).\" >> famille.pl\n",
"echo \"grandparent(X,Y) <-- parent(X,Z), parent(Z,Y).\" >> famille.pl\n",
"echo \"cousin(X,Y) <-- grandparent(Z,X), grandparent(Z,Y).\" >> famille.pl"
]
},
{
"cell_type": "code",
"execution_count": 177,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- freresoeur(cyrill, claire).\n",
"?- freresoeur(renaud, claire).\n",
" { }\n",
"?- freresoeur(claire, claire).\n",
" { }\n",
"?- grandparent(X,olivier).\n",
" { X = cyrill }\n",
"?- grandparent(X,gaelle).\n",
" { X = cyrill }\n"
]
}
],
"source": [
"./prolog famille.pl \"freresoeur(cyrill, claire).\" # faux\n",
"./prolog famille.pl \"freresoeur(renaud, claire).\" # vrai\n",
"./prolog famille.pl \"freresoeur(claire, claire).\" # vrai\n",
"\n",
"./prolog famille.pl \"grandparent(X,olivier).\" # cyrill\n",
"./prolog famille.pl \"grandparent(X,gaelle).\" # cyrill"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A vous de trouver une définition récursive de ce prédicat `ancetre` qui fonctionne comme on le souhaite."
]
},
{
"cell_type": "code",
"execution_count": 178,
"metadata": {},
"outputs": [],
"source": [
"#echo \"ancetre(X,Y) <-- ancetre(X,Z), grandparent(Z,Y).\" >> famille.pl\n",
"echo \"ancetre(X,Y) <-- parent(X,Y).\" >> famille.pl\n",
"echo \"ancetre(X,Y) <-- grandparent(X,Y).\" >> famille.pl\n",
"#echo \"ancetre(X,X).\" >> famille.pl"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On peut vérifier tous les axiomes et règles qu'on a ajouté :"
]
},
{
"cell_type": "code",
"execution_count": 179,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"parent(cyrill, renaud).\n",
"parent(cyrill, claire).\n",
"parent(renaud, clovis).\n",
"parent(valentin, olivier).\n",
"parent(claire, olivier).\n",
"parent(renaud, claudia).\n",
"parent(claire, gaelle).\n",
"freresoeur(X,Y) <-- parent(Z,X), parent(Z,Y).\n",
"grandparent(X,Y) <-- parent(X,Z), parent(Z,Y).\n",
"cousin(X,Y) <-- grandparent(Z,X), grandparent(Z,Y).\n",
"ancetre(X,Y) <-- parent(X,Y).\n",
"ancetre(X,Y) <-- grandparent(X,Y).\n"
]
}
],
"source": [
"cat famille.pl"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Questions :"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Les ancêtres d'Olivier sont Valentin, Claire et Cyrill :"
]
},
{
"cell_type": "code",
"execution_count": 180,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- parent(X,olivier).\n",
" { X = valentin }\n",
" { X = claire }\n",
"?- grandparent(X,olivier).\n",
" { X = cyrill }\n"
]
}
],
"source": [
"./prolog famille.pl \"parent(X,olivier).\"\n",
"./prolog famille.pl \"grandparent(X,olivier).\"\n"
]
},
{
"cell_type": "code",
"execution_count": 181,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- ancetre(X,olivier).\n",
" { X = valentin }\n",
" { X = claire }\n",
" { X = cyrill }\n"
]
}
],
"source": [
"./prolog famille.pl \"ancetre(X,olivier).\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- L'ancêtre commun d'Olivier et Renaud est Cyrill :"
]
},
{
"cell_type": "code",
"execution_count": 182,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- ancetre(olivier,X),ancetre(renaud,X).\n"
]
}
],
"source": [
"./prolog famille.pl \"ancetre(olivier,X),ancetre(renaud,X).\""
]
},
{
"cell_type": "code",
"execution_count": 183,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- ancetre(X,olivier),ancetre(X,renaud).\n",
" { X = cyrill }\n"
]
}
],
"source": [
"./prolog famille.pl \"ancetre(X,olivier),ancetre(X,renaud).\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Claudia et Gaëlle ne sont pas sœurs, mais elles sont cousines :"
]
},
{
"cell_type": "code",
"execution_count": 149,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- freresoeur(gaelle,claudia).\n",
"?- cousin(gaelle,claudia).\n",
" { }\n"
]
}
],
"source": [
"./prolog famille.pl \"freresoeur(gaelle,claudia).\" # faux\n",
"./prolog famille.pl \"cousin(gaelle,claudia).\" # vrai"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Claudia est la sœur de Clovis, et Olivier et Gaëlle sont ces cousins :"
]
},
{
"cell_type": "code",
"execution_count": 147,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- freresoeur(X,clovis).\n",
" { X = clovis }\n",
" { X = claudia }\n",
"?- cousin(X,clovis).\n",
" { X = clovis }\n",
" { X = claudia }\n",
" { X = olivier }\n",
" { X = gaelle }\n"
]
}
],
"source": [
"./prolog famille.pl \"freresoeur(X,clovis).\"\n",
"./prolog famille.pl \"cousin(X,clovis).\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"## Listes\n",
"\n",
"Je donne la correction complète directement, ce petit exercice n'aurait pas dû poser de problème :"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vous \u001b[01;33mquittez\u001b[01;37m le dossier \u001b[01;34m'/home/lilian/teach/teachensren/AGREG/2017_2018/PROG/tp8'\u001b[01;37m.\n",
"\tDirection ==> \u001b[01;32mexemples\u001b[01;37m\n"
]
},
{
"ename": "",
"evalue": "1",
"output_type": "error",
"traceback": []
}
],
"source": [
"cd exemples"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"liste(nil).\n",
"liste(cons(X, Y)) <-- liste(Y).\n",
"\n",
"dernier(X, cons(X, L)).\n",
"avant_dernier(Y, cons(X, cons(Y, L))).\n",
"\n",
"taille(o, nil).\n",
"taille(s(K), cons(X, L)) <-- taille(K, L).\n",
"\n",
"element_numero(X, o, cons(X, L)).\n",
"element_numero(X, s(K), cons(Y, L)) <-- element_numero(X, K, L).\n",
"\n",
"dupliquer(nil, nil).\n",
"dupliquer(cons(X, cons(X, L2)), cons(X, L)) <-- dupliquer(L2, L).\n"
]
}
],
"source": [
"cat listes.pl"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On vérifie que l'on sait tester si des listes sont bien des listes :"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- liste(nil).\n",
" { }\n",
"?- liste(cons(toto, nil)).\n",
" { }\n",
"?- liste(pasliste).\n",
"?- liste(cons(zorro, pasliste)).\n"
]
}
],
"source": [
"../prolog/prolog listes.pl \"liste(nil).\" # vrai\n",
"../prolog/prolog listes.pl \"liste(cons(toto, nil)).\" # vrai\n",
"../prolog/prolog listes.pl \"liste(pasliste).\" # faux\n",
"../prolog/prolog listes.pl \"liste(cons(zorro, pasliste)).\" # faux"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Maintenant on vérifie qu'on peut accéder au dernier et avant-dernier élément d'une liste :"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- dernier(X, nil).\n",
"?- dernier(X, cons(toto, nil)).\n",
" { X = toto }\n",
"?- avant_dernier(X, cons(zorro, cons(toto, nil))).\n",
" { X = toto }\n",
"?- avant_dernier(X, cons(titeuf, cons(zorro, cons(toto, nil)))).\n",
" { X = zorro }\n"
]
}
],
"source": [
"../prolog/prolog listes.pl \"dernier(X, nil).\" # {} aucune solution !\n",
"../prolog/prolog listes.pl \"dernier(X, cons(toto, nil)).\" # X = toto\n",
"../prolog/prolog listes.pl \"avant_dernier(X, cons(zorro, cons(toto, nil))).\" # X = toto\n",
"../prolog/prolog listes.pl \"avant_dernier(X, cons(titeuf, cons(zorro, cons(toto, nil)))).\" # X = zorro"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On peut calculer la taille d'une liste (en *unaire*) :"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- taille(K, nil).\n",
" { K = o }\n",
"?- taille(K, cons(toto, nil)).\n",
" { K = s(o) }\n",
"?- taille(K, cons(zorro, cons(toto, nil))).\n",
" { K = s(s(o)) }\n",
"?- taille(K, cons(titeuf, cons(zorro, cons(toto, nil)))).\n",
" { K = s(s(s(o))) }\n"
]
}
],
"source": [
"../prolog/prolog listes.pl \"taille(K, nil).\" # K = o\n",
"../prolog/prolog listes.pl \"taille(K, cons(toto, nil)).\" # K = s(o)\n",
"../prolog/prolog listes.pl \"taille(K, cons(zorro, cons(toto, nil))).\" # K = s(s(o))\n",
"../prolog/prolog listes.pl \"taille(K, cons(titeuf, cons(zorro, cons(toto, nil)))).\" # K = s(s(s(o)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On peut accéder au $k$-ième élément aussi :"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- element_numero(X, o, nil).\n",
"?- element_numero(X, o, cons(toto, nil)).\n",
" { X = toto }\n",
"?- element_numero(X, s(o), cons(zorro, cons(toto, nil))).\n",
" { X = toto }\n",
"?- element_numero(X, o, cons(titeuf, cons(zorro, cons(toto, nil)))).\n",
" { X = titeuf }\n"
]
}
],
"source": [
"../prolog/prolog listes.pl \"element_numero(X, o, nil).\" # {} erreur\n",
"../prolog/prolog listes.pl \"element_numero(X, o, cons(toto, nil)).\" # X = toto\n",
"../prolog/prolog listes.pl \"element_numero(X, s(o), cons(zorro, cons(toto, nil))).\" # X = toto\n",
"../prolog/prolog listes.pl \"element_numero(X, o, cons(titeuf, cons(zorro, cons(toto, nil)))).\" # X = titeuf"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On peut accéder au troisième élément d'une liste (s'il existe). Ici la liste est $[1, 2, 3, 4]$ donc le troisième élément (d'indice $2 = s(s(0))$) est $3$ :"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- element_numero(X, s(s(o)), cons(un, cons(deux, cons(trois, cons(quatre, nil))))).\n",
" { X = trois }\n"
]
}
],
"source": [
"../prolog/prolog listes.pl \"element_numero(X, s(s(o)), cons(un, cons(deux, cons(trois, cons(quatre, nil))))).\" # X = titeuf"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Enfin, on peut facilement dupliquer les éléments d'une liste :"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- dupliquer(X, cons(a, cons(b, cons(c, nil)))).\n",
" { X = cons(a,cons(a,cons(b,cons(b,cons(c,cons(c,nil)))))) }\n"
]
}
],
"source": [
"../prolog/prolog listes.pl \"dupliquer(X, cons(a, cons(b, cons(c, nil)))).\" # X = [a, a, b, b, c, c]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"## Problème : dominos"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Cet exercice serait plus simple si on s'autoriser à utiliser la syntaxe de GNU Prolog pour les listes, mais malheureusement on ne l'a pas implémenté dans notre mini prolog.\n",
"\n",
"On va devoir écrire les concaténations de listes avec un prédicat, un peu comme au dessus.\n",
"On utiliser $p(a,b)$ pour les paires, et $c(a,u)$ pour la concaténation."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vous \u001b[01;33mquittez\u001b[01;37m le dossier \u001b[01;34m'/home/lilian/teach/teachensren/AGREG/2017_2018/PROG/tp8'\u001b[01;37m.\n",
"\tDirection ==> \u001b[01;32mexemples\u001b[01;37m\n"
]
}
],
"source": [
"cd exemples"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[ -f dominos.pl ] && rm -vf dominos.pl"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"echo \"est_liste(nil).\" >> dominos.pl\n",
"echo \"est_liste(c(X, L)) <-- est_liste(L).\" >> dominos.pl\n",
"\n",
"echo \"est_paire(p(A, B)).\" >> dominos.pl"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Pour l'enchaînement de dominos, ce n'est pas trop difficile : $[(a,b); (c,d); ...]$ s'enchaîne bien si $b = c$ et si la suite s'enchaîne bien (définition récursive). Les cas de bases sont vrais pour la liste vide et un singleton."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"echo \"enchainement(nil).\" >> dominos.pl\n",
"echo \"enchainement(c(p(A, B), nil)).\" >> dominos.pl\n",
"echo \"enchainement(c(p(Z, X), c(p(X, Y), Q))) <-- enchainement(c(p(X, Y), Q)).\" >> dominos.pl"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- enchainement(nil).\n",
" { }\n",
"?- enchainement(c(p(a, b), nil)).\n",
" { }\n",
"?- enchainement(c(p(a, b), c(p(a, b), nil))).\n",
"?- enchainement(c(p(b, a), c(p(a, b), nil))).\n",
" { }\n"
]
}
],
"source": [
"../prolog/prolog dominos.pl \"enchainement(nil).\" # vrai\n",
"../prolog/prolog dominos.pl \"enchainement(c(p(a, b), nil)).\" # vrai\n",
"../prolog/prolog dominos.pl \"enchainement(c(p(a, b), c(p(a, b), nil))).\" # faux\n",
"../prolog/prolog dominos.pl \"enchainement(c(p(b, a), c(p(a, b), nil))).\" # vrai : b-a a-b s'enchaine bien"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Maintenant l'insertion, qui teste si `l2` peut s'obtenir par une insertion de `x` **quelque part** dans `l1` (et pas uniquement en tête ou en queue de `l1`)."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"echo \"insere(X, L, c(X, L)).\" >> dominos.pl\n",
"echo \"insere(X, c(T, Q1), c(T, Q2)) <-- insere(X, Q1, Q2).\" >> dominos.pl"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On a évidemment $n+1$ possibilités pour insérer `a` si `l1` est de taille $n$ :"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- insere(a, c(b, c(d, nil)), L2).\n",
" { L2 = c(a,c(b,c(d,nil))) }\n",
" { L2 = c(b,c(a,c(d,nil))) }\n",
" { L2 = c(b,c(d,c(a,nil))) }\n"
]
}
],
"source": [
"../prolog/prolog dominos.pl \"insere(a, c(b, c(d, nil)), L2).\" # 2+1 possibilités"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour les permutations, ce n'est pas tellement différent. On teste si $L$ peut être obtenue par permutation depuis $T :: Q$ en testant si $Q$ est obtenue par permutation d'une certaine liste $L_2$ et si $T$ peut être inséré dans $L_2$ pour donner $L$."
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [],
"source": [
"echo \"perm(nil, nil).\" >> dominos.pl\n",
"echo \"perm(L, c(T, Q)) <-- insere(T, L2, L), perm(L2, Q).\" >> dominos.pl"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- perm(c(a,c(b,nil)), X).\n",
" { X = c(a,c(b,nil)) }\n",
" { X = c(b,c(a,nil)) }\n"
]
}
],
"source": [
"../prolog/prolog dominos.pl \"perm(c(a,c(b,nil)), X).\" # [a;b] et [b;a]"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- perm(c(a,c(b,c(d,nil))), X).\n",
" { X = c(a,c(b,c(d,nil))) }\n",
" { X = c(a,c(d,c(b,nil))) }\n",
" { X = c(b,c(a,c(d,nil))) }\n",
" { X = c(b,c(d,c(a,nil))) }\n",
" { X = c(d,c(a,c(b,nil))) }\n",
" { X = c(d,c(b,c(a,nil))) }\n"
]
}
],
"source": [
"../prolog/prolog dominos.pl \"perm(c(a,c(b,c(d,nil))), X).\" # 6 = 3! possibilités, toutes montrées"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour les permutations de $[a;b;c;d]$, on devrait trouver $24=4!$ possibilités :"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- perm(c(u,c(v,c(w,c(x,nil)))), X).\n",
" { X = c(u,c(v,c(w,c(x,nil)))) }\n",
" { X = c(u,c(v,c(x,c(w,nil)))) }\n"
]
}
],
"source": [
"../prolog/prolog dominos.pl \"perm(c(u,c(v,c(w,c(x,nil)))), X).\" # 24 = 4! possibilités, pas toutes montrées ?!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour les arrangements, c'est similaire mais on considère aussi la possibilité d'inverser un domino (*i.e.*, $(a,b) \\mapsto (b,a)$) :"
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {},
"outputs": [],
"source": [
"echo \"miroir(p(A, B), p(B, A)).\" >> dominos.pl"
]
},
{
"cell_type": "code",
"execution_count": 90,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- miroir(p(u,v), X).\n",
" { X = p(v,u) }\n"
]
}
],
"source": [
"../prolog/prolog dominos.pl \"miroir(p(u,v), X).\" # X = p(v,u)"
]
},
{
"cell_type": "code",
"execution_count": 91,
"metadata": {},
"outputs": [],
"source": [
"echo \"arrangement(nil, nil).\" >> dominos.pl\n",
"echo \"arrangement(L, c(T,Q)) <-- insere(T, L2, L), arrangement(L2, Q).\" >> dominos.pl\n",
"echo \"arrangement(L, c(T,Q)) <-- miroir(T2, T), insere(T2, L2, L), arrangement(L2, Q).\" >> dominos.pl"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Les arrangements de petites listes ne donne pas grand chose :"
]
},
{
"cell_type": "code",
"execution_count": 92,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- arrangement(nil, L).\n",
" { L = nil }\n",
"?- arrangement(c(a,nil)), L).\n"
]
}
],
"source": [
"../prolog/prolog dominos.pl \"arrangement(nil, L).\" # L = nil\n",
"../prolog/prolog dominos.pl \"arrangement(c(a,nil)), L).\" # rien"
]
},
{
"cell_type": "code",
"execution_count": 93,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- arrangement(c(a,c(b,nil)), X).\n",
" { X = c(a,c(b,nil)) }\n",
" { X = c(b,c(a,nil)) }\n"
]
}
],
"source": [
"../prolog/prolog dominos.pl \"arrangement(c(a,c(b,nil)), X).\" # X = [a;b] ou [b;a]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Mais avec trois éléments ou plus :"
]
},
{
"cell_type": "code",
"execution_count": 94,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- arrangement(c(a,c(b,c(d,nil))), X).\n",
" { X = c(a,c(b,c(d,nil))) }\n",
" { X = c(a,c(d,c(b,nil))) }\n",
" { X = c(b,c(a,c(d,nil))) }\n",
" { X = c(b,c(d,c(a,nil))) }\n",
" { X = c(d,c(a,c(b,nil))) }\n",
" { X = c(d,c(b,c(a,nil))) }\n"
]
}
],
"source": [
"../prolog/prolog dominos.pl \"arrangement(c(a,c(b,c(d,nil))), X).\" # 6 réponses"
]
},
{
"cell_type": "code",
"execution_count": 96,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- arrangement(c(p(u,v),c(p(w,u),nil)), X).\n",
" { X = c(p(u,v),c(p(w,u),nil)) }\n",
" { X = c(p(u,v),c(p(u,w),nil)) }\n",
" { X = c(p(w,u),c(p(u,v),nil)) }\n",
" { X = c(p(w,u),c(p(v,u),nil)) }\n",
" { X = c(p(v,u),c(p(w,u),nil)) }\n",
" { X = c(p(v,u),c(p(u,w),nil)) }\n",
" { X = c(p(u,w),c(p(u,v),nil)) }\n",
" { X = c(p(u,w),c(p(v,u),nil)) }\n"
]
}
],
"source": [
"# X = [(u,v);(w,u)] ou [(w,u);(u,v)] avec 0 miroir\n",
"# ou X = [(v,u);(w,u)] ou [(w,u);(v,u)] avec 1 miroir sur (u,v)\n",
"# ou X = [(u,v);(u,w)] ou [(u,w);(u,v)] avec 1 miroir sur (w,u)\n",
"# ou X = [(v,u);(u,w)] ou [(u,w);(v,u)] avec 2 miroirs\n",
"../prolog/prolog dominos.pl \"arrangement(c(p(u,v),c(p(w,u),nil)), X).\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Maintenant on peut résoudre le problème, avec $u,v,w,x = 1,2,3,4$."
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {},
"outputs": [],
"source": [
"echo \"quasisolution(L1, L2) <-- perm(L1, L2), enchainement(L2).\" >> dominos.pl\n",
"echo \"solution(L1, L2) <-- arrangement(L1, L2), enchainement(L2).\" >> dominos.pl"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On peut ordonner $[(1,2); (3,1); (2,4)]$ en $[(3,1); (1,2); (2,4)]$ si on ignore les miroirs :"
]
},
{
"cell_type": "code",
"execution_count": 102,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- quasisolution(c(p(un,deux),c(p(trois,un),c(p(deux,quatre),nil))), L).\n",
" { L = c(p(trois,un),c(p(un,deux),c(p(deux,quatre),nil))) }\n"
]
}
],
"source": [
"../prolog/prolog dominos.pl \"quasisolution(c(p(un,deux),c(p(trois,un),c(p(deux,quatre),nil))), L).\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On peut ordonner $[(1,2); (3,1); (2,4)]$ en $[(3,1); (1,2); (2,4)]$ mais aussi en $[(4,2); (2,1); (1,3)]$ car on a le droit de tourner les dominos !"
]
},
{
"cell_type": "code",
"execution_count": 101,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"?- solution(c(p(un,deux),c(p(trois,un),c(p(deux,quatre),nil))), L).\n",
" { L = c(p(trois,un),c(p(un,deux),c(p(deux,quatre),nil))) }\n",
" { L = c(p(quatre,deux),c(p(deux,un),c(p(un,trois),nil))) }\n"
]
}
],
"source": [
"../prolog/prolog dominos.pl \"solution(c(p(un,deux),c(p(trois,un),c(p(deux,quatre),nil))), L).\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"### Comparaison avec GNU Prolog\n",
"La solution avec GNU Prolog serait :"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"enchainement([]).\n",
"enchainement([_]).\n",
"enchainement([ [_, X] | [[X, Y]| Q] ]) :- enchainement([[X, Y]|Q]).\n",
"\n",
"insere(X, L, [X|L]).\n",
"insere(X, [T|Q1], [T|Q2]) :- insere(X, Q1, Q2).\n",
"\n",
"miroir([X, Y], [Y, X]).\n",
"\n",
"perm([], []).\n",
"perm(L, [T|Q]) :- perm(L2, Q), insere(T, L2, L).\n",
"\n",
"assemblage([], []).\n",
"assemblage(L, [T|Q]) :- assemblage(L2, Q), insere(T, L2, L).\n",
"assemblage(L, [T|Q]) :- assemblage(L2, Q), miroir(T2, T), insere(T2, L2, L).\n",
"\n",
"quasisolution(L1, L2) :- perm(L1, L2), enchainement(L1).\n",
"solution(L1, L2) :- assemblage(L1, L2), enchainement(L1).\n"
]
}
],
"source": [
"cat domino.pl"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Il faut la comparer à notre solution, un peu plus verbeuse à cause de l'absence de syntaxe spécifique aux listes et aux paires, mais qui encode la même logique."
]
},
{
"cell_type": "code",
"execution_count": 103,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"est_liste(nil).\n",
"est_liste(c(X, L)) <-- est_liste(L).\n",
"est_paire(p(A, B)).\n",
"\n",
"enchainement(nil).\n",
"enchainement(c(p(A, B), nil)).\n",
"enchainement(c(p(Z, X), c(p(X, Y), Q))) <-- enchainement(c(p(X, Y), Q)).\n",
"\n",
"insere(X, L, c(X, L)).\n",
"insere(X, c(T, Q1), c(T, Q2)) <-- insere(X, Q1, Q2).\n",
"\n",
"perm(nil, nil).\n",
"perm(L, c(T, Q)) <-- insere(T, L2, L), perm(L2, Q).\n",
"\n",
"miroir(p(A, B), p(B, A)).\n",
"\n",
"arrangement(nil, nil).\n",
"arrangement(L, c(T,Q)) <-- insere(T, L2, L), arrangement(L2, Q).\n",
"arrangement(L, c(T,Q)) <-- miroir(T2, T), insere(T2, L2, L), arrangement(L2, Q).\n",
"\n",
"quasisolution(L1, L2) <-- perm(L1, L2), enchainement(L2).\n",
"\n",
"solution(L1, L2) <-- arrangement(L1, L2), enchainement(L2).\n"
]
}
],
"source": [
"cat dominos.pl"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## Conclusion\n",
"\n",
"Fin. C'était le dernier TP.\n",
"\n",
"- Essayez de travailler un peu toutes les notions vues dans les 8 TPs cette année pour vous entraîner aux oraux.\n",
"- Pour le plus grand nombre possible de texte d'annales de modélisations, essayez d'implémenter parfaitement la question de programmation obligatoire, **avec des tests et des exemples**, et essayez de faire un ou deux bonus pour chaque texte."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Bash",
"language": "bash",
"name": "bash"
},
"language_info": {
"codemirror_mode": "shell",
"file_extension": ".sh",
"mimetype": "text/x-sh",
"name": "bash"
},
"toc": {
"colors": {
"hover_highlight": "#DAA520",
"running_highlight": "#FF0000",
"selected_highlight": "#FFD700"
},
"moveMenuLeft": true,
"nav_menu": {
"height": "511px",
"width": "251px"
},
"navigate_menu": true,
"number_sections": true,
"sideBar": true,
"threshold": 4,
"toc_cell": true,
"toc_position": {
"height": "578px",
"left": "0px",
"right": "1288px",
"top": "149px",
"width": "152px"
},
"toc_section_display": "block",
"toc_window_display": false
},
"varInspector": {
"cols": {
"lenName": 16,
"lenType": 16,
"lenVar": 40
},
"kernels_config": {
"python": {
"delete_cmd_postfix": "",
"delete_cmd_prefix": "del ",
"library": "var_list.py",
"varRefreshCmd": "print(var_dic_list())"
},
"r": {
"delete_cmd_postfix": ") ",
"delete_cmd_prefix": "rm(",
"library": "var_list.r",
"varRefreshCmd": "cat(var_dic_list()) "
}
},
"types_to_exclude": [
"module",
"function",
"builtin_function_or_method",
"instance",
"_Feature"
],
"window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}