Všechna řešení Všechna řešení, třídění, rozdílové seznamy % zOmeno, Při jmen i, Pohlavi , Vek, Prače, Fi rma) z(petr,novak.m,30, skladni k,škoda). z(pavel,novy,m,40,mechani k,škoda). z(rostislav,lucensky,m,50, techni k, škoda) . z(alena,veselá,z, 25, sekretářka, škoda) . zCjana, dankova, z, 35 , asistentka, škoda) . zOenka.meri nska, z, 35 , ucetni , škoda) . z(roman, maly,m,35.manažer,cs). z(alena,novotna,z,40,učitelka,zs_stara). z(david,novy,m,30,učitel,zs_stara). zCpetra,špičková,z,45,uklizečka,zs_stara). ■ Najděte jméno a příjmení všech lidí. ?- findall Qmeno-Pri jmeni, zQmeno, Pri jmeni ,_,_,_,_), L) . ?- bagofC Jmeno-Prijmeni, [S,V,Pr,F] A zQmeno, Pri jmeni , S, V, Pr, F) , L). ?- bagofC Jmeno-Prijmeni, [V,Pr,F] A zQmeno, Pri jmeni , S, V, Pr, F) , L ). ■ Najděte jméno a příjmení všech zaměstnanců firmy škoda a cs ?- findallC cQ,P,Firma), ( zQ , P, Fi rma) , ( Firma=skoda ; Fi rma=cs ) ), ?- bagofC >P, [S,V,Pr]A(zO,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). ?- setofC P-J, [S,V,Pr]A(z(],P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). Hana Rudová, Logické programování I, 8. dubna 2010 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(Prijmeni, z(_,Prijmeni,z,_,_,_), L). 2. findall Qmeno-Pri jmeni , ( zQmeno, Pri jmeni ,_,Vek,_,_) , Vek>30 ), L) . 3. setofCP-J, [S,V,Pr,F]Az(],P,S,V,Pr,F), L). 4. findall(Prijmeni, ( z(_,PrijmeniP,zs_stara), (P=ucitel;P=ucitelka) ), L). 5. findall(b(]l-P,]2-P), ( zQl, P,m,_,_,_) ,zQ2 , P,m,_,_,_) , J1@l ), S). Hana Rudová, Logické programování I, 8. dubna 2010 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; 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 bubblesortCS,Sorted) :- swap (S,SI), !, bubblesortCSl, Sorted). bubblesortCSorted,Sorted). swap([X,Y|Rest],[Y,X|Restl]) :-X>Y. swap([Z|Rest],[Z|Restl]) :-swapCRest,Restl). Hana Rudová, Logické programování I, 8. dubna 2010 % Existuje použitelný swap v S? % ]inak je seznam seřazený % swap prvnich 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 ■ 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 ■ seřaďte Big do SortedBig ■ setříděný seznam vznikne spojením SortedSmall a [XISortedBig] quicksort([] , []) . quicksort([X|T], Sorted) konec rekurze pro S=[] např. vyberte hlavu S split(X,Seznam,Small,Big) rekurzivně quicksortem rekurzivně quicksortem append splitCX, Tail, Small, Big), quicksortCSmall, SortedSmall), quicksort(Big, SortedBig), appendCSortedSmall, [XISortedBig], Sorted). splitCX, [], [], []). splitCX, [Y|T], [Y|Small], Big) :-X>Y, !, split(X, T, Small, Big). splitCX, [Y|T], Small, [Y|Big]) :- splitCX, T, Small, Big). Hana Rudová, Logické programování I, 8. dubna 2010 5 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 A1 Z1 A2 Z2 L1 L2 \ -=»- L3 ■ ?- append( [1,2,3|Zl]-Zl, [4,5|Z2]-Z2, Al-[]). ■ append( Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 append( [1, 2 , 3 ,4, 5] - [4, 5] , [4,5]-[], [1, 2 , 3 ,4, 5] - [] ). Hana Rudová, Logické programování I, 8. dubna 2010 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 ■ seřaďte tělo T seznamu S ■ 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. insertsortC[], []) . insertsort([X|T].Sorted) :- i nsertsort(T,SortedT), insert(X,SortedT,Sorted). insertCX,[YlSorted],[Y|Sortedl]) X > Y, ! , insertCX,Sorted,Sortedl). insertCX,Sorted,[XlSorted]). konec rekurze pro S=[] rekurzivně insertsortem insert(X,SortedT,Sorted) % seřazeni těla % vloženi X na vhodné mi sto Hana Rudová, Logické programování I, 8. dubna 2010 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árni 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, 8. dubna 2010 Všechna řešení, třídění, rozdílové seznamy DÚ: pal i ndrom(L) quicksort pomocí rozdílových seznamů 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,1 5,1 2] pal i ndrom(Seznam) reverse(Seznam,Seznam). Hana Rudová, Logické programování I, 8. dubna 2010 Všechna řešení, třídění, rozdílové seznamy Neprázdný seznam S seřaďte tak, že ■ 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 ■ seřaďte Big do SortedBig ■ setříděný seznam vznikne spojením SortedSmall a [XISortedBig] quicksort(S, Sorted) :- quicksortl(S,Sorted-[]). quicksortl([],Z-Z). quicksortl([X|T], A1-Z2) :- split(X, T, Small, Big), quicksortlCSmall, A1-[X|A2]), quicksortKBig, A2-Z2). append(A1-A2, A2-Z2, A1-Z2). Hana Rudová, Logické programování I, 8. dubna 2010 Všechna řešení, třídění, rozdílové seznamy