Všechna řešení, třídění, rozdílové seznamy vsecnna reseni % z(Jmeno,Prijmeni,Pohlavi,Vek,Prace,Firma) z(petr,novak,m,30,skladnik,skoda). z(pavel,novy,m,40,mechanik,skoda). z(rostislav,lucensky,m,50,technik,skoda). z(alena,vesela,z,25,sekretarka,skoda). z(jana,dankova,z,35,asistentka,skoda). z(lenka,merinska,z,35,ucetni,skoda). z(roman,maly,m,35,manazer,cs). z(alena,novotna,z,40,ucitelka,zs_stara). z(david,novy,m,30,ucitel,zs_stara). z(petra,spickova,z,45,uklizecka,zs_stara). JS> Najdete 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 ). Najdete jméno a příjmení všech zamestnanců firmy skoda a cs ?- findall( c(J,P,Firma), ( z(J,P,_,_,_,Firma), ( Firma=skoda ; Firma=cs ) ), L ?- bagof( J-P, [S,V,Pr]A(z(J,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). ?- setof( 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 2011 2 Všechna řešení, třídění, rozdílové seznamy Všechna řešení Kolik žen a mužů je v databázi? ?- findall( c(P,J), z(P,J,z,_,_,_), L), length(L,N). ?- findall( c(P,J), z(P,J,m,_,_,_), L), length(L,N). Hana Rudová, Logické programování I, 1. dubna 2011 3 Všechna řešení, třídění, rozdílové seznamy Všechna řešení Kolik žen a mužů je v databázi? ?- findall( c(P,J), z(P,J,z,_,_,_), L), length(L,N). ?- findall( c(P,J), z(P,J,m,_,_,_), L), length(L,N). ?- bagof(c(P,J), [Ve,Pr,Fi]Az(P,J,S,Ve,Pr,Fi), L), length(L,N). Hana Rudová, Logické programování I, 1. dubna 2011 3 Všechna řešení, třídení, rozdílové seznamy Všechna řešení Kolik žen a mužu je v databázi? ?- findall( c(P,J), z(P,J,z,_,_,_), L), length(L,N). ?- findall( c(P,J), z(P,J,m,_,_,_), L), length(L,N). ?- bagof(c(P,J), [Ve,Pr,Fi]Az(P,J,S,Ve,Pr,Fi), L), length(L,N). ?- findall( S-N, ( bagof(c(P,J), [Ve,Pr,Fi]Az(P,J,S,Ve,Pr,Fi), L), length(L,N) ), Dvojice ). Hana Rudová, Logické přogřamování I, 1. dubna 2011 3 Všechna řešení, t řídení, řozdílové seznamy Všechna řešení: příklady 1. Jaká jsou příjmení všech žen? 2. Kteří lidé mají více než 30 rokU? Naleznete jejich jméno a příjmení 3. Naleznete abecedne seřazený seznam všech lidí. 4. Naleznete příjmení vyucujících ze zs_stara. 5. Jsou v databázi dva břatři (mají stejné příjmení a řůzná jména)? 6. Kteřé fiřmy v databázi mají více než jednoho zaměstnance? Hana Rudová, Logické přogřamování I, 1. dubna 2011 4 Všechna řešení, třídení, řozdílové seznamy Všechna řešení: příklady 1. Jaká jsou příjmení všech žen? 2. Kteří lidé mají více než 30 rokU? Naleznete jejich jméno a příjmení 3. Naleznete abecedne seřazený seznam všech lidí. 4. Naleznete příjmení vyucujících ze zs_stara. 5. Jsou v databázi dva břatři (mají stejné příjmení a řůzná jména)? 6. Kteřé fiřmy v databázi mají více než jednoho zaměstnance? 1. findall(Prijmeni, z(_,Prijmeni,z,_,_,_), L). Hana Rudová, Logické přogřamování I, 1. dubna 2011 4 Všechna řešení, třídení, řozdí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ů? Naleznete jejich jméno a příjmení. 3. Naleznete abecedne seřazený seznam všech lidí. 4. Naleznete příjmení vyucujících ze zs_stara. 5. Jsou v databázi dva břatři (mají stejné příjmení a řůzná jména)? 6. Kteřé fiřmy v databázi mají více než jednoho zaměstnance? 1. findall(Prijmeni, z(_,Prijmeni,z,_,_,_), L). 2. findallOmeno-Prijmeni, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). Hana Rudová, Logické programování I, 1. dubna 2011 4 Všechna řešení, třídení, řozdí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ů? Naleznete jejich jméno a příjmení. 3. Naleznete abecedne seřazený seznam všech lidí. 4. Naleznete příjmení vyucujících ze zs_stara. 5. Jsou v databázi dva břatři (mají stejné příjmení a řůzná jména)? 6. Kteřé fiřmy v databázi mají více než jednoho zaměstnance? 1. findall(Prijmeni, z(_,Prijmeni,z,_,_,_), L). 2. findallOmeno-Prijmeni, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). 3. setof(P-O [S,V,Pr,F]Az(J,P,S,V,Pr,F), L ). Hana Rudová, Logické programování I, 1. dubna 2011 4 Všechna řešení, třídení, řozdílové seznamy Všechna řešení: příklady 1. Jaká jsou příjmení všech žen? 2. Kteří lidé mají více než 30 rokU? Naleznete jejich jméno a příjmení. 3. Naleznete abecedne seřazený seznam všech lidí. 4. Naleznete příjmení vyucujících ze zs_stara. 5. Jsou v databázi dva břatři (mají stejné příjmení a řůzná jména)? 6. Kteřé fiřmy v databázi mají více než jednoho zaměstnance? 1. findall(Prijmeni, z(_,Prijmeni,z,_,_,_), L). 2. findallOmeno-Prijmeni, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). 3. setof(P-O [S,V,Pr,F]AzO,P,S,V,Pr,F), L ). 4. findall(Prijmeni, ( z(_,Prijmeni,_,_,P,zs_stara), (P=ucitel;P=ucitelka) ), L). Hana Rudová, Logické přogřamování I, 1. dubna 2011 4 Všechna řešení, třídení, řozdílové seznamy Všechna řešení: příklady 1. Jaká jsou příjmení všech žen? 2. Kteří lidé mají více než 30 rokU? Naleznete jejich jméno a příjmení. 3. Naleznete abecedne seřazený seznam všech lidí. 4. Naleznete příjmení vyucujících ze zs_stara. 5. Jsou v databázi dva břatři (mají stejné příjmení a řůzná jména)? 6. Kteřé fiřmy v databázi mají více než jednoho zaměstnance? 1. findall(Prijmeni, z(_,Prijmeni,z,_,_,_), L). 2. findallOmeno-Prijmeni, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). 3. setof(P-O [S,V,Pr,F]AzO,P,S,V,Pr,F), L ). 4. findall(Prijmeni, ( z(_,Prijmeni,_,_,P,zs_stara), (P=ucitel;P=ucitelka) ), L). 5. findall(b(J1-P,J2-P), ( z(J1,P,m,_,_,_),z(J2,P,m,_,_,_), J1@30 ), L). 3. setof(P-II, [S,V,Pr,F]AzO,P,S,V,Pr,F), L ). 4. findall(Prijmeni, ( z(_,Prijmeni,_,_,P,zs_stara), (P=ucitel;P=ucitelka) ), L). 5. findall(b(J1-P,J2-P), ( z(J1,P,m,_,_,_),z(J2,P,m,_,_,_), J1@1 ), S). Hana Rudová, Logické programování I, 1. dubna 2011 4 Všechna řešení, třídení, rozdílové seznamy bubblesort(S,Sorted) Seznam S seřaďte tak, že naleznete přvní dva sousední přvky X a Y v S tak, že X>Y, vymente pořadí X a Y a získate S1; a seřaďte S1 pokud neexistuje žádný takový pář sousedních přvků X a Y, pak je S seřazený seznam swap(S,S1) řekuřzivne bubblesořtem bubblesort(S,Sorted) :- swap (S,S1), !, bubblesort(S1, Sorted). bubblesort(Sorted,Sorted). % Existuje použitelný swap v S? % Jinak je seznam seřazený swap([X,Y|Rest],[Y,X|Rest1]) :-X>Y. swap([X|Rest],[X|Rest1]) :-swap(Rest,Rest1). % swap prvních dvou prvků % nebo obecneji X@>Y, resp. gt(X,Y) % swap prvků až ve zbytku Hana Rudová, Logické přogřamování I, 1. dubna 2011 Všechna řešení, t řídení, řozdílové seznamy 5 quicksort(S,Sorted) Neprázdný seznam S serad'te tak, že vybeřte nejaký přvek X z S; řozdelte zbytek S na dva seznamy Small a Big tak, že: v Big jsou vetší přvky než X a v Small jsou zbývající přvky konec rekurze pro S=[] napr. vyberte hlavu S split(X,Seznam,Small,Big) serad'te Small do SortedSmall rekurzivne quicksortem se rad'te Big do SortedBig rekurzivne quicksortem setrídený seznam vznikne spojením SortedSmall a [X|SortedBig] append Hana Rudová, Logické programování I, 1. dubna 2011 6 Všechna řešení, t řídení, řozdílové seznamy quicksort(S,Sorted) Neprázdný seznam S serad'te tak, že & vyberte nejaký prvek X z S; rozdelte zbytek S na dva seznamy Small a Big tak, že: v Big jsou vetší prvky než X a v Small jsou zbývající prvky J5> serad'te Small do SortedSmall & serad'te Big do SortedBig & setrídený seznam vznikne spojením SortedSmall a [X|SortedBig] konec rekurze pro S=[] např. vyberte hlavu S split(X,Seznam,Small,Big) rekurzivne quicksortem rekurzivne quicksortem append quicksort([],[]). quicksort([X|T], Sorted) :- split(X, Tail, Small, Big), quicksort(Small, SortedSmall), quicksort(Big, SortedBig), append(SortedSmall, [X|SortedBig], Sorted). Hana Rudová, Logické programování I, 1. dubna 2011 6 Všechna rešení, t rídení, rozdílové seznamy quicksort(S,Sorted) Neprázdný seznam S serad'te tak, že & vyberte nejaký prvek X z S; rozdelte zbytek S na dva seznamy Small a Big tak, že: v Big jsou vetší prvky než X a v Small jsou zbývající prvky J5> serad'te Small do SortedSmall & serad'te Big do SortedBig & setrídený seznam vznikne spojením SortedSmall a [X|SortedBig] konec rekurze pro S=[] napr. vyberte hlavu S split(X,Seznam,Small,Big) rekurzivne quicksortem rekurzivne quicksortem append quicksort([],[]). quicksort([X|T], Sorted) :- split(X, Tail, Small, Big), quicksort(Small, SortedSmall), quicksort(Big, SortedBig), append(SortedSmall, [X|SortedBig], Sorted). splitCX, [], [], []). split(X, [Y|T], [Y|Small], Big) :-X>Y, !, split(X, T, Small, Big). splitCX, [Y|T], Small, [Y|Big]) :- split(X, T, Small, Big). Hana Rudová, Logické programování I, 1. dubna 2011 Všechna řešení, trídení, rozdílové seznamy 6 DÚ:insertsort(S,Sorted) Nepřázdný seznam S=[X|T] seřaďte tak, že & seřaďte telo T seznamu S ií* vložte hlavu X do seřazeného tela tak, že výsledný seznam je zase seřazený. Víme: výsledek po vložení X je celý seřazený seznam. konec řekuřze přo S=[] řekuřzivne inseřtsořtem inseřt(X,SořtedT,Sořted) Hana Rudová, Logické přogřamování I, 1. dubna 2011 7 Všechna řešení, t řídení, řozdílové seznamy DÚ:insertsort(S,Sorted) Neprázdný seznam S=[X|T] serad'te tak, že konec rekurze pro S=[] seřaďte telo T seznamu S vložte hlavu X do seřazeného tela tak, že výsledný seznam je zase seřazený. Víme: výsledek po vložení X je celý seřazený seznam. rekurzivne insertsortem insert(X,SortedT,Sorted) insertsort([],[]). insertsort([X|T],Sorted) :-insertsort(T,SortedT), insert(X,SortedT,Sorted). insert(X,[Y|Sorted],[Y|Sorted1]) :-X > Y, 1, insert(X,Sorted,Sorted1). insert(X,Sorted,[X|Sorted]). % seřazení tela % vložení X na vhodné místo Hana Rudová, Logické přogřamování I, 1. dubna 2011 Všechna řešení, t řídení, řozdílové seznamy 7 Rozdílové seznamy Zapamatování konce a připojení na konec: řozdílové seznamy [a,b] ... L1-L2 = [a,b|T]-T = [a,b,c|S]-[c|S] = [a,b,c]-[c] Repřezentace přázdného seznamu: L-L A1 Z1 A2 Z2 1 \ i L2 \ L3 M ?- append( [1,2,3|Z1]-Z1, [4,5|Z2]-Z2, A1-[]). M append( A1-Z1, Z1-Z2, A1-Z2 ). L1 L2 L3 append( [1,2,3,4,5]-[4,5], [4,5]-[], Hana Rudová, Logické přogřamování I, 1. dubna 2011 8 [1,2,3,4,5]-[] ). Všechna řešení, t řídení, řozdílové seznamy reverse(Seznam, Opacny) % kvadratická složitost reverse( [], [] ). reverse( [ H | T ], Opacny ) :- reverse( T, OpacnyT ), append( OpacnyT, [ H ], Opacny ). Hana Rudová, Logické přogřamování I, 1. dubna 2011 9 Všechna řešení, t řídení, řozdílové seznamy reverse(Seznam, Opacny) % kvadratická složitost reverse( [], [] ). reverse( [ H | T ], Opacny ) :- reverse( T, OpacnyT ), append( OpacnyT, [ H ], Opacny ). % lineární složitost, rozdílové seznamy reverse( Seznam, Opacny ) :- reverse0( Seznam, ). reverse0( [], ). reverse0( [ H | T ], ) :- reverse0( T, ). Hana Rudová, Logické přogřamování I, 1. dubna 2011 9 Všechna řešení, třídění, rozdílové seznamy reverseCSeznam, Opacny) % kvadratická složitost reverseC [], [] )■ reverseC [H | T ], Opacny ) i- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). % lineární složitost, rozdílové seznamy reverseC Seznam, Opacny ) i- reverseOC Seznam, Opacny-[] ). reverseOC [], S-S ). reverseOC [ H | T ], Opacny-OpacnyKonec ) i- reverseOC T, Opacny-[ H | OpacnyKonec] ). Hana Rudová, Logické programování I, l. dubna 20ll 9 Všechna rešení, t rídení, rozdílové seznamy quicksort pomocí rozdílových seznamů Neprázdný seznam S serad'te tak, že & vyberte nejaký prvek X z S; rozdelte zbytek S na dva seznamy Small a Big tak, že: v Big jsou vetší prvky než X a v Small jsou zbývající prvky ií* serad'te Small do SortedSmall & serad'te Big do SortedBig setrídený seznam vznikne spojením SortedSmall a [X|SortedBig] quicksort(S, Sorted) :- quicksort1(S, ). quicksort1([], ). quicksort1([X|T], ) :- split(X, T, Small, Big), quicksort1(Small, ), quicksort1(Big, ). append(A1-A2, A2-Z2, A1-Z2). Hana Rudová, Logické programování I, 1. dubna 2011 10 Všechna řešení, t rídení, rozdílové seznamy quicksort pomocí rozdílových seznamů Neprázdný seznam S se rad'te tak, že & vyberte nejaký prvek X z S; rozdeite zbytek S na dva seznamy Small a Big tak, že: v Big jsou vetší prvky než X a v Small jsou zbývající prvky ií* se rad'te Small do SortedSmall JS* se rad'te Big do SortedBig set rídený seznam vznikne spojením SortedSmall a [X|SortedBig] quicksort(S, Sorted) :- quicksort1(S,Sorted-[]). quicksort1([],Z-Z). quicksort1C[X|T], A1-Z2) :- split(X, T, Small, Big), quicksort1(Small, A1-[X|A2]), quicksort1(Big, A2-Z2). append(A1-A2, A2-Z2, A1-Z2). Hana Rudová, Logické programování I, 1. dubna 2011 10 Všechna řešení, t rídení, rozdílové seznamy DÚ: palindrom(L) Napište předikát palindřom(Seznam), kteřý uspeje pokud se Seznam cte stejne zezadu i zepředu, př. [a,b,c,b,a] nebo [12,15,1,1,15,12] Hana Rudová, Logické přogřamování I, 1. dubna 2011 11 Všechna řešení, t řídení, řozdílové seznamy DÚ: palindrom(L) Napište predikát palindrom(Seznam), který uspeje pokud se Seznam cte stejne zezadu i zepredu, pr. [a,b,c,b,a] nebo [12,15,1,1,15,12] palindrom(Seznam) :- reverse(Seznam,Seznam). Hana Rudová, Logické programování I, 1. dubna 2011 11 Všechna rešení, t rídení, rozdílové seznamy