Všechna řešení, třídění, rozdílové seznamy Všechna řešení % z(Jmeno,Přijmeni,Pohlavi,Vek,Prace,Fi rma) z(petr,novak,m,30,skladnik,škoda). z(pavel,novy,m,40,mechani k,škoda). z(rostislav,lucensky,m,50,technik,škoda). z(alena,vesel a,z,25,sekretárka,škoda). z(jana,dankova,z,35,asistentka,škoda). z(lenka,merinska,z,35,ucetni,škoda). z(román,malý,m,35,manažer,es). z(alena,novotna,z,40,ucitelka,zs_stara). z(david,novy,m,30,učitel,zs_stara). z(petra,špičková,z,45,uklizečka,zs_stara). -• Najděte jméno a příjmení všech lidí. ?- findall(Jmeno-Prijmeni, z(Jmeno,Prijmeni,_,_,_,_),L). ?- bagof( Jmeno-Prijmeni, [S,V,Pr,F] a z(Jmeno,Prijmeni,S,V,Pr,F) , L). ?- bagof( Jmeno-Prijmeni, [V,Pr,F] a z(Jmeno,Prijmeni,S,V,Pr,F) , L ). -• Najděte jméno a příjmení všech zaměstnanců firmy škoda a es ?- findall( c(J , P, Fi rma) , ( z(J , P, _,_,_, Fi rma) , ( Firma=skoda ; Fi rma=cs ) ), L ?- bagof( J-P, [S,V,Pr]A(z(J,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). ?- setofC P-J, [S,V,Pr]A(z(J,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). Hana Rudová, Logické programování I, 1. dubna 2009 2 Všechna řešení, třídění, rozdílové seznamy Všechna řešení: příklady 1. Jaká jsou příjmení všech žen? 2. Kteří lidé mají více než 30 roků? Nalezněte jejich jméno a příjmení. 3. Nalezněte abecedně seřazený seznam všech lidí. 4. Nalezněte příjmení vyučujících ze zs_stara. 5. Jsou v databázi dva bratři (mají stejné příjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zaměstnance? Hana Rudová, Logické programování I, 1. dubna 2009 3 Všechna řešení, třídění, rozdílové seznamy Všechna řešení: příklady 1. Jaká jsou příjmení všech žen? 2. Kteří lidé mají více než 30 roků? Nalezněte jejich jméno a příjmení. 3. Nalezněte abecedně seřazený seznam všech lidí. 4. Nalezněte příjmení vyučujících ze zs_stara. 5. Jsou v databázi dva bratři (mají stejné příjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zaměstnance? 1. findall(Přijmeni, z(_,Přijmeni,z,_,_,_), L). 2. findall(Jmeno-Prijmeni, ( z(Jmeno,Přijmeni,_,Vek,_,_), Vek>30 ), L). 3. setof(P-II, [S,V,Pr,F]AzO,P,S,V,Pr,F), L ). Hana Rudová, Logické programování I, 1. dubna 2009 3 Všechna řešení, třídění, rozdílové seznamy Všechna řešení: příklady 1. Jaká jsou příjmení všech žen? 2. Kteří lidé mají více než 30 roků? Nalezněte jejich jméno a příjmení. 3. Nalezněte abecedně seřazený seznam všech lidí. 4. Nalezněte příjmení vyučujících ze zs_stara. 5. Jsou v databázi dva bratři (mají stejné příjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zaměstnance? 1. findall(Přijmeni, z(_,Přijmeni,z,_,_,_), L). 2. findall(Jmeno-Prijmeni, ( z(Jmeno,Přijmeni,_,Vek,_,_), Vek>30 ), L). 3. setof(P-II, [S,V,Pr,F]AzO,P,S,V,Pr,F), L ). 4. findall(Přijmeni, ( z(_,Přijmeni,_,_,P,zs_stara), (P=ucitel;P=ucitelka) ), L). 5. findall(b(Jl-P,J2-P), ( z(Jl,P,m,_,_,_),z(J2,P,m,_,_,_), J1@l ), S). Hana Rudová, Logické programování I, 1. dubna 2009 3 Všechna řešení, třídění, rozdílové seznamy bubblesort(S,Sorted) Seznam S seřaďte tak, že «Ä nalezněte první dva sousední prvky X a Y v S tak, že X>Y, vyměňte pořadí X a Y a získate SI; swap(S a seřaďte SI rekurzivně bubblesor & pokud neexistuje žádný takový pár sousedních prvků X a Y, pak je S seřazený seznam bubblesort(S,Sorted) :- swap (S,SI), !, % Existuje použitelný swap v S? bubblesort(Sl, Sorted). bubblesort(Sorted,Sorted). % Jinak je seznam seřazený swap([X,Y|Rest],[Y,X|Restl]) :- X>Y. swap([Z|Rest],[Z|Restl]) :- swap(Rest,Restl). Hana Rudová, Logické programování I, 1. dubna 2009 % swap prvních dvou prvků % nebo obecněji X@>Y, resp. gt(X,Y) % swap prvků až ve zbytku 4 Všechna řešení, třídění, rozdílové seznamy qui cksort(S,Sorted) Neprázdný seznam S seřaďte tak, že konec rekurze pro S=[] M vyberte nějaký prvek X z S; např. vyberte hlavu S rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky split(X,Seznam,Small,Big) M seřaďte Small do SortedSmall rekurzivně quicksortem M seřaďte Big do SortedBig rekurzivně quicksortem M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] append Hana Rudová, Logické programování I, 1. dubna 2009 5 Všechna řešení, třídění, rozdílové seznamy qui cksort(S,Sorted) Neprázdný seznam S seřaďte tak, že konec rekurze pro S=[] M vyberte nějaký prvek X z S; např. vyberte hlavu S rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky split(X,Seznam,Small,Big) M seřaďte Small do SortedSmall rekurzivně quicksortem M seřaďte Big do SortedBig rekurzivně quicksortem M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] append quicksort([] , []) . quicksort([X|T], Sorted) :- spi i t(X, Tail, Small, Big), quicksort(Small, SortedSmall), quicksort(Big, SortedBig), append(SortedSmall, [X|SortedBig], Sorted). Hana Rudová, Logické programování I, 1. dubna 2009 5 Všechna řešení, třídění, rozdílové seznamy qui cksort(S,Sorted) Neprázdný seznam S seřaďte tak, že konec rekurze pro S=[] M vyberte nějaký prvek X z S; např. vyberte hlavu S rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky split(X,Seznam,Small,Big) M seřaďte Small do SortedSmall rekurzivně quicksortem M seřaďte Big do SortedBig rekurzivně quicksortem M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] append quicksort([] , []) . quicksort([X|T], Sorted) :- spi i t(X, Tail, Small, Big), quicksort(Small, SortedSmall), quicksort(Big, SortedBig), append(SortedSmall, [X|SortedBig], Sorted). spi i t (X, [], [], []). split(X, [Y|T], [Y|Small], Big) :-X>Y, !, spi i t(X, T, Small, Big). spi i t(X, [Y|T], Small, [Y|Big]) :- spi i t(X, T, Small, Big). Hana Rudová, Logické programování I, 1. dubna 2009 5 Všechna řešení, třídění, rozdílové seznamy DU:insertsort(S,Sorted) Neprázdný seznam S=[X|T] seřaďte tak, že konec rekurze pro S=[] seřaďte tělo T seznamu S rekurzivně insertsortem vložte hlavu X do seřazeného těla tak, že výsledný seznam je zase seřazený. Víme: výsledek po vložení X je celý seřazený seznam. insert(X,SortedT,Sorted) Hana Rudová, Logické programování I, 1. dubna 2009 Všechna řešení, třídění, rozdílové seznamy DU:insertsort(S,Sorted) Neprázdný seznam S=[X|T] seřaďte tak, že konec rekurze pro S=[] M seřaďte tělo T seznamu S rekurzivně insertsortem M vložte hlavu X do seřazeného těla tak, insert(X,SortedT,Sorted) že výsledný seznam je zase seřazený. Víme: výsledek po vložení X je celý seřazený seznam. insertsort([] , []) . insertsort([X|T],Sorted) :- insertsort(T,SortedT), % seřazeni těla insert(X,SortedT,Sorted). % vloženi X na vhodné místo insertCX,[Y|Sorted],[Y|Sortedl]) :- X > Y, !, insert(X,Sorted,Sortedl). insert(X,Sorted,[X|Sorted]). Hana Rudová, Logické programování I, 1. dubna 2009 6 Všechna řešení, třídění, rozdílové seznamy Rozdílové seznamy Zapamatování konce a připojení na konec: rozdílové seznamy [a,b] = L1-L2 = [a,b|T]-T = [a,b,c|S]-[c|S] = [a,b,c]-[c] Reprezentace prázdného seznamu: L-L ?- appendC [1,2,3|Z1]-Z1, [4,5|Z2]-Z2, S ). appendC Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 appendC [1,2,3,4,5]-[4,5], [4,5]-[], [1,2,3,4,5]-[] ). Hana Rudová, Logické programování I, 1. dubna 2009 Všechna řešení, třídění, rozdílové seznamy reverse(Seznam, Opacny) % kvadratická složitost reverseC [], [] ) . reverseC [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). Hana Rudová, Logické programování I, 1. dubna 2009 8 Všechna řešení, třídění, rozdílové seznamy reverse(Seznam, Opacny) % kvadratická složitost reverseC [], [] ) . reverseC [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). % lineární složitost, rozdílové seznamy reverseC Seznam, Opacny ) :- reverseOC Seznam, ). reverseOC [] , ) ■ reverseOC [ H | T ] , ) :- reverseOC T, ) . Hana Rudová, Logické programování I, 1. dubna 2009 8 Všechna řešení, třídění, rozdílové seznamy reverse(Seznam, Opacny) % kvadratická složitost reverseC [], [] ) . reverseC [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). % lineární složitost, rozdílové seznamy reverseC Seznam, Opacny ) :- reverseOC Seznam, Opacny-[] ). reverseOC [], S-S ). reverseOC [ H | T ], Opacny-OpacnyKonec ) :- reverseOC T, Opacny-[ H | OpacnyKonec] ). Hana Rudová, Logické programování I, 1. dubna 2009 8 Všechna řešení, třídění, rozdílové seznamy DÚ: palindrom(L) Napište predikát palindrom(Seznam), který uspěje pokud se Seznam čte stejně zezadu i zepředu, př. [a,b,c,b,a] nebo [1 2,1 5,1,1,15,12] Hana Rudová, Logické programování I, 1. dubna 2009 9 Všechna řešení, třídění, rozdílové seznamy DÚ: palindrom(L) Napište predikát palindrom(Seznam), který uspěje pokud se Seznam čte stejně zezadu i zepředu, př. [a,b,c,b,a] nebo [1 2,1 5,1,1,15,12] pal indrom(Seznam) :- reverse(Seznam,Seznam). Hana Rudová, Logické programování I, 1. dubna 2009 9 Všechna řešení, třídění, rozdílové seznamy quicksort pomocí rozdílových seznamů Neprázdný seznam S seřaďte tak, že -M vyberte nějaký prvek X z S; rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky M seřaďte Small do SortedSmall -• seřaďte Big do SortedBig M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] quicksort(S, Sorted) :- quicksortl(S, ). quicksortl([] , ) . quicksortl([X|T], ) :- spi i t(X, T, Small, Big), quicksortl(Small, ), quicksortl(Big, ). append(Al-A2, A2-Z2, A1-Z2). Hana Rudová, Logické programování I, 1. dubna 2009 10 Všechna řešení, třídění, rozdílové seznamy quicksort pomocí rozdílových seznamů Neprázdný seznam S seřaďte tak, že -M vyberte nějaký prvek X z S; rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky M seřaďte Small do SortedSmall -• seřaďte Big do SortedBig M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] quicksort(S, Sorted) :- quicksortl(S,Sorted-[]). quicksortl([],Z-Z). quicksortl([X|T], A1-Z2) :- spi i t(X, T, Small, Big), quicksortlCSmall, A1-[X|A2]), quicksortlCBig, A2-Z2). append(Al-A2, A2-Z2, A1-Z2). Hana Rudová, Logické programování I, 1. dubna 2009 1 0 Všechna řešení, třídění, rozdílové seznamy