Devoirs Hebdomadaire N°7
CDL...DH7

Prolog I

M. Joseph DASSE BRIKA

Soient les opérations d'addition, de soustraction, de multiplication et de division entière en Prolog sur les entiers naturels spécifiées par :  

nat(zero).  
nat(s(N)) :- nat(N).

%addition : a/3 : on dit  A plus B d'où
a(A,zero,A) :- nat(A).   % A + 0 = A
a(A,s(B),s(S)):- a(A , B , S).  % A + (B+1) = A+B + 1 = S+1

%soustraction : s/3 : si B > A la soustraction n'a pas de sens...
s(A,B,S) :- ie(s(A) , B) , a(S,B,A).

%multiplication : m/3 : on dit  A multiplié B d'où
m(A,zero , zero) :- nat(A). % A *  0 = 0
m(A,s(zero), A) :- nat(A). % A *  1 = A
m(A,s(s(B)), P) :- m(A,s(B),W), a(W,A,P).

%la division entière : d/3 on dit  A divisé par B d'où
d(A,B , Q) :- d4(A,B , Q,_).  % on ne s'intéresse qu'au quotien

%d4/4
d4(A,B , zero,A) :- ie(s(A),B).
d4(A,B , s(Q),R) :- ie(B,A),
s(A,B , NA),
d4(NA,B , Q,R).

%prédicat : inférieur ou égal : ie/2
ie(zero,N) :- nat(N).
ie(s(A) , s(B)) :- ie(A,B).

On veut "optimiser" l'addition et la multiplication en se fondant sur les remarques : "on ajoute le plus petit au plus grand"  (pour A+B si A<B on calcule en fait B+A) et "on multiplie le plus grand par le plus petit "(pour A*B  si A<B on calcule en fait B*A)

QUESTION 1 : introduire ces "optimisations" dans la spécification des prédicats aOPTI/3  et mOPTI/3 utilisant les prédicats a/3 et m/3 ci dessus et donner un exemple d'exécution pour chacun d'eux.

Les entiers naturels relatifs : On définit Z les entiers relatifs comme des entiers naturels ( s(s(...(zero)...)) ) signés. Par exemple  z(+ , s(s(zero))) ou bien z(- , s(s(zero))). Ce prédicat z/2 , spécifié ci dessous, permet aussi de vérifier si un nombre est un entier relatif :

z(+ , Valeur) :- nat(Valeur).
z(-  , Valeur) :- nat(Valeur).   

Remarque :  le 0 est noté indifféremment : z(+ , zero) ou z(- , zero)

QUESTION 2 :

Spécifier en Prolog les 4 opérations addition (aZ/3), soustraction (sZ/3), multiplication (mZ/3) et division entière (dZ/3) sur les entiers relatifs en utilisant les prédicats sur les "nat" de la question 1 et les règles classiques sur les signes (+,-) et donner un exemple pour chaque opération.

%addition : a/3 : on dit  A plus B
a(A,zero,A) :- nat(A).
a(A,s(B),s(S)) :- a(A,B,S) .

%addition : a/3 : on dit  A plus B
aOPTI(A,zero,A) :- nat(A).
aOPTI(A,B,S) :- ie(s(A) , B) , a(B,A,S) .
aOPTI(A,B,S) :- ie(B,A) , a(A,B,S) .

%soustraction : s/3 : si B > A la soustraction n'a pas de sens...
s(A,B,S) :- ie(B,A) , a(S,B,A).

%multiplication : m/3 : on dit  A multiplié B d'où
m(A,zero,zero) :- nat(A) .  % A *  0 = A
m(A,s(zero), A) :- nat(A).  % A *  1 = A
m(A,s(s(B)), P) :- m(A,s(B),W), a(W,A,P).

%multiplication : m/3 : on dit  A multiplié B d'où
mOPTI(A,zero,zero) :- nat(A) .  % A *  0 = A
mOPTI(A,s(zero), A) :- nat(A).  % A *  1 = A
mOPTI(A,B, P) :- ie(s(A),B) , m(B,A,P).
mOPTI(A,B, P) :- ie(B,A)  , m(A,B,P).

%la division entière : d/3 on dit  A divisé par B d'où
d(A,B , Q) :- d4(A,B , Q,_).

   d4(A,B, zero,A) :- ie(s(A) , B).
   d4(A,B , s(Q),R) :- ie(B,A),
   s(A,B , NA),
   d4(NA,B , Q,R).
     
ie(zero,N) :- nat(N).
ie(s(A) , s(B)) :- ie(A,B).

nat(zero).
nat(s(N)) :- nat(N).

Question 2

z(+ , N) :- nat(N).
z(- , N) :- nat(N).

aZ(z(S,A) , z(S,B) , z(S,C)) :- a(A,B,C).
aZ(z(+,A) , z(-,A) , z(+,zero)) :- nat(A).
aZ(z(-,A) , z(+,A) , z(+,zero)) :- nat(A).
aZ(z(+,A) , z(-,B) , z(+,C)) :- ie(s(B) , A) , a(B,C,A).
aZ(z(+,A) , z(-,B) , z(-,C)) :- ie(s(A) , B) , aOPTI(B,C,A).
aZ(z(-,A) , z(+,B) , z(-,C)) :- ie(s(B) , A) , aOPTI(A,C,B).
aZ(z(-,A) , z(+,B) , z(-,C)) :- ie(s(A) , B) , a(A,C,B).

sZ(z(+,A) , z(-,B) , z(+,C)) :- aOPTI(A,B,C).
sZ(z(-,A) , z(+,B) , z(-,C)) :- aOPTI(A,B,C).
sZ(z(S,A) , z(S,B) , z(S,C)) :- a(B,C,A).

mZ(z(S1,A) , z(S2,B) , z(S3,C)) :- regleSignes(S1,S2,S3) , mOPTI(A,B,C).
regleSignes(+,+,+).
regleSignes(+,-,-).
regleSignes(-,+,-).
regleSignes(-,-,+).

dZ(z(S1,A) , z(S2,B) , z(S3,C)) :- regleSignes(S1,S2,S3) , d(A,B,C).

?- dZ(z(+ , s(s(s(s(s(s(s(zero)))))))) ,z(- , s(s(s(zero)))) , Q).

Q = z(-, s(s(zero))) ;

No

FIN_dh7

ACCUEIL CONTACT FAVORIS ANNALES DH1 DH2 DH3 DH4 DH5 DH6 DH7 DH8 DH9 DH10 DH11 DH12 DH13 DH14 DH15 DH16