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,ji rku,m,40.mechanik,škoda). z(rostislav,lucensky,m,50, techni k, škoda) . z(alena,veselá,z, 25, sekretářka, škoda) . zCjana,dankova,z,35,asistentka,škoda). z(hana,jirku,z,35,kuchárka,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). zCpetra,špičková,z,45,uklizecka,zs_stara). ■ Najděte jméno a příjmení všech lidí. ?- f i ndal 1 Qmeno-Pri jmen i, z (Jméno, Pri jmen i ,_S ,_V,_Pr ,_F) , 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 ). ?- 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 ?- bagofC >P, [S,V,Pr]A(zO,P,S,V,Pr,F),( F=skoda ?- setofC P-J, [S,V,Pr]A(z(],P,S,V,Pr,F),( F=skoda Hana Rudová, Logické programování I, 18. května 2012 2 Fi rma=cs ) ), ; F=cs ) ) , L ). ; F=cs ) ) , L ). Všechna řešení, třídění, rozdílové seznamy Všechna řešení Kolik žen a mužů je v databázi? ?- findallC c(P,]), z(P,],z,_,_,_), L), length(L.N). ?- findallC c(P,]), z(P,],m,_,_,_), L), length(L.N). ?- bagof (c(PJ) , [Ve,Pr,Fi]Az(P,J,S,Ve,Pr,Fi), L), length(L.N). ?- findallC S-N, C bagof (c(PJ) , [Ve, Pr, Fi ] AZ(P, ] , S, Ve, Pr, Fi) , L), length(L.N) ), Dvoj i ce ) . Hana Rudová, Logické programování I, 18. května 2012 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? 1. findall(Prijmeni, z(_,Prijmeni,z,_,_,_), L). 2. findall Qmeno-Pri jmeni , ( z(]meno, 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, _,_,_), z(]2 , P,m, _,_,_) , J1@l ), S). Hana Rudová, Logické programování I, 1 8. května 201 2 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 bubblesortCS,Sorted) :- swapCS,SI), !, bubblesortCSl, Sorted). bubblesortCSorted,Sorted). % Existuje použitelný swap v S? % ]inak je seznam seřazený swapC[X,Y|Rest],[Y,X|Rest]) :-X>Y. swap([X|Rest],[XIRestl]) :-swapCRest,Restl) . Hana Rudová, Logické programování I, 18. května 2012 % swap prvnich dvou prvků % nebo obecněji X@>Y, resp. gt(X,Y) % swap prvků až ve zbytku 5 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í Xje celý seřazený seznam. insertsortC[] , []) . insertsort([X|T].Sorted) :- i nsertsort(T,SortedT), insert(X.SortedT,Sorted). insertCX,[YlSorted],[YlSortedl]) X > Y, ! , insertCX,Sorted,Sortedl). insertCX,Sorted, [X|Sorted]). 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, 18. května 2012 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] quicksortC[] , []) . quicksortC[X|T], Sorted) konec rekurze pro S=[] např. vyberte hlavu S split(X,Seznam,Small,Big) rekurzivně quicksortem rekurzivně quicksortem append splitCX, T, Small, Big), quicksortCSmall, SortedSmall), quicksortCBig, SortedBig), appendCSortedSmall, [XISortedBig], Sorted). splitCX, [], [], []). splitCX, [Y|T], [Y|Small], Big) :-X>Y, !, splitCX, T, Small, Big). splitCX, [Y|T], Small, [Y|Big]) :- splitCX, T, Small, Big). Hana Rudová, Logické programování I, 1 8. května 201 2 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 A1 v Z1 A2 Z2 L1 L2 \ -3- L3 ?- append( [1,2,3|Z1]-Z1, [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, 1 8. května 201 2 Všechna řešení, třídění, rozdílové seznamy reverse(Seznam, Opacny) quicksort pomocí rozdílových seznamů % 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, 18. května 2012 9 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,1 5,1 2] pal indromCSeznam) :- reverseCSeznam,Seznam). 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] quicksortCS, Sorted) :- quicksortlCS,Sorted-[]). quicksortlC[],Z-Z). quicksortlC[X|T], A1-Z2) :- splitCX, T, Small, Big), quicksortlCSmall, AI-[X|Zl]), quicksortlCBig, Z1-Z2). appendCAl-Zl, Z1-Z2, A1-Z2). Hana Rudová, Logické programování I, 1 8. května 201 2 10 Všechna řešení, třídění, rozdílové seznamy Hana Rudová, Logické programování I, 1 8. května 201 2 Všechna řešení, třídění, rozdílové seznamy