definire operatori strutture dati fabio massimo zanzotto (slides di andrea turbati)
TRANSCRIPT
![Page 1: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/1.jpg)
Definire operatoriStrutture dati
Fabio Massimo Zanzotto
(slides di Andrea Turbati)
![Page 2: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/2.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Le strutture dati, anche complesse, sono alla base dei vari linguaggi di programmazione
• In Prolog è possibile creare ed utilizzarle in modo palese
Strutture dati
![Page 3: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/3.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Un database può essere rappresentato in Prolog come un elenco di fatti
• Per comprendere come creare/usare le strutture dati in Prolog useremo i seguenti esempi:– Famiglia– Automa non deterministico– Problema delle 8 Regine
Strutture dati
![Page 4: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/4.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Una famiglia può essere rappresentata da un fatto, family, con 3 argomenti:– Padre– Madre– Figli (tramite una lista)
• Gli elementi della famiglia sono delle persone (person), rappresentati a sua volta da dei termini complessi formati da 4 elementi: nome, cognome, data di nascita e salario
Famiglia
![Page 5: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/5.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Rappresentazione della famiglia Smith
• family(person(bob, smith, date(7, may,1968),30000),
person(ann, smith, date(18, july,1970),32000),
[person(dave, smith, date(1, june,1984),0),
person(edna, smith, date(25, may,1990),0)]).
Famiglia
![Page 6: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/6.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Possiamo effettuare varie query, basandoci non solo sui valori ma anche sulla struttura stessa
• family(person(_,fox, _, _), _, _). si riferisce alla famiglia fox, usando solo il cognome del padre e nessun altra informazione
• Esiste un altro modo per riferirsi alla famiglia fox?
Famiglia
![Page 7: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/7.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• family(_, _, [_,_,_]). Indica una famiglia con 3 figli
• Come si può indicare una famiglia con almeno 3 figli ?
• Creiamo ora delle regole più “generiche” che però si appoggiano sempre al termine family
Famiglia
![Page 8: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/8.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
husband(X):-
family(X, _, _).
wife(X):-
family(_, X, _).
child(X):-
family(_, _, Children),
member(X, Children).
Regole per family
![Page 9: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/9.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
exists(X):-
husband(X)
;
wife(X)
;
child(X).
salary(person(_, _, _, S), S).
dateOfBirth(person(_, _, Date, _),Date).
Regole per family
![Page 10: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/10.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• ?- exists(person(mario, rossi, _, _)).
• ?- exists(person(Name, Surname, _, _)).
• ?- child(X),
dateOfBirth(X, date(_,_,Y)),
Y < 2000.
• ?- exists(X),
salary(X, Y),
Y >30000.
Possibili query
![Page 11: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/11.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Automa non deterministico
s4
s1
s3
s2
b
b
null
a null
a
b
![Page 12: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/12.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
final(s3).
trans(s1, a, s1).
trans(s1, a, s2).
trans(s1, b, s1).
trans(s2, b, s3).
trans(s3, b, s2).
trans(s1, a, s4).
silent(s2, s4).
silent(s3, s1).
Automa non deterministico
![Page 13: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/13.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
accepts(State, []):-
final(State).
accepts(State, [X|Rest]):-
trans(State, X, State1),
accepts(State1, Rest).
accepts(State, Rest):-
silent(State, State1),
accepts(State1, Rest).
Automa non deterministico
![Page 14: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/14.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• ?- accepts(s1, [a,a,a,b]).– true
• ?- accepts(S, [a,b]).– S=s1;– S=s3;
• ?- accepts(s1, [X1,X2,X3]).– X1=a X2=a X3=b– …
• ?- String=[_,_,_], accepts(s1, String).– String = [a,a,b];– …
Query Automa
![Page 15: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/15.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Posizionare 8 regine su di una scacchiera vuota in modo che nessuna possa mangiare o essere mangiata da un’altra
• Esistono varie soluzione in Prolog, qui ne viene presentata una semplice con il minimo numero di variabili
Problema delle 8 Regine
![Page 16: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/16.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
solution( [] ).
solution( [X/Y | Others] ) :- % First queen at X/Y, other queens at Others
solution( Others),
member( Y, [1,2,3,4,5,6,7,8] ),
noattack( X/Y, Others). % First queen does not attack others
noattack( _, [] ). % Nothing to attack
noattack( X/Y, [X1/Y1 | Others] ) :-
Y =\= Y1, % Different Y-coordinates
Y1-Y =\= X1-X, % Different diagonals
Y1-Y =\= X-X1,
noattack( X/Y, Others).
% A solution template
template( [1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8] ).
8 Regine
![Page 17: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/17.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Famiglia:
– Scrivere la regola per avere le famiglie senza figli
– Scrivere la regola per avere Il reddito totale di una famiglia
– Scrivere la regola per avere le famiglie in cui i figli guadagnano più dei genitori
Esercizi
![Page 18: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/18.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Automa:– Scrivere una regola che accetti lo stato iniziale e due
numeri che rappresentino il numero minimo e massimo di transizioni (non nulle) che si possono fare. Tale regola dovrà accettare anche una variabile che conterrà la lista dei simboli di input usati per andare dallo stato iniziare a quello finale
Esercizi
![Page 19: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/19.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• 8 Regine:
– Modificare il programma per trattare un numero variabile di regine
– Scrivere una nuova versione della soluzione al problema delle 8 regine
Esercizi
![Page 20: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/20.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• In Prolog è possibile definire nuovi operatori, ma ne esistono già alcuni definiti (esempio gli operatori aritmetici)
• 1*2+3*4 ha i due operatori + e *• la scrittura in Prolog sarebbe:
– +(*(1,2), *(3,4))
Operatori
1 2 3 4
*
+
*
![Page 21: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/21.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Ogni operatore ha una sua priorità• a + b*c come deve essere letto?
– +(a, *(b,c) ?– *( +(a,b), c) ?
• Nel senso comune trasmessoci, * lega di più di +,
Definire un operatore
b c
*
+
a
a b
c
*
+
![Page 22: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/22.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Definire un operatore
Codificare la priorità: l’albero delle interpretazioni ha priorità decrescenti
+ ha priorità 500
* ha priorità 400
(e quindi + ha priorità più alta di *)
b c
*
+
a
a b
c
*
+
a + b*c
![Page 23: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/23.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• :- op(Priorità, Tipo, Operatore).
• Priorità è un numero tra 0 e 1200
• Tipo:– infisso : xfx, xfy, yfx– prefisso: fx, fy– postfisso: xf, fy
• Operatore: il nome/simbolo dell’operatore
Definire un operatore
![Page 24: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/24.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Il tipo serve ad indicare anche la precedenza degli operatori:– x : la sua priorità deve essere minore di quella
dell’operatore– y: la sua priorità deve essere minore o uguale a quella
dell’operatore
• :- op(700, yfx, somma).• Qual è l’albero risultante di
– 9 somma 5 somma 7 ?
Definire un operatore
![Page 25: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/25.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• :- op(700, yfx, somma).• 9 somma 5 somma 7
• Quello a sinistra è corretto, perché?
Definire un operatore
a b
c
somma
somma
b c
somma
somma
a
![Page 26: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/26.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esercizio
Studiamo la sintassi della lingua
Realizziamo gli operatori «ha» e «di», di modo che con frasi:• mario ha la macchina di dario• giovanni ha il cestino di mario
Risponda a interrogazioni come
Chi ha Cosa di X
![Page 27: Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)](https://reader035.vdocumenti.com/reader035/viewer/2022062701/5542eb6b497959361e8d7109/html5/thumbnails/27.jpg)
© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
• Definire la regola max(A, B, Max) in modo che in Max ci vada il massimo tra A e B
• Pensare anche al caso:– max(A, 5, 9)– A = 9.
Esercizio