Esercizio 7.1			Esercizio 7.2
		Esercizio 7.3			Esercizio 7.4
		Esercizio 7.5			Esercizio 7.6
		Esercizio 7.7			Esercizio 7.8
		Esercizio 7.9

		Esercizio 7.1

Scrivere, utilizzando la rappresentazione simbolica dei numeri interi, due procedure Prolog per il calcolo della divisione intera (parte intera e resto), ossia le due procedure:

div(N,M,INT) INT è la parte intera della divisione tra N e M

mod(N,M,INT) INT è il resto della divisione tra N e M

SOLUZIONE

somma(X,0,X).
somma(X,s(Y),s(Z)) :- somma(X,Y,Z).

minore(0,s(_)).
minore(s(A),s(B)) :- minore(A,B).

div(N,M,0) :- minore(N,M).
div(N,M,s(INT)) :- somma(N1,M,N),
div(N1,M,INT).

mod(N,M,N) :- minore(N,M).
mod(N,M,INT) :- somma(N1,M,N),
mod(N1,M,INT).

		Esercizio 7.2

Scrivere un programma Prolog per il calcolo di una funzione mediante minimizzazione limitata, ossia data la funzione calcolabile f(x,y) scrivere una procedura Prolog per il calcolo della funzione:

h(x,z)	= m y <= z (f(x,y)=0)	se y esiste
	= indefinita	altrimenti.

SOLUZIONE

f(_,3,0):- !.
f(_,5,0):- !.
f(_,7,0):- !.
f(_,_,1).

h(X,Z,Y) :- h1(X,0,Z,Y).

h1(X,B,Z,B) :- B =< Z, f(X,B,0).
h1(X,B,Z,Y) :- B =< Z, B1 is B+1, h1(X,B1,Z,Y).
h1(_,_,_,undef).

		Esercizio 7.3

Si supponga di avere a disposizione un linguaggio logico senza aritmetica floating-point. Si determini una rappresentazione per i numeri reali (ad esempio come coppie di numeri interi che rappresentano rispettivamente la parte intera e quella decimale) e si scrivano delle procedure Prolog per le operazioni di somma, prodotto, differenza e divisione.

SOLUZIONE

ricomponi((S,D,I),X) :-
X is (1000*D+I)*S.

scomponi((1,D,I),X) :-
X >= 0,
D is X // 1000,
I is X mod 1000.
scomponi((-1,D,I),X) :-
X < 0,
XX is -X,
scomponi((_,D,I),XX).

somma(A,B,C) :-
ricomponi(A,AA),
ricomponi(B,BB),
CC is AA+BB,
scomponi(C,CC).

diff(A,B,C) :-
ricomponi(A,AA),
ricomponi(B,BB),
CC is AA-BB,
scomponi(C,CC).

prod(A,B,C) :-
ricomponi(A,AA),
ricomponi(B,BB),
CC is AA*BB/1000,
scomponi(C,CC).

divis(A,B,C) :-
ricomponi(A,AA),
ricomponi(B,BB),
CC is (AA*1000)//BB,
scomponi(C,CC).

		Esercizio 7.4

Si realizzi in Prolog l'aritmetica dei numeri complessi.

SOLUZIONE La rappresentazione usata vede un numero complesso come coppia (parte reale, parte immaginaria).

somma((A,B),(C,D),(E,F)):-
E is A+C,
F is B+D.

diff((A,B),(C,D),(E,F)):-
E is A-C,
F is B-D.

prod((A,B),(C,D),(E,F)) :-
E is A*C-B*D,
F is B*C+A*D.

divis((A,B),(C,D),(E,F)) :-
DEN is C*C+D*D,
E is (A*C+B*D)/DEN,
F is (B*C+A*D)/DEN.

		Esercizio 7.5

Si scrivano le procedure Prolog per il calcolo delle seguenti funzioni:

SOLUZIONE

% Versione ricorsiva della funzione f.

f(0,0).
f(N,Y) :-
N > 0,
N1 is N-1,
f(N1,Y1),
Y is Y1+N*N.

% Versione iterativa della funzione f.

fIT(N,Y) :- fIT(N,0,Y).

fIT(0,ACC,ACC).
fIT(N,ACC,Y) :-
N > 0,
ACC1 is ACC+N*N,
N1 is N-1,
fIT(N1,ACC1,Y).

% Versione ricorsiva della funzione g.

g(0,0).
g(N,Y) :-
N > 0,
s(N,Y1),
N1 is N-1,
g(N1,Y2),
Y is Y1+Y2.

s(I,Y) :- potenza(I,2,Y1),
h(I,Y2),
Y is Y1*Y2.

h(I,I).

potenza(_,0,1).
potenza(X,K,Y) :- K > 0,
K1 is K-1,
potenza(X,K1,Y1),
Y is Y1*X.

% Versione iterativa della funzione g.

gIT(N,Y) :- gIT(N,0,Y).

gIT(0,ACC,ACC).
gIT(N,ACC,Y) :-
N > 0,
s(N,Y1),
ACC1 is ACC+Y1,
N1 is N-1,
gIT(N1,ACC1,Y).

		Esercizio 7.6

Si scriva la procedura Prolog per il calcolo della seguente funzione:

(n k)= n*(n-1)*....*(n-k+1) / k!

si ottimizzi (se possibile) il programma.

SOLUZIONE

binom(N,K,Y) :-
START is N-K+1,
produttoria(START,N,NUM),
produttoria(1,K,DEN),
Y is NUM/DEN.

produttoria(START,END,Y) :-
START =< END,
produttoria(START,END,1,Y).

produttoria(START,START,ACC,Y) :-
Y is ACC*START.
produttoria(START,END,ACC,Y) :-
START < END,
ACC1 is ACC*END,
END1 is END-1,
produttoria(START,END1,ACC1,Y).

		Esercizio 7.7

Scrivere una procedura più efficiente per il calcolo dei numeri di Fibonacci.

SOLUZIONE

fib(0,0).
fib(1,1).
fib(N,Y) :-
N > 1,
COUNT is N-1,
fib1(COUNT,1,0,Y).

fib1(0,ACC,_,ACC).
fib1(COUNT,ACC,R2,Y) :-
COUNT1 is COUNT-1,
ACC1 is ACC+R2,
fib1(COUNT1,ACC1,ACC,Y).

		Esercizio 7.8

Scrivere una procedura Prolog per il calcolo della funzione di Ackermann. La definizione della funzione è la seguente:

ackermann(0,n) = n+1
ackermann(m,0) = ackermann(m-1,1)
ackermann(m,n) = ackermann(m-1, ackermann(m, n-1))

SOLUZIONE

ack(0,N,Y) :-
Y is N+1.
ack(M,0,Y) :-
M1 is M-1,
ack(M1,1,Y).
ack(M,N,Y) :-
N1 is N-1,
ack(M,N1,Y1),
M1 is M-1,
ack(M1,Y1,Y).

		Esercizio 7.9

Si disegni lo stack relativo all'esecuzione della chiamata fatt1(3,N) dove fatt1/2 è definito dal programma (7.5). Si mostri poi come lo si può ridurre mediante ottimizzazione tail.

SOLUZIONE