Esercizi proposti

(1)

Esercizi proposti

1. Implementare il proprio “albero genealogico” e definire le principali rela- zioni di parentela.

2. Scrivere un programma per calcolare il perimetro di alcune figure piane. Il programma deve contenere la definizione di un predicato perimetro(P,F), che significa che P `e il perimetro della figura F. Ad esempio,

perimetro(20,rettangolo(4,6)) deve essere dimostrabile. Il program- ma deve essere in grado di gestire triangoli, cerchi, quadrati e rettangoli.

3. Scrivere una procedura per il calcolo del fattoriale di un numero naturale.

4. Implementare l’algoritmo di Euclide per il calcolo del massimo comun divisore di due numeri.

5. Scrivere un programma che risolva il problema delle torri di Hanoi (usare il predicato write per l’output su video delle mosse eseguite).

6. Nella terminologia del Prolog, “testa” si riferisce a due diversi concetti.

Quali?

7. Implementare tutte le principali relazioni che coinvolgono liste: member, length, reverse, delete (cancellazione di tutte le occorrenze di un ele- mento), delete first (cancellazione della prima occorrenza di un elemen- to), subst (sostituzione di tutte le occorrenze di un elemento con un altro), ....

8. Avendo definito il predicato pari(X) :- 0 is X mod 2.

definire un predicato split(L,P,D) che, data una lista L di interi, riporti le due liste P e D, dove P contiene tutti gli elementi pari di L e D tutti i dispari.

9. Definire un predicato a un argomento, palindroma(X), vero se X è una lista palindroma (se la lista viene letta in un verso o nell’altro si ottiene la stessa sequenza di elementi). Ad esempio [a,b,c,b,a] è palindroma, [a,b,c,a] non lo è.

10. Scrivere una procedura che definisce un predicato a due argomenti prefisso(X,Y), vero se X `e un prefisso di Y. Ad esempio, [1,2,3] `e un prefisso di [1,2,3,4,5].

11. Scrivere una procedura che definisce un predicato a due argomenti suffisso(X,Y), vero se X `e un suffisso di Y. Ad esempio, [1,2,3] `e un suffisso di [4,5,1,2,3].

12. Definire una relazione sublist tale che sublist(S,L) vale se S `e una sottolista di L (cio`e una sequenza di elementi contigui in L).

1

(2)

13. Diciamo che X occorre in Y se X=Y, oppure Y `e una lista e X `e un elemento di Y oppure X occorre in qualche elemento di Y.

(a) Definire un predicato occurs in(X,Y) vero se X occorre in Y.

(b) Definire un predicato flat(X,Y) che riporta in Y tutti i termini (atomi o strutture) che occorrono in Y.

14. Definire un predicato depth(X,N) vero se N `e la profondit`a del termine X.

15. Scrivere una procedura che, dati due insiemi rappresentati mediante liste, ne costruisca il prodotto cartesiano.

16. Definire una relazione insert tale che insert(X,L1,L2) vale se L2 risulta dall’inserimento di X in L1 (in qualsiasi posizione).

17. Definire un predicato permut(X,Y) vero se Y `e una permutazione di X.

18. Definire una relazione listmap a tre argomenti, tale che, se P `e un atomo:

listmap(P,[x

₁

,...,x

ⁿ

],[y

₁

,...,y

^m

]) vale se n = m e per ogni i vale P(x

ⁱ

,y

ⁱ

).

Suggerimento: utilizzare il predicato Univ per costruire il termine P(x

ⁱ

,y

ⁱ

).

19. Si consideri la procedura seguente permut([],[]).

permut([H|T],Y) :- permut(T,Z), append(Z1,Z2,Z), append(Z1,[H|Z2],Y).

La ricerca di tutte le soluzioni della query ?- permut([a,b],X) termina, ma non se la query `e ?- permut(X,[a,b]).

Spiegare questo fatto.

20. Definire un predicato sorted che vale per una lista di interi se e solo se la lista `e ordinata. Usando sorted e permutation, definire una relazione sort tale che sort(L,S) vale se S contiene gli stessi elementi di L ed `e ordinata.

21. Si implementino l’insertion sort, il quick sort e il merge sort in Prolog.

22. Definire le principali relazioni insimistiche (subset, intersection, union, list2set, disjoint, setdiff, ...)

23. Si risolva il problema di determinare un sottoinsieme S

₁

di un insieme S di interi non negativi, tali che la somma degli elmenti di S

₁

sia uguale a un intero dato N .

2

(3)

24. Una sostituzione si pu` o rappresentare mediante una lista della forma [t1/x1,...,tn/xn], dove le x sono atomi e le t sono termini. Defini- re un predicato che rappresenti l’applicazione di una sostituzione a un termine e un predicato che rappresenti la composizione di sostituzioni.

Implementare l’algoritmo di unificazione di Robinson.

25. Sia data la rappresentazione di un grafo con stati iniziali, mediante un insieme di fatti. Ad esempio:

initial(0).

initial(1).

delta(0,1).

delta(1,2).

delta(1,3).

delta(0,3).

delta(3,4).

delta(3,5).

delta(4,5).

delta(5,3).

Scrivere una procedura che ricerchi nel grafo un ciclo raggiungibile da uno stato iniziale e riporti, se esiste, una rappresentazione del corrispondente cammino “ultimately periodic”. Tale cammino pu` o essere rappresentato da una coppia di liste: la prima rappresenta il cammino dallo stato iniziale all’inizio del ciclo, la seconda la parte ciclica. Ad esempio, nel grafo dato, la coppia ([0,1,2],[3,4,5]) rappresenta il cammino 0, 1, 2, (3, 4, 5)

^ω

. 26. Sia V un insieme di variabili di stato e C un insieme di costanti, disgiunto

da V . Rappresentiamo gli elementi di entrambi gli insiemi mediante atomi.

Rappresentiamo uno stato mediante una lista di elementi della forma x=e, dove x `e una variabile di stato e e un valore costituito da una costante o un numero intero.

Ad esempio, se V = {x, y, pcl, pcr} e l1, r1 ∈ C, la lista [x=2, y=3, pcl=l1, pcr=r1] rappresenta uno stato.

(a) Si considerino semplici espressioni della forma c, e1+e2, e1*e2, e1/e2, e1-e2, dove c è una costante e le sottoespressioni e1, e2 sono costituite da variabili di stato o numeri interi, o sono a loro volta espressioni. Definire un predicato valore a tre argomenti, tale che valore(S,E,V) è vero se il valore dell’espressione E nello stato rappresentato dalla lista S è V. V deve essere una costante o un intero.

(b) Si considerino semplici espressioni della forma v=e, not(v=e), v>e, e1+e2, v>=e, v=<e dove v è una variabile di stato e e, e1, e2 sono espressioni. Definire un predicato vera a due argomenti, tale che vera(E,S) è vero se E (un’espressione della forma sopra descritta) è vera nello stato S.

3

(4)

(c) Si estenda la definizione del predicato valore a espressioni della forma if(e,e1,e2).

(d) Definire una procedura che, dato uno stato S, una lista di variabili Vars e una lista di espressioni Vals (della stessa lunghezza di Vars), costruisca lo stato che si ottiene da S modificando i valori in Vars, assegnandogli i valori che hanno in S le rispettive espressioni in Vals.

(e) Definire un operatore := (per rappresentare le assegnazioni di una transizione), scrivere un insieme di clausole che rappresenti l’insieme delle transizioni di un sistema e un insieme di clausole che rappresenti gli stati iniziali del sistema, e scrivere un programma che generi e stampi tutti gli stati raggiungibili da stati iniziali, la relazione di transizione e trovi, se ve ne sono, gli stati finali.

(f) Generalizzare il programma precedente in modo che legga in input il nome di un file in cui sono definite transizioni e stati iniziali del sistema.

27. Si determini un modo di rappresentare formule della logica proposizionale classica, definendo gli operatori opportuni.

(a) Definire un predicato a due argomenti nnf(X,Y) che, data una for- mula X, costruisca in Y la sua forma normale negativa.

(b) Scrivere un programma che, data una formula e un’interpretazione rappresentata come insieme di atomi, determini se la formula `e vera nell’interpretazione.

(c) Scrivere un programma che, data una lista di formule Formlist, de- termini se Formlist `e soddisfacibile o no, applicando il metodo dei tableaux. Se Formlist `e soddisfacibile, il programma riporter` a un modello di Formlist, rappresentato come lista di atomi.

28. Si determini un modo di rappresentare formule della logica temporale lineare, definendo gli operatori opportuni.

(a) Scrivere un programma che, data una formula F, applichi la defini- zione di verit` a di F in un’interpretazione stampando tutti i passaggi fino ai casi base.

(b) Si determini un modo di rappresentare un’interpretazione ciclica del- la logica temporale lineare (eventualmente attraverso clausole del programma) e scrivere un programma che, data una formula F e un’interpretazione, determini se F `e vera o falsa nell’interpretazione.

4