Ordinamento e Operazioni su
Strutture Dati
Fabio Massimo Zanzotto
University of Rome “Tor Vergata”
Ordinare una lista
Ordinare liste è sempre necessario :-)
/*ordinata(Lista,ListaOrdinata)*/
vera se ListaOrdinata è una lista che contiene tutti gli
elementi di Lista ed è ordinata.
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Ordinamento: prima realizzazione
Guardiamo alle proprietà:
ordinata(L,LO):permutazione(L,LO),
/*vera se L è una permutazione degli elementi di LO*/
ordinata(LO).
/*vera se L è una lista ordinata*/
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Ordinamento: prima realizzazione
/*ordinata(L).*/
scrivere
/*permutazione(L,LO).*/
scrivere
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
ordinata([]).
ordinata([X1]).
ordinata([X1,X2|R]):- X1 >= X2 ,!, ordinata([X2|R]).
permutazione([],[]).
permutazione([X|RX],Y):- permutazione(RX,RY),
member_new(X,Y,RY).
member_new(X,[X|R],R).
member_new(X,[P|R],[P|RR]):member_new(X,R,RR).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Ordinare una lista
• Nella letteratura esistono vari algoritmi per
ordinare una lista di elementi (confrontabili)
• I più famosi sono:
– Insertion sort
– Bubble sort
– Quick sort
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Bubble sort
bubblesort(List, Sorted):swap(List, List1),!,
bubblesort(List1, Sorted).
bubblesort(Sorted, Sorted).
swap([X,Y|Rest], [Y,X|Rest]):X @> Y.
swap([Z|Rest], [Z|Rest1]):swap(Rest, Rest1).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Quick sort
quicksort( [], []).
quicksort( [X|Tail], Sorted) :split( X, Tail, Small, Big),
quicksort( Small, SortedSmall),
quicksort( Big, SortedBig),
conc( SortedSmall, [X|SortedBig], Sorted).
split( X, [], [], []).
split( X, [Y|Tail], [Y|Small], Big) :gt( X, Y), !,
split( X, Tail, Small, Big).
split( X, [Y|Tail], Small, [Y|Big]) :split( X, Tail, Small, Big).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esercizio
• Implementare l’insertion sort
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Cercare con Alberi Binari
• Cercare elemento in una lista
• Alberi binari come rappresentazione efficiente
– Ricercare in alberi binari
– Aggiungere elementi in alberi binari
– Rimuovere elementi
– Costruire da una lista un albero binario bilanciato
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Cercare elementi in liste
member(X,[X|_]).
member(X,[_|L]):- member(X,L).
Costo?
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari
• Alberi che hanno:
– una radice
– un sottoalbero destro
– un sottoalbero sinistro
a
b
c
d
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari: una rappresentazione
/*t(SINISTRO,RADICE,DESTRO)
nil albero nullo*/
a
b
t(
t(nil,b,nil),
a,
t(t(nil,d,nil),c,nil)
).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
c
d
University of Rome “Tor Vergata”
Alberi binari: cercare in alberi binari
/*in(X,T).*/
Vero se X è un elemento, T è un albero binario, e X
è un nodo dell’albero.
in(X,t(_,X,_)).
in(X,t(L,_,_)):- in(X,L).
in(X,t(_,_,R)):- in(X,R).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari: cercare efficientemente
Ipotesi:
l’albero binario è costruito in modo che nella parte
sinistra ci siano solo elementi minori della radice e
nella parte destra solo elementi maggiori della radice
b
a
© A.Turbati, F.M.Zanzotto
c
d
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari: cercare efficientemente
Riscrivere
/*in(X,T).*/
Vero se X è un elemento, T è un albero binario, e X
è un nodo dell’albero.
in(X,t(_,X,_)).
in(X,t(L,Y,_)):- X<Y, !, in(X,L).
in(X,t(_,Y,R)):- X>Y, !, in(X,R).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari: problema
Ipotesi:
l’albero binario è costruito in modo che nella parte
sinistra ci siano solo elementi minori della radice e
nella parte destra solo elementi maggiori della radice
Come costruirli?
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari: costruzione
Immettere un elemento in un albero
/*add(S,X,S1)*/
vero se S è un albero binario con la proprietà
precedente, X è un elemento, S1 è un albero binario
con X è per cui vale la proprietà precedente
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari: costruzione
Partiamo da
/*addleaf(S,X,S1)*/
vero se S è un albero binario con la proprietà
precedente, X è un elemento, S1 è un albero binario
con X come foglia e per cui vale la proprietà
precedente
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari: costruzione
addleaf(nil,X,t(nil,X,nil)).
addleaf(t(L,X,R),X,t(L,X,R)).
addleaf(t(L,Root,R),X,t(L, Root,R1)):gt(X,Root),
addleaf(R,X,R1).
addleaf(t(L,Root,R),X,t(L1, Root,R)):gt(Root,X),
addleaf(L1,X,R).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari: togliere elemento
Partiamo da
/*delleaf(S,X,S1)*/
vero se S è un albero binario con la proprietà
precedente, X è un elemento foglia, S1 è un albero
binario senza X è per cui vale la proprietà precedente
delleaf(S,X,S1) :- addleaf(S1,X,S).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari: togliere elemento
Problema: ma se X non è una foglia?
A
X
?
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari: togliere elemento
Problema: ma se X non è una foglia?
X
Y
Y
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari: togliere elemento
/*del(S,X,S1)*/
vero se S è un albero binario con la proprietà
precedente, X è un nodo, S1 è un albero binario per
cui vale la proprietà precedente senza X
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari: togliere elemento
del(t(nil,X,R),X,R).
del(t(L,X,nil),X,L).
del(t(L,X,R),X,t(L,Y,R1)):delmin(R,Y,R1).
del(t(L,Y,R),X,t(L,Y,R1)):gt(X,Y),
del(R,X,R1).
del(t(L,Y,R),X,t(L1,Y,R)):gt(Y,X),
del(L,X,L1).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari: togliere elemento
delmin(t(nil,Y,R),Y,R).
delmin(t(L,Y,R),X, t(L1,Y,R)):delmin(L,X,L1).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Alberi binari
Esercizio
Costruire un albero binario bilanciato da una lista
/*listaInAlberoBinario(L,A)*/
vero se L è una lista, A è un albero binario con tutti
gli elementi della lista per cui valga la proprietà e sia
bilanciato.
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica