Všechna řešení, třídění, rozdílové seznamy Všechna řešení % z( Jméno, Prijmem' , Pohlaví , Vek, Prace, F i rma) z(petr,novak,m,30,skladník,škoda). z(pavel,ji rku,m,40,mechanik,škoda). z(rošti slav,1ucensky,m,50,techni k,škoda). z(alena,veselá,z,25,sekretárka,škoda). z(jana,dankova,z,35,asistentka,škoda). z(hana,ji rku,z,35,kuchařka,zs_stara). z(roman,maly,m,35,manažer,cs). z(alena,novotna,z,40,učitelka,zs_stara). z(david,ji rku,m,30,učitel,zs_stara). z(petra,špičková,z,45,uklizečka,zs_stara). M Najděte jméno a příjmení všech lidí. ?- findal1(Jmeno-Prijmeni, z(Jmeno,Prijmeni,_S,_V,_Pr,_F),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 ). ?- bagof( Jmeno-Prijmeni, [V,Pr,F] a z(Jmeno,Prijmeni,_S,V,Pr,F) , L). Hana Rudová, Logické programování 1,10. dubna 201 3 2 Všechna řešení, třídění, rozdílové seznamy Všechna řešení % z( Jméno, Prijmem' , Pohlaví , Vek, Prace, F i rma) z(petr,novak,m,30,skladník,škoda). z(pavel,ji rku,m,40,mechanik,škoda). z(rošti slav,1ucensky,m,50,techni k,škoda). z(alena,veselá,z,25,sekretárka,škoda). z(jana,dankova,z,35,asistentka,škoda). z(hana,ji rku,z,35,kuchařka,zs_stara). z(roman,maly,m,35,manažer,cs). z(alena,novotna,z,40,učitelka,zs_stara). z(david,ji rku,m,30,učitel,zs_stara). z(petra,špičková,z,45,uklizečka,zs_stara). M Najděte jméno a příjmení všech lidí. ?- findal1(Jmeno-Prijmeni, z(Jmeno,Prijmeni,_S,_V,_Pr,_F),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 ). ?- 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 cs ?- findal1( c(J,P,Firma), ( z(J,P,Firma), ( Firma=skoda ; Firma=cs ) ), ?- bagof( J-P, [S,V,Pr]a(zO,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). ?- setof( P-J, [S,V,Pr]a(zO,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). Hana Rudová, Logické programování I, 10. dubna 201 3 2 Všechna řešení, třídění, rozdílové seznamy Všechna řešení Kolik žen a mužů je v databázi? ?- findallC c(PJ), z(P, 3 ,z,_,_,_) , L) , length(L,N). ?- findallC c(PJ), z(P, 3 ,m, _,_,_) , L) , 1 ength(L, N) . Hana Rudová, Logické programování 1,10. dubna 201 3 3 Všechna řešení, třídění, rozdílové seznamy Všechna řešení Kolik žen a mužů je v databázi? ?- findalK c(PJ), z(P, 3 , z,_,_,_) , L) , 1 ength(L, N) . ?- findalK c(PJ), z(P, 3 ,m,_,_,_) , L) , length(L,N). ?- bagof(c(P,J), [Ve,Pr,Fi]az(P,3,S,Ve,Pr,Fi), L), 1ength(L,N). Hana Rudová, Logické programování 1,10. dubna 201 3 3 Všechna řešení, třídění, rozdílové seznamy Všechna řešení Kolik žen a mužů je v databázi? ?- findalK c(PJ), z(P, 3 , z,_,_,_) , L) , 1 ength(L, N) . ?- findalK c(PJ), z(P, 3 ,m,_,_,_) , L) , length(L,N). ?- bagof(c(P,J), [Ve,Pr,Fi]az(P,3,S,Ve,Pr,Fi), L), 1ength(L,N). ?- findalK S-N, ( bagof (c(P, J) , [Ve, Pr, Fi]az(P, 3 ,S,Ve, Pr, Fi) , L) , length(L,N) ), Dvojice ). Hana Rudová, Logické programování 1,10. dubna 201 3 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) \= vs. @< 6. Které firmy v databázi mají více než jednoho zaměstnance? Hana Rudová, Logické programování 1,10. dubna 201 3 4 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) \= vs. @< 6. Které firmy v databázi mají více než jednoho zaměstnance? 1. findal1(Přijmeni, z(_,Přijmeni,z,_,_,_), L). Hana Rudová, Logické programování 1,10. dubna 201 3 4 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) \= vs. @< 6. Které firmy v databázi mají více než jednoho zaměstnance? 1. findal1(Přijmeni, z(_,Přijmeni,z,_,_,_), L). 2. findal1(Jmeno-Prijmeni, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). Hana Rudová, Logické programování 1,10. dubna 201 3 4 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) \= vs. @< 6. Které firmy v databázi mají více než jednoho zaměstnance? 1. findal1(Přijmeni, z(_,Přijmeni,z,_,_,_), L). 2. findal1(Jmeno-Prijmeni, ( z(Jmeno,Přijmeni,_,Vek,_,_), Vek>30 ), L). 3. setofCP-J, [S,V,Pr,F]AzO,P,S,V,Pr,F), L ). Hana Rudová, Logické programování 1,10. dubna 201 3 4 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) \= vs. @< 6. Které firmy v databázi mají více než jednoho zaměstnance? 1. findal1(Přijmeni, z(_,Přijmeni,z,_,_,_), L). 2. findal1(Jmeno-Prijmeni, ( z(Jmeno,Přijmeni,_,Vek,_,_), Vek>30 ), L). 3. setofCP-J, [S,V,Pr,F]AzO,P,S,V,Pr,F), L ). 4. findal1(Přijmeni, ( z(_,PřijmeniP,zs_stara), (P=ucitel;P=ucitelka) ), L). Hana Rudová, Logické programování 1,10. dubna 201 3 4 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) \= vs. @< 6. Které firmy v databázi mají více než jednoho zaměstnance? 1. findal1(Přijmeni, z(_,Přijmeni,z,_,_,_), L). 2. findal1(Jmeno-Prijmeni, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). 3. setofCP-J, [S,V,Pr,F]AzO,P,S,V,Pr,F), L ). 4. findal1(Přijmeni, ( z(_,PřijmeniP,zs_stara), (P=ucitel;P=ucitelka) ), L). 5. findall(b(Jl-P,J2-P), ( z(Jl,P,m,_,_,_),z(J2,P,m,_,_,_), J1@30 ), L). 3. setofCP-J, [S,V,Pr,F]AzO,P,S,V,Pr,F), L ). 4. findal1(Přijmeni, ( z(_,PřijmeniP,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, 10. dubna 201 3 4 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; a seřaďte SI pokud neexistuje žádný takový pár sousedních prvků X a Y, pak je S seřazený seznam swap(S,Sl) rekurzivně bubblesortem bubblesort(S,Sorted) :- swap(S,SI), !, bubblesort(Sl, Sorted) bubblesort(Sorted,Sorted). % Existuje použitelný swap v S? % Jinak je seznam seřazený swap([X,YI Rest],[Y,X|Rest]) X>Y. swap([X|Rest],[XIRestl]) :-swap(Rest,Restl). % swap prvnich dvou prvků % nebo obecněji X@>Y, resp. gt(X,Y) % swap prvků až ve zbytku Hana Rudová, Logické programování 1,10. dubna 201 3 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=[] 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 např. vyberte hlavu S split(X,Seznam,Small,Big) seřaďte Small do SortedSmall rekurzivně quicksortem seřaďte Big do SortedBig rekurzivně quicksortem setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] append Hana Rudová, Logické programování 1,10. dubna 201 3 6 Všechna řešení, třídění, rozdílové seznamy qui cksort(S,Sorted) 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 seřaďte Small do SortedSmall M seřaďte Big do SortedBig M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] konec rekurze pro S=[] např. vyberte hlavu S split(X,Seznam,Small,Big) rekurzivně quicksortem rekurzivně quicksortem append quicksort([] , []) . quicksort([X|T], Sorted) : - split(X, T, Small, Big), quicksort(Smal1, SortedSmall), quicksort(Big, SortedBig), append(SortedSmal1, [X|SortedBig], Sorted) Hana Rudová, Logické programování 1,10. dubna 201 3 6 Všechna řešení, třídění, rozdílové seznamy qui cksort(S,Sorted) 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 seřaďte Small do SortedSmall M seřaďte Big do SortedBig M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] konec rekurze pro S=[] např. vyberte hlavu S split(X, Seznam, Small, Big) rekurzivně quicksortem rekurzivně quicksortem append quicksort([] , []) . quicksort([X|T], Sorted) :- split(X, T, Small, Big), quicksort(Smal1, SortedSmall), quicksort(Big, SortedBig), append(SortedSmal1, [X|SortedBig], Sorted) split(X, [], [], []). split(X, [Y|T], [Y|Small], Big) :- X>Y, !, split(X, T, Small, Big). split(X, [Y|T], Small, [Y|Big]) :- split(X, T, Small, Big). Hana Rudová, Logické programování 1,10. dubna 201 3 Všechna řešení, třídění, rozdílové seznamy DÚ: 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í 1,10. dubna 201 3 7 Všechna řešení, třídění, rozdílové seznamy DÚ: 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 insert(X,[Y|Sorted],[Y|Sortedl]) :-X > Y, !, insert(X,Sorted,Sortedl). insert(X,Sorted,[X|Sorted]). Hana Rudová, Logické programování 1,10. dubna 201 3 7 Všechna řešení, třídění, rozdílové seznamy 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 A1 Z1 A2 Z2 V V v \ L1 L2 ^-^ L3 ^ ?- append( [1,2,3|Zl]-Zl, [4,5|Z2]-Z2, Al-[]). 3 append( Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 append( [l,2,3,4,5]-[4,5], [4,5] Hana Rudová, Logické programování 1,10. dubna 2013 8 -[], [l,2,3,4,5]-[] ). Všechna řešení, třídění, rozdílové seznamy reverse(Seznam, Opacny) % kvadratická složitost reverse( [] , [] ) . reverse( [ H | T ], Opacny ) :- reverse( T, OpacnyT ), append( OpacnyT, [ H ], Opacny ). Hana Rudová, Logické programování 1,10. dubna 201 3 9 Všechna řešení, třídění, rozdílové seznamy reverse(Seznam, Opacny) % kvadratická složitost reverse( [] , [] ) . reverse( [ H | T ], Opacny ) :- reverse( T, OpacnyT ), append( OpacnyT, [ H ], Opacny ). % lineárni složitost, rozdilové seznamy reverse( Seznam, Opacny ) :- reverseO( Seznam, ). reverseO( [], ). reverseO( [ H | T ], ) :- reverseO( T, ). Hana Rudová, Logické programování 1,10. dubna 201 3 9 Všechna řešení, třídění, rozdílové seznamy reverse(Seznam, Opacny) % kvadratická složitost reverse( [] , [] ) . reverse( [ H | T ], Opacny ) :- reverse( T, OpacnyT ), append( OpacnyT, [ H ], Opacny ). % lineárni složitost, rozdilové seznamy reverse( Seznam, Opacny ) :- reverseO( Seznam, Opacny-[] ). reverseO( [], S-S ). reverseO( [ H | T ], Opacny-OpacnyKonec ) :- reverseO( T, Opacny-[ H | OpacnyKonec] ). Hana Rudová, Logické programování 1,10. dubna 201 3 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 3 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 3 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), qui cksortl(Smal1, ), quicksortl(Big, ). append(Al-Zl, Z1-Z2, A1-Z2). Hana Rudová, Logické programování 1,10. dubna 2013 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 3 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 3 seřaďte Big do SortedBig M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] quicksort(S, Sorted) :- quicksortl(S,Sorted-[]). qui cksortl( [],Z-Z). quicksortl([X|T], A1-Z2) :- spi i t(X, T, Small, Big), quicksortKSmall , A1-[X|Z1]) , qui cksortl(Bi g, Z1-Z2). append(Al-Zl, Z1-Z2, A1-Z2). Hana Rudová, Logické programování 1,10. dubna 2013 10 Všechna řešení, třídění, rozdílové seznamy DÚ: pal i ndrom(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í 1,10. dubna 201 3 Všechna řešení, třídění, rozdílové seznamy DÚ: pal i ndrom(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í 1,10. dubna 201 3 Všechna řešení, třídění, rozdílové seznamy