Option Prolog

Licence Informatique
Année 2000-2001
UNSA Option Prolog
Correction du TD3 : Les Listes Exercice 1 :
(a) Il faut décomposer la liste donnée comme dans l'exemple du paragraphe
sur la construction des listes, et placer le deuxième élément dans la liste
résultat.
elements-pair(X.Y.U, Y.L) :- elements-pairs(U, L).
elements-pair(nil, nil).
Lancement :
elements-pairs(0.1.2.3.4.5.nil, L).
(b) On utilise une liste auxiliaire sur laquelle on dépile successivement
les éléments qui composeront la liste finale.
pairs-inverses (X.Y.U, M, L) :- pairs-inverses(U, Y.M, L).
pairs-inverses(nil, L, L).
Lancement :
pairs-inverses(0.1.2.3.4.5.nil, nil, L). Exercice 2 :
En traitant les éléments deux par deux, on arrivera finalement à une liste
de la forme X.nil, où X est le dernier élément de la liste donnée. Il est
de rang impair, il ne faut donc pas le retenir. Seuls les deux règles
d'arrêt sont à modifier et deviennent :
elements-pairs(X.nil, nil).
elements-pairs(X.nil, L, L).
Les lancements restent identiques, mais les listes ont des tailles
impaires. Exercice 3 :
On accède directement aux premiers éléments de U et de V qui servent à
construire le début de la liste résultat, l'appel récursif se fait sur les
listes restantes. En outre fusionner deux listes vides donne la liste vide.
fusionner(X.Y, S.T, X.S.L) :- fusionner(Y. T. L).
fusionner(nil, nil, nil).
Lancement :
fusionner(0.1.2.3.nil, 4.5.6.7.nil, L).
Pour obtenir les listes de rang pair et impair, il suffit de lancer le
programme avec la liste L connue, et les listes U et V inconnues.
Lancement :
fusionner(U, V, 0.4.1.5.2.6.3.7.nil).
Exercice 4 :
Tant qu'on dépile les éléments, on réserve la réponse. Si on découvre
l'élément cherché, la réponse est vrai, si on arrive à la fin de la liste,
la réponse est faux.
element-de(X, nil, faux).
element-de(X, X,L, vrai).
element-de(X, U.L, R) :- dif(X, U), element-de(X, L, R).
Cette version de element-de est importante car elle permet dans certains
cas d'éviter l'apparition d'un slash dans une règle. Considérons le schéma
de travail suivant : pour résoudre un problème, si X est élément d'une
liste L, il faut appliquer traitement1, sinon, il faut appliquer
traitement2. C'est-à-dire :
R1 : resoudre(X, L, ...) :- element-de(X, L), traitement1(...).
R2 : resoudre(X, L, ...) :- traitement2(...).
Si X est élément de L, traitement1 s'effectuera, mais lors de la remontée,
traitement2 sera lancé, ce qui constitue une faute. On modifie alors R1 en
écrivant :
R1 : resoudre(x, L, ...) :- element-de(X, L), /, traitement1(...).
On supprime ainsi la remontée. On peut cependant éviter le slash en
utilisant la nouvelle version de element-de de la manière suivante :
resoudre(X, L, ...) :- element-de(X, L, R), suite-resoudre(R, ...).
suite-resoudre(vrai, ...) :- traitement1(...).
suite-resoudre(faux, ...) :- traitement2(...).
On en trouvera une illustration dans l'exercice 8. Exercice 5 :
hors-de(X, U.L) :- dif(X, U), hors-de(X, L).
hors-de(X, nil). Exercice 6 :
differents(X.L) :- hors-de(X, L) differents(L).
differents(nil). Exercice 7 :
Il suffit de verifier que chacun des elements de U appartient à V, ce qui
s'ecrit :
contenue-de(X.L, V) :- element-de(X, V), contenue(L, V).
contenue(nil, V).
Le lancement par
contenue(L, ``a``.``b``.``c``.``d``.``e``.nil).
provoquera la construction de listes infinies {``a``.``a``. ...}
Le lancement par :
contenue(``a``.``b``.nil, L).
provoquera la construction d'une inifinité de listes :
{ L = ``a``.``b``.X}
{ L = ``a``.X.``b``.Y}
{ L = ``a``.X.Y.``b``.Z} ... Exercice 8 :
Il suffit de remarquer que la concaténation de U et V donne L.
debut-et-fin(U, L, V) :- concatener(U, V, L). Exercice 9 :
a) Intersection de deux ensembles : un élément de U appartient à L s'il
appartient à V.
intersection(X.M, V, X.L) :- element-de(X, V), /, intersection(M, V,
L).
intersection(X.M, V, L) :- intersection(M, V, L).
intersection(nil, L, nil).
On peut éviter le slash au moyen de hors-de :
intersection(X.M, V, X.L) :- element-de(X, V), intersection(M, V, L).
intersection(X.M, V, L) :- hors-de(X, V), intersection(M, V, L).
intersection(nil, L, nil).
Autre solution en utilisant element-de qui repond vrai ou faux :
intersection(X.M, V, L) :- element-de(X, V, R), suite-inter(R, X, M,
V, L).
intersection(nil, L, nil).
suite-inter(vrai, X, M, V, X.L) :- intersection(M, V, L).
suite-inter(faux, X, M, V, L) :- intersection(M, V, L). (b)Réunion de deux ensembles : la réunion de U et de V est composée des
éléments de V et des éléments de U qui ne sont pas dans V.
reunion(X.M, V, X.L) :- hors-de(X, V), /, reunion(M, V, L).
reunion(X.M, V, L) :- reunion(M, V, L).
reunion(nil, L, L).
On évite le slash au moyen de solutions analogues à celles du (a) :
reunion(X.M, V, X.L) :- hors-de(X, V), reunion(M, V, L).
reunion(X.M, V, L) :- element-de(X, V), reunion(M, V, L).
reunion(nil, L, L).
Et encore :
reunion(X.M, V, L) :- element-de(X, V, R), suite-reunion(R, X, M, V,
L).
reunion(nil, L, L).
suite-reunion(vrai, X, M, V, L) :- reunion(M, V, L).
suite-reunion(faux, X, M, V, X.L) :- reunion(M, V, L). Exercice 10 :
chemin(X, Y, L) :- chemin-sans-boucle(X, Y, X.nil, L).
chemin-sans-boucle(X, Y, L, Y.L) :- fleche(X, Y).
chemin-sans-boucle(X, Y, M, L) :- fleche(X, Z), hors-de(Z, M),
chemin-sans-boucle(Z, Y, Z.M, L).
chemin-sans-boucle a pour troisième paramètre la liste (construite à
l'envers) des sommets déjà parcourus. Au départ cette liste vaut X.nil,
elle ne contient que le point d'origine du chemin cherché. Par la suite,
chaque fois qu'un nouveau sommet est envisagé, on vérifie qu'il est hors de
cette liste. Lorsqu'une flèche existe entre les deux sommets considérés, il
y a passage final de cette liste partielle pour constituer la liste finale
(sans oublier l'ajout du sommet final). Exercice 11 :
Première solution :
On simule réellement le jeu en n'ajoutant les dominos qu'en tête ou
en queue de la suite. On commence par placer le premier domino dans une
liste auxiliaire A initialement vide, puis on tente d'ajouter un domino de
L en tête de la suite A. On relance alors la boucle avec les nouvelles
valeurs M et B de L et A. En cas d'échec la même tentative est faite en fin
de la suite. Lorsqu'il n'y a plus de dominos à placer, le résultat
s'obtient par passage final de paramètre. Pour ajouter on considère les
deux possibilités pour le premier domino et, en cas d'échec, on passe au
suivant. Voici le programme :
aligner(X.L, nil, R) :- aligner(L, X.nil, R).
aligner(L, A, R) :- ajouter-en-tete(L, A, M, B), aligner(M, B,
R).
aligner(L, A, R) :- ajouter-en-queue(L, A, M, B), aligner(M, B,
R).
aligner(nil, R, R).
ajouter-en-tete((X.Y).L, (Y.Z).A, L, (X.Y).(Y.Z).A).
ajouter-en-tete((X.Y).L, (X.Z).A, L, (Y.X).(X.Z).A).
ajouter-en-tete(D.L, A, D.M, B) :- ajouter-en-tete(L, A, M, B).
ajouter-en-queue((X.Y).L, A, L, B) :- concatener(U, (Z.X).nil,
A),
concatener(A, (X.Y).nil, B) .
ajouter-en-queue((X.Y).L, A, L, B) :- concatener(U, (Z.Y).nil,
A),
concatener(A, (Y.X).nil, B).
ajouter-en-queue(D.L, A, D.M, B) :- ajouter-en-queue(L, A, M,
B).
On lance ce programme par l'effacement du but :
aligner((1.4).(1.5).(2.3).(2.5).(3.4).(3.6).(4.6).(6.6).nil, nil, R).
La même solution peut être construite de plusieurs façons distinctes. b) Deuxième solution :
Le programme précédent a plusieurs défauts. On a confié aux règles
ajouter la double tâche de placer un domino lorsque c'est possible, et de
lancer d'autres tentatives lorsque c'est impossible, d'où une grande
confusion à la lecture. En outre la présence de quatre concaténations
n'est guère rassurante. Nous allons lui apporter deux améliorations.
Il est préférable de conserver en permanence les numéros de début et de
fin de la liste construite pour effectuer les placements à coup sûr (je
vous laisse le soin de modifier le programme précédent dans ce sens).
Nous allons en outre utiliser un procédé indique au cours des exercices :
la liste auxiliaire commencera et se terminera par la même variable.
Après deux coups elle aura par exemple la structure U.(1.4).(4.6).U.
Alors si on prend U = (6.6).V , la liste devient :
((6.6).V).(1.4).(4.6).(6.6).V
En relançant avec V.(1.4).(4.6).(6.6).V , on a ajouté (6.6) à la fin et
on retrouve la même structure de liste. Pour terminer on prendra V = nil.
Dans aligner le premier argument constitue la liste des dominos à placer,
I et J les numéros de début et de fin de la suite construite, puis vient
la liste auxiliaire avec sa structure particulière et le résultat. Si la
suite commence par le numéro I, on retire le domino (I.K) ou le domino
(K.I) de la liste des dominos à placer, et on relance avec K comme numéro
de tête et (K.I) au début de A. Le placement en fin de liste repose sur
le même principe.
aligner(L, I, J, U.A, R) :- retirer(L, I, K, M), aligner(M, K, J,
U.(K.I).A, R).
aligner(L, I, J, ((J.K).V).A, R) :- retirer(L, J, K, M), aligner(M, I,
K, V.A, R).
aligner(nil, I, J, nil.R, R).
retirer((I.K).L, I, K, L).
retirer((K.I).L, I, K, L).
retirer(X.L, I, K, X.M) :- retirer(L, I, K, M).