IB013 Logické programování I (průsvitky ze cvičení) Hana Rudová jaro 2011 Backtracking, unifikace, aritmetika Syntaxe logického programu Term: JS> univerzální datová struktura (slouží také pro příkazy jazyka) ii> definovaný rekurzivně & konstanty: číselné, alfanumerické (začínají malým písmenem), ze speciálních znaku (operátory) proměnné: pojmenované (alfanumerické retezce začínající anonymní (zacínají podtržítkem) složený term: funktor, arita, argumenty struktury jsou opet termy Hana Rudová, Logické programování I, 13. kvetna 2011 Backtracking, unifikace, aritmetika Anatomie a sémantika logického programu & Program: množina predikátů (v jednom nebo více souborech). & Predikát (procedura) je seznam klauzulí s hlavou stejného jména a arity & Klauzule: vety ukoncené teckou, se skládají z hlavy a tela. Prázdné telo mají fakta, neprázdné pak pravidla, existují také klauzule bez hlavy - direktivy. Hlavu tvorí literál (složený term), telo seznam literálu. Literálům v tele nebo v dotazu ríkáme cíle. Dotazem v prostredí interpretu se spouští programy ci procedury. & pr. otec(Otec,Dite) i- rodic(Otec,Dite), muz(Otec). rodicCpetr, jana). i- otec(Otec, jana). Sémantika logického programu: procedury = databáze faktu a pravidel = logické formule Hana Rudová, Logické programování I, 13. kvetna 2011 4 Backtracking, unifikace, aritmetika : SICStus Debugging - My Prolog Project/rny_rnodule.pro - Eclipse SDK dow Help O ' EH 1 $ SICStus Debu... | " % Debug eT\^ % 0»» D ■ 1 3. o> .ß % 1 ^ Q n"1 M= Variables eTX^*« Breakpoints] to *í B ^ " n' ^ Prolog Top-level Configuration [SICStus Launch Configuration Type 1] Name Value jj^ Prolog Target ❖ Suff [a, .7551, c] = call: suffix[[a,_7551,c],_1810] ❖ X _1810 = rny_predlL1810] ^ Prolog Top-level Process rny_rnodule,pro S3 /* -*- Mode .-Prolog □ Outline */ :- ir.odule (ir.y_rr.odule, [it.y_predl/i, it.y pred3/J £ c=rr.s about exporting undefined predicate ]> ■ dl :- use_ir.odule (library (lists) , [postfix/5, Í varus about importing undefined predicate suffix/5 £ integrated help {also for- user predicatesj If * my_predl/l IDE -> Eclipse 3.6 Jr príkazový rádek: z nabídky All Programs -> IDE -> SICStus 4.1.3 nastavíme pracovní adresár pomocí File/Working directory, v prípade potreby nastavíme font Settings/Font a uložíme nastavení Settings/Save settings. C- Iniciální nastavení SICStus IDE v Eclipse pomocí Help->Cheat Sheets->Initial set up of paths to installed SICStus Prolog s cestou "C:\Program Files (x86)\SICStus Prolog VC9 4.L3\bin\sicstus.exe" návod: http://www.sics.se/sicstus/spider/site/prerequisites.html#SettingUp Hana Rudová, Logické programování I, 13. kvetna 2011 6 Backtracking, unifikace, aritmetika SICStus Prolog: konzultace & Otevření souboru: File->Open File & Přístup k příkazové řádce pro zadávání dotazU: SICStus->Open Toplevel & NaCtení programu: tzv. konzultace prímo z Menu: SICStus->Consult Prolog Code (okno s programem aktivní) nebo zadáním na příkazový rádek po uložení souboru (Ctrl+S) ?- consult(rodokmen). pokud uvádíme celé jméno prípadne cestu, dáváme jej do apostrofů ?- consult('D:\prolog\moje\programy\rodokmen.pl'). JS> V Eclipse lze nastavit Key bindings, pracovní adresár, ... Hana Rudová, Logické programování I, 13. kvetna 2011 7 Backtracking, unifikace, aritmetika SICStus Prolog: spouštění a přerušení výpočtu Spouštění programů/procedur/predikátů je zápis dotazů na příkazové řádce (v okne TopLevel, kůrzor můsí být na konci posledního řádků s | ?- ), př. ?- predek(petr,lenka). ?- predek(X,Y). Každý příkaz ůkonCůjeme teCkoů. & Prerušení a zastavení cyklícího programu: pomocí ikony Restařt Přolog z okna Toplevel Hana Růdová, Logické přogřamování I, 13. května 2011 8 Backtracking, unifikace, aritmetika Příklad rodokmen rodicCpetr, filip). rodic(petr, lenka). rodic(pavel, jan). rodic(adam, petr). rodic(tomas, michal). rodic(michal, radek). rodic(eva, filip). rodic(jana, lenka). rodic(pavla, petr). rodic(pavla, tomas). rodic(lenka, vera). otec(Otec,Dite) rodic(Otec,Dite), muz(petr). muz(filip). muz(pavel). muz(jan). muz(adam). muz(tomas). muz(michal). muz(radek). zena(eva). zena(lenka). zena(pavla). zena(jana). zena(vera). muz(Otec). Hana Rudová, Logické programování I, 13. května 2011 9 Backtracking, unifikace, aritmetika Backtracking: príklady V pracovním adresáři vytvořte program rodokmen.pl. Načtěte program v interpretu (konzultujte). V interpretu Sicstus Prologu pokládejte dotazy: Je Petr otcem Lenky? & Je Petr otcem Jana? JS> Kdo je otcem Petra? & Jaké deti má Pavla? JS> Ma Petr dceru? Které dvojice otec-syn známe? Hana Rudová, Logické programování I, 13. kvetna 2011 10 Backtracking, unifikace, aritmetika Backtracking: řešení příkladů Stredníkem si vyžádáme další rešení | ?- otec(petr,lenka). yes | ?- otec(petr,jan). no | ?- otec(Kdo,petr). Kdo = adam ? ; no | ?- rodic(pavla,Dite). Dite = petr ? ; Dite = tomas ? ; no | ?- otec(petr,Dcera),zena(Dcera). Dcera = lenka ? ; no Hana Rudová, Logické programování I, 13. kvetna 2011 | ?- otec(Otec,Syn),muz(Syn). Syn = filip, Otec = petr ? ; Syn = jan, Otec = pavel ? ; Syn = petr, Otec = adam ? ; Syn = michal, Otec = tomas ? ; Syn = radek, Otec = michal ? ; no I ?- 11 Backtracking, unifikace, aritmetika Backtracking: příklady II Predikát potomek/2: potomek(Potomek,Predek) rodic(Predek,Potomek). potomek(Potomek,Predek) rodic(Predek,X), potomek(Potomek,X). Naprogramujte predikáty & prababicka(Prababicka,Pravnouce) nevlastni_bratr(Nevlastni_bratr,Nevlastni_sourozenec) nápoveda: využijte X \== Y (X a Y nejsou identické) Hana Rudová, Logické programování I, 13. kvetna 2011 12 Backtracking, unifikace, aritmetika Backtracking: příklady II Predikát potomek/2: potomek(Potomek,Predek) rodic(Predek,Potomek). potomek(Potomek,Predek) rodic(Predek,X), potomek(Potomek,X). Naprogramujte predikáty & prababicka(Prababicka,Pravnouce) nevlastni_bratr(Nevlastni_bratr,Nevlastni_sourozenec) nápoveda: využijte X \== Y (X a Y nejsou identické) Rešení: prababicka(Prababicka,Pravnouce):-rodic(Prababicka,Prarodic), zena(Prababicka), rodic(Prarodic,Rodic), rodic(Rodic,Pravnouce). Hana Rudová, Logické programování I, 13. kvetna 2011 12 Backtracking, unifikace, aritmetika Backtracking: řešení příkladů II nevlastni_bratr(Bratr,Sourozenec):-rodic(X,Bratr), muz(Bratr), rodic(X,Sourozenec), /* tento test neni nutny, ale zvysuje efektivitu */ Bratr \== Sourozenec, rodic(Y,Bratr), Y \== X, rodic(Z,Sourozenec), Z \== X, Z \== Y. /* nevhodne umisteni testu -vypocet "bloudi" v neuspesnych vetvich */ nevlastni_bratr2(Bratr,Sourozenec):-rodic(X,Bratr), rodic(X,Sourozenec), rodic(Y,Bratr), rodic(Z,Sourozenec), Y \ == X, Z \ == X, Z \== Y, muz(Bratr). Hana Rudová, Logické programování I, 13. května 2011 13 Backtracking, unifikace, aritmetika Backtracking: prohledávání stavového prostoru -í* Zkuste predem odhadnout (odvodit) poradí, v jakem budou nalezeni potomci Pavly? Jaký vliv má poradí klauzulí a cílu v predikátu potomek/2 na jeho funkci? Nahrad'te ve svých programech volání predikátu rodic/2 následujícím predikátem rodic_v/2 rodic_v(X,y):-rodicCX,Y),printCX),printC'? '). Pozorujte rozdíly v délce výpoctu dotazu nev1astni_bratr(fi1ip,X) pri zmene poradí testů v definici predikátu nev1astni_bratr/2 Hana Rudová, Logické programování I, 13. kvetna 2011 14 Backtracking, unifikace, aritmetika Backtracking: řešení III /* varianta 1a */ potomek(Potomek,Predek):-rodic(Predek,Potomek). potomek(Potomek,Predek):-rodic(Predek,X),potomek(Potomek,X). /* varianta 1b - jine poradi odpovedi, neprimi potomci maji přednost */ potomek(Potomek,Predek):-rodic(Predek,X),potomek(Potomek,X). potomek(Potomek,Predek):-rodic(Predek,Potomek). /* varianta 2a - leva rekurze ve druhe klauzuli, na dotaz potomek(X,pavla) vypise odpovedi, pak cykli */ potomek(Potomek,Predek):-rodic(Predek,Potomek). potomek(Potomek,Predek):-potomek(Potomek,X),rodic(Predek,X). /* varianta 2b - leva rekurze v prvni klauzuli, na dotaz potomek(X,pavla) hned cykli */ potomek(Potomek,Predek):-potomek(Potomek,X),rodic(Predek,X). potomek(Potomek,Predek):-rodic(Predek,Potomek). Hana Rudová, Logické programování I, 13. kvetna 2011 15 Backtracking, unifikace, aritmetika | ?- nevlastni_bratr(X,Y). petr? petr? petr? petr? eva? petr? jana? X = filip, Y = lenka ? ; petr? pavel? pavel? adam? adam? tomas? tomas? michal? michal? eva? eva? jana? pavla? pavla? pavla? adam? pavla? pavla? pavla? pavla? pavla? pavla? lenka? no | ?- nevlastni_bratr2(X,Y). petr? petr? petr? petr? eva? eva? petr? eva? petr? petr? petr? jana? eva? petr? jana X = filip, Y = lenka ? ; petr? petr? petr? petr? eva? jana? petr? eva? petr? petr? petr? jana? jana? petr? jana? pavel? pavel? pavel? pavel? adam? adam? adam? adam? pavla? pavla? adam? pavla? tomas? tomas? tomas? tomas? michal? michal? michal? michal? eva? eva? petr? petr? eva? eva? petr? eva? jana? jana? petr? petr? jana? jana? petr? jana? pavla? pavla? adam? adam? pavla? pavla? adam? pavla? pavla? adam? pavla? pavla? pavla? pavla? pavla? pavla? adam? pavla? pavla? pavla? pavla? lenka? lenka? lenka? lenka? no Hana Rudová, Logické programování I, 13. kvetna 2011 16 Backtracking, unifikace, aritmetika Unifikace:příklady Které unifikace jsou korektní, které ne a proC? Co je výsledkem provedených unifikací? 1. a(X)=b(X) 2. X=a(Y) 3. a(X)=a(X,X) 4. X=a(X) 5. jmeno(X,X)=jmeno(Petr,p1us) 6. s(1,a(X,q(w)))=s(Y,a(2,Z)) 7. s(1,a(X,q(X)))=s(W,a(Z,Z)) 8. X=Y,P=R,s(1,a(P,q(R)))=s(Z,a(X,Y)) Hana Rudová, Logické programování I, 13. května 2011 17 Backtracking, unifikace, aritmetika Unifikace:příklady Které unifikace jsou korektní, které ne a proc? Co jě výsledkem provedených unifikací? 1. a(X)=b(X) 2. X=a(Y) 3. a(X)=a(X,X) 4. X=a(X) 5. jmeno(X,X)=jmeno(Petr,plus) 6. s(1,a(X,q(w)))=s(Y,a(2,Z)) 7. s(1,a(X,q(X)))=s(W,a(Z,Z)) 8. X=Y,P=R,s(1,a(P,q(R)))=s(Z,a(X,Y)) Neuspeje volání 1) a 3), ostatní ano, cyklické struktury vzniknou v případech 4),7) a 8) prestože u posledních dvou mají levá a pravá strana unifikace disjunktní množinyjmen promenných. Hana Rudová, Logické programování I, 13. kvetna 2011 17 Backtracking, unifikace, aritmetika Mechanismus unifikace I Unifikace v přůbehů dokazování předikátů odpovídá předávání pařametřů při přovádení přocedůřy, aleje důležité ůvedomit si řozdíly. Celý přoces si ůkážeme na příkladů předikátů suma/3. suma(0,X,X). /*klauzule A*/ suma(s(X),Y,s(Z)):-suma(X,Y,Z). /*klauzule B*/ pomocí sůbstitůcních řovnic při odvozování odpovedi na dotaz ?- suma(s(0),s(0),X0). Hana Růdová, Logické přogřamování I, 13. kvetna 2011 ls Backtracking, unifikace, aritmetika Mechanismus unifikace II suma(0,X,X). /*A*/ suma(sCX),Y,s(Z)):-suma(X,Y,Z). /*B*/ ?- suma(s(0),s(0),X0). 1. dotaz unifikujeme s hlavou klauzule B, s A nejde unifikovat (1. argument) suma(s(0),s(0),X0) = suma(s(X1),Y1,s(Z1)) ==> X1 = 0, Y1 = s(0), s(Z1) = X0 ==> suma(0,s(0),Z1) 2. dotaz (nový podcíl) unifikujeme s hlavou klauzule A, klauzuli B si poznacíme jako další možnost suma(0,s(0),Z1) = suma(0,X2,X2) X2 = s(0), Z1 = s(0) ==> X0 = s(s(0)) X0 = s(s(0)) ; 2' dotaz z kroku 1. nejde unifikovat s hlavou klauzule B (1. argument) no Hana Rudová, Logické programování I, 13. kvetna 2011 19 Backtracking, unifikace, aritmetika Vícesmernost predikátů Logický program lze využít vícesmerne, napríklad jako JS> výpocet kdo je otcem Petra? ?- otec(X,petr). kolikje 1+1? ?- suma(s(0),s(0),X). iS* test je Jan otcem Petra? ?- otec(jan,petr). Je 1+1 2??- suma(s(0),s(0),s((0)) ). & generátor které dvojice otec-díte známe? ?-otec(X,Y). Které X a Y dávají v souctu 2? ?- suma(X,Y,s(s(0)) ). ... ale pozor na levou rekurzi, volné promenné, asymetrii, a jiné záležitosti Následující dotazy ?-suma(X,s(0),Z). ?-suma(s(0),X,Z). nedávají stejné výsledky. Zkuste si je odvodit pomocí substitucních rovnic. Hana Rudová, Logické programování I, 13. kvetna 2011 20 Backtracking, unifikace, aritmetika Aritmetika Zavádíme z praktických duvodu, ale aritmetické predikáty již nejsou vícesmerné, protože v každém aritmetickém výrazu musí být všechny promenné instaciovány císelnou konstantou. Duležitý rozdíl ve vestavených predikátech is/2 vs. =/2 vs. =:=/2 is/2: < konstanta nebo promenná > is < aritmetický výraz > výraz na pravé strane je nejdríve aritmeticky vyhodnocen a pak unifkován s levou stranou =/2: < libovolný term > = < libovolný term > levá a pravá strana jsou unifikovány "=:="/2 "=\="/2 ">="/2 "=<"/2 < aritmetický výraz > =:= < aritmetický výraz > < aritmetický výraz > =\= < aritmetický výraz > < aritmetický výraz > =< < aritmetický výraz > < aritmetický výraz > >= < aritmetický výraz > levá i pravá strana jsou nejdríve aritmeticky vyhodnoceny a pak porovnány Hana Rudová, Logické programování I, 13. kvetna 2011 21 Backtracking, unifikace, aritmetika Aritmetika: príklady Jak se liší následující dotazy (na co se kdy ptáme)? Kteřé ůspejí (kladná odpoved ' ), kteřé neůspejí (zápořná odpoved'), a kteřé jsoů špatne (dojde k chybe)? Za jakých předpokladů by ty neúspešné případne špatné ůspely? 1. X = Y+ 1 2. X is Y+ 1 3. X = Y 4. X== Y 5. 1 + 1 = 2 6. 2 = 1 + 1 7. 1 + 1 = 1 + 1 8. 1 + 1 is 1 + 1 9. 1 + 2 =:= 2 + 1 10. X \== Y 11. X=\= Y 12.1+2 =\= 1-2 13. 1 <= 2 14. 1 =< 2 15. sin(X) is sin(2) 16. sin(X) = sin(2+Y) 17. sin(X) =:= sin(2+Y) Nápoveda: '='/2 ůnifikace, '=='/2 test na identitů, '=:='/2 ařitmetická řovnost, '\==' /2 negace testů na identitů, '=\=' /2 ařitmetická neřovnost Hana Růdová, Logické přogřamování I, 13. kvetna 2011 22 Backtracking, unifikace, aritmetika Aritmetika: příklady II Jak se liší predikáty sl/3 a s2/3? Co umí sl/3 navíc oproti s2/3 a naopak? s1(s(X),Y,s(Z)):-s1(X,Y,Z). s2(X,Y,Z):- Z is X + Y. Hana Rudová, Logické programování I, 13. května 2011 23 Backtracking, unifikace, aritmetika Aritmetika: příklady II Jak se liší predikáty sl/3 a s2/3? Co umí sl/3 navíc oproti s2/3 a naopak? s1(s(X),Y,s(Z)):-s1(X,Y,Z). s2(X,Y,Z):- Z is X + Y. sl/3 je vícesmerný- umí sCítat, odeCítat, generovat souCty, ale pracuje jen s nezápornými celými Císly s2/3 umí pouze scítat, ale také záporná a reálná císla Hana Rudová, Logické programování I, 13. kvetna 2011 23 Backtracking, unifikace, aritmetika Operátory Definice operátoru umožnuje prehlednejší infixový zápis binárních a unárních predikátů, príklad: definice op(1200,Y,':-') umožnuje zápis a:-print(s(s(0))),b,c). pro výraz :-(a,,(print(s(s(0))),,(b,c))). Prefixovou notaci lze získat predikátem display/1. Vyzkoušejte display((a:-print(s(s(0))),b,c)). display(a+b+c-d-e*f*g-h+i). display([1,2,3,4,5]). Definice standardních operátoru najdete na konci manuálu. Hana Rudová, Logické programování I, 13. kvetna 2011 24 Backtracking, unifikace, aritmetika Zaver Dnešní látku jste pochopili dobre, pokud víte -i* jaký vliv má poradí klauzulí a cílu v predikátu potomek/2 na jeho funkci, -í* jak umisťovat testy, aby byl prohledávaný prostor co nejmenší (príklad nevlastni_bratr/2), -i* k ccemu dojde po unifikaci X=a(X), -i* proc neuspeje dotaz ?- X=2, sin(X) is sin(2). za jakých predpokladu uspejí tyto cíle X=Y, X==Y, X=:=Y, & a umíte odvodit pomocí substitucních rovnic odpovedi na dotazy suma(X,s(0),Z) a suma(s(0),X,Z). Hana Rudová, Logické programování I, 13. kvetna 2011 25 Backtracking, unifikace, aritmetika Seznamy, řez Reprezentace seznamu -i* Seznam: [a, b, c], prázdný seznam [] & Hlava (libovolný objekt), telo (seznam): .(Hlava, Telo) A všechny strukturované objekty stromy - i seznamy ± funktordva argumenty .(a, .(b, .(c, []))) = [a, b, c] i> notace: [ Hlava | Telo ] = [a|Te1o] Telo je v [a|Te1o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] & Lze psát i: [a,b|Te1o] pred "|"je libovolný pocet prvků seznamu , za "|"je seznam zbývajících prvků [a,b,c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]] pozor: [ [a,b] | [c] ] = [ a,b | [c] ] & Seznam jako neúplná datová struktura: [a,b,c|T] A Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S] Hana Rudová, Logické programování I, 13. kvetna 2011 27 Seznamy, rez Cvičení: append/2 appendC [], S, S ). % (1) append( [X|S1], S2, [X|S3] ) :- append( S1, S2, S3). % (2) :- append([1,2],[3,4],A). I (2) I A=[1|B] :- append([2],[3,4],B). I (2) | B=[2|C] => A=[1,2|C] :- append([],[3,4],C). | (1) | C=[3,4] => A=[1,2,3,4], yes Hana Rudová, Logické programování I, 13. května 2011 28 Seznamy, rez Cvičení: append/2 append( [], S, S ). % (1) append( [X|S1], S2, [X|S3] ) :- append( S1, S2, S3). % (2) :- append([1,2],[3,4],A). I (2) I A=[1|B] :- append([2],[3,4],B). I (2) | B=[2|C] => A=[1,2|C] :- append([],[3,4],C). | (1) | C=[3,4] => A=[1,2,3,4], yes Prědchudcě a naslědnik prvku X v seznamu S hledej(S,X,Pred,Po) :- append( _S1, [ Pred,X,Po | _S2 ], S) Hana Rudová, Logické programování I, 13. května 2011 28 Seznamy, rěz Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) append( S1, S2, S3). Napište následující predikáty pomocí append/3: Jí* prefix( S1, S2 ) :-DÚ: suffix(S1,S2) Hana Rudová, Logické programování I, 13. kvetna 2011 29 Seznamy, rez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) append( S1, S2, S3). Napište následující predikáty pomocí append/3: Jí* prefix( S1, S2 ) append( S1, _S3, S2). DÚ: suffix(S1,S2) Hana Rudová, Logické programování I, 13. kvetna 2011 29 Seznamy, rez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) :- append( S1, S2, S3). Napište následující predikáty pomocí append/3: Jí* prefix( S1, S2 ) :- append( S1, _S3, S2). DÚ: suffix(S1,S2) M last( X, S ) :- append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] Hana Rudová, Logické programování I, 13. kvetna 2011 29 Seznamy, rez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) append( S1, S2, S3). Napište následující predikáty pomocí append/3: Jí* prefix( S1, S2 ) append( S1, _S3, S2). DÚ: suffix(S1,S2) last( X, S ) append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] Hana Rudová, Logické programování I, 13. kvetna 2011 29 Seznamy, rez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) :- append( S1, S2, S3). Napište následůjící předikáty pomocí append/3: & prefix( S1, S2 ) :- append( S1, _S3, S2). DÚ: suffix(S1,S2) last( X, S ) :- append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] & member( X, S ) :- append([3,4,1], [2,6], [3,4,1,2,6]). X=2, S=[3,4,1,2,6] DÚ: adjacent(X,Y,S) Hana Růdová, Logické přogřamování I, 13. kvetna 2011 29 Seznamy, řez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) :- append( S1, S2, S3). Napište následující predikáty pomocí append/3: prefix( S1, S2 ) :- append( S1, _S3, S2). DÚ: suffix(S1,S2) last( X, S ) :- append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] & member( X, S ) :- append( S1, [X|S2], S ). append([3,4,1], [2,6], [3,4,1,2,6]). X=2, S=[3,4,1,2,6] DÚ: adjacent(X,Y,S) Hana Rudová, Logické programování I, 13. kvetna 2011 29 Seznamy, rez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) :- append( S1, S2, S3). Napište následující predikáty pomocí append/3: & prefix( S1, S2 ) :- append( S1, _S3, S2). DÚ: suffix(S1,S2) 1ast( X, S ) :- append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] & member( X, S ) :- append( S1, [X|S2], S ). append([3,4,1], [2,6], [3,4,1,2,6]). X=2, S=[3,4,1,2,6] DÚ: adjacent(X,Y,S) J£ % sub1ist(+S,+ASB) sub1ist(S,ASB) :- Hana Rudová, Logické programování I, 13. kvetna 2011 29 Seznamy, rez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) append( S1, S2, S3). Napište následující predikáty pomocí append/3: & prefix( S1, S2 ) append( S1, _S3, S2). DÚ: suffix(S1,S2) last( X, S ) append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] & member( X, S ) append( S1, [X|S2], S ). append([3,4,1], [2,6], [3,4,1,2,6]). X=2, S=[3,4,1,2,6] DÚ: adjacent(X,Y,S) J£ % sublist(+S,+ASB) sublist(S,ASB) append( AS, B, ASB ), append( A, S, AS ). POZOR na efektivitu, bez append lze casto napsat efektivneji Hana Rudová, Logické programování I, 13. kvetna 2011 29 Seznamy, rez Optimalizace posledního volaní Last Call Optimization (LCO) Implementacní technika snižující nároky na pamet' Mnoho vnorených rekurzivních volání je nárocné na pamet' Použití LCO umožnuje vnorenou rekurzi s konstantními pametovými nároky Typický príklad, kdy je možné použití LCO: A procedura musí mít pouze jedno rekurzivní volání: v posledním cíli poslední klauzule A cíle predcházející tomuto rekurzivnímu volání musí být deterministické -i> p( ... ) ... % žádné rekurzivní volání v těle klauzule p( ...):- ... % žádné rekurzivní volání v těle klauzule p(...) !, p( ... ). % rez zajišťuje determinismus & Tento typ rekurze lze převést na iteraci Hana Rudová, Logické programování I, 13. kvetna 2011 30 Seznamy, rez LCO a akumulátor -í* Reformulace rekurzivní procedury, aby umožnila LCO VýpoCet délky seznamu 1ength( Seznam, Delka ) 1ength( [], 0 ). 1ength( [ H | T ], Delka ) :- 1ength( T, DelkaO ), Delka is 1 + DelkaO. Hana Rudová, Logické programování I, 13. kvetna 2011 31 Seznamy, rez LCO a akumulátor -í* Rěformulacě rěkurzivní procědury, aby umožnila LCO & Výpocět délky sěznamu length( Seznam, Delka ) length( [], 0 ). length( [ H | T ], Delka ) :- length( T, DelkaO ), Delka is 1 + DelkaO. -í* Upravěná procědura, tak aby umožnila LCO: % length( Seznam, ZapocitanaDelka, CelkovaDelka ): % CelkovaDelka = ZapocitanaDelka + ,,poCet prvků v Seznam'' Hana Rudová, Logické programování I, 13. května 2011 31 Sěznamy, rěz LCO a akumulátor -í* Reformulace rekurzivní procedury, aby umožnila LCO & Výpocet délky seznamu length( Seznam, Delka ) length( [], 0 ). length( [ H | T ], Delka ) :- length( T, Delka0 ), Delka is 1 + Delka0. & Upravená procedura, tak aby umožnila LCO: % length( Seznam, ZapocitanaDelka, CelkovaDelka ): % CelkovaDelka = ZapocitanaDelka + ,,pocet prvku v Seznam'' length( Seznam, Delka ) :- length( Seznam, 0, Delka ). % pomocný predikát length( [], Delka, Delka ). % celková délka = zapocítaná délka length( [ H | T ], A, Delka ) :- A0 is A + 1, length( T, A0, Delka ). & Prídavný argument se nazývá akumulátor Hana Rudová, Logické programování I, 13. kvetna 2011 31 Seznamy, rez Akumulátor a sum_list(S,Sum) ?- sum_list( [2,3,4], Sum ). Hana Rudová, Logické programování I, 13. kvetna 2011 32 Seznamy, rez Akumulátor a sum_list(S,Sum) ?- sum_list( [2,3,4], Sum ). bez akumulátoru: sum_list( [], 0 ). sum_list( [H|T], Sum ) :- sum_list( T, SumT ), Sum is H + SumT. s akumulátorem: sum_list( S, Sum ) :- sum_list( S, 0, Sum ). sum_list( [], Sum, Sum ). sum_list( [H|T], A, Sum ) :- A1 is A + H, sum_list( T, A1, Sum). Hana Rudová, Logické programování I, 13. kvetna 2011 32 Seznamy, rez Výpočet faktoriálu fact(N,F) s akůmůlátořem: Hana Růdová, Logické přogřamování I, 13. kvetna 2011 33 Seznamy, řez Výpočet faktoriálu fact(N,F) s akumulátorěm: fact( N, F ) :- fact (N, 1, F ). fact( 1, F, F ) :- !. fact( N, A, F ) :- N > 1, A1 is N * A, N1 is N - 1, fact( N1, A1, F ). Hana Rudová, Logické programování I, 13. května 2011 33 Sěznamy, rěz r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). Přozkoůmejte třasy výpoctů a navřacení např. pomocí následůjících dotazů (vždy si středníkem vyžádejte navřacení): p(X):-write(p1). p(X):-a(X),b(X),l, (1) X=1,r(X). (3) X=0,r(X). (2) X=3,r(X). (4) X= -6,r(X). c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),l, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > 0, write(bl). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(cl). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(dl). d(X):- write(d2). Prozkoumejte trasy výpoctu a navracení nap r . pomocí následujících dotazu (vždy si středníkem vyžádejte navracení): (1) X=1,r(X). (3) X=0,r(X). (2) X=3,r(X). (4) X= -6,r(X). rez v predikátu p/1 neovlivní alternativy predikátu r/1 dokud nebyl proveden rez, alternativy predikátu a/1 se uplatnují, p r . neúspech b/1 v dotazu (3) p r i neúspechu cíle za rezem se výpocet navrací až k volající procedu r e r/1, viz (1) alternativy vzniklé po provedení rezu se zachovávají - další možnosti predikátu c/1 viz (2) a (4) Hana Rudová, Logické programování I, 13. kvetna 2011 34 Seznamy, rez r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pl). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > 0, write(bl). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(cl). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(dl). d(X):- write(d2). r(X)i-write(rl). r(X)i-p(X),write(r2). r(X)i-write(r3). pCX)i-write(pl). p(X)i-a(X),b(X),!, c(X),d(X),write(p2). p(X)i-write(p3). a(X)i-write(al). a(X)i-write(a2). b(X)i- X > O, write(bl). b(X)i- X < O, write(b2). c(X)i- X mod 2 =i= O, write(cl). c(X)i- X mod 3 =i= O, write(c2). j ľ- X=l,r(X). d(X)i- abs(X) < 1O, write(dl). d(X)i- write(d2). r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). | ?- X=1,r(X). r1 X = 1 ? ; I ?- X=1,r(X). r(X)i-writeCrl). r(X)i-p(X),write(r2). r(X):-write(r3). X= p1r2 r1 1 ? ■ X= p(X)i-write(p1). p(X)i-aCX),b(X),i, c(X),d(X),write(p2). p(X)i-write(p3). a(X)i-write(a1). a(X)i-write(a2). b(X)i- X > 0, write(bl). b(X)i- X < 0, write(b2). c(X)i- X mod 2 =:= 0, write(cl). c(X)i- X mod 3 =:= 0, write(c2). d(X)i- abs(X) < 10, write(dl). d(X)i- write(d2). r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pl). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > 0, write(bl). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(cl). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(dl). d(X):- write(d2). j ?- X=l,r(X). rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; r(X)i-write(rl). r(X)i-p(X),write(r2). r(X)i-write(r3). pCX)i-write(pl). p(X)i-a(X),b(X),!, c(X),d(X),write(p2). p(X)i-write(p3). a(X)i-write(al). a(X)i-write(a2). b(X)i- X > O, write(bl). b(X)i- X < O, write(b2). c(X)i- X mod 2 =i= O, write(cl). c(X)i- X mod 3 =i= O, write(c2). d(X)i- abs(X) < 1O, write(dl). d(X)i- write(d2). j ľ- X=l,r(X). rl X = 1 ľ ; plr2 X = 1 ľ ; alblr3 X = 1 ľ ; no r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),i, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > O, write(b1). b(X):- X < O, write(b2). c(X):- X mod 2 =:= O, write(c1). c(X):- X mod 3 =:= O, write(c2). d(X):- abs(X) < 1O, write(d1). d(X):- write(d2). | ľ- X=1,r(X). r1 X = 1 ľ ; p1r2 X = 1 ľ ; a1b1r3 X = 1 ľ ; no j ľ- X=O,r(X). r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). | ?- X=1,r(X). r1 X = 1 ? ; p1r2 X = 1 ? ; a1b1r3 X = 1 ? ; no | ?- X=0,r(X). r1 X = 0 ? ; r(X)i-write(r1). r(X):-p(X),write(r2). r(X)i-write(r3). p(X)i-write(p1). p(X)i-aCX),b(X),i, c(X),d(X),write(p2). p(X)i-write(p3). a(X)i-write(a1). a(X)i-write(a2). b(X)i- X > 0, write(bl). b(X)i- X < 0, write(b2). c(X)i- X mod 2 =i= 0, write(cl). c(X)i- X mod 3 =:= 0, write(c2). d(X)i- abs(X) < 10, write(dl). d(X)i- write(d2). I ?- X=1,r(X). rl X = 1 ? ; p1r2 X = 1 ? ; a1b1r3 X = 1 ? ; no I ?- X=0,r(X). r1 X = 0 ? ; p1r2 X = 0 ? ; r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pl). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > 0, write(bl). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(cl). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(dl). d(X):- write(d2). j ?- X=l,r(X). rl X = 1 ? i plr2 X = 1 ? i alblr3 X = 1 ? i no j ?- X=0,r(X). rl X = 0 ? i plr2 X = 0 ? i ala2p3r2 X = 0 ? i r(X)i-write(r1). r(X)i-p(X),write(r2). r(X)i-writeCrB). pCX)i-write(p1). pCX)i-aCX),bCX),!, c(X),d(X),write(p2). pCX)i-write(pB). a(X)i-writeCa1). a(X)i-writeCa2). b(X)i- X > O, write(b1). b(X)i- X < O, write(b2). c(X)i- X mod 2 =i= O, write(c1). c(X)i- X mod B =i= O, write(c2). d(X)i- abs(X) < 1O, write(d1). d(X)i- write(d2). j ľ- X=1,rCX). r1 X = 1 ľ i p1r2 X = 1 ľ i a1b1rB X = 1 ľ i no j ľ- X=O,r(X). r1 X = O ľ i p1r2 X = O ľ i a1a2pBr2 X = O ľ i rB X = O ľ i r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). I ľ- X=1,r(X). r1 X = 1 ľ i p1r2 X = 1 ľ i a1b1r3 X = 1 ľ i no I ľ- X=0,r(X). r1 X = 0 ľ i p1r2 X = 0 ľ i a1a2p3r2 X = 0 ľ i r3 X = 0 ľ i no r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). | ?- X=1,r(X). r1 X = 1 ? ; p1r2 | ?- X=3,r(X). X = 1 ? ; a1b1r3 X = 1 ? ; no | ?- X=0,r(X). r1 X = 0 ? ; p1r2 X = 0 ? ; a1a2p3r2 X = 0 ? ; r3 X = 0 ? ; no r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),i, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). | ľ- X=1,r(X). r1 X = 1 ľ i p1r2 | ľ- X=3,r(X). X = 1 ľ i r1 a1b1r3 X = 3 ľ i X = 1 ľ i no | ľ- X=0,r(X). r1 X = 0 ľ i p1r2 X = 0 ľ i a1a2p3r2 X = 0 ľ i r3 X = 0 ľ i no r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pl). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= O, write(cl). c(X):- X mod 3 =:= O, write(c2). d(X):- abs(X) < 1O, write(dl). d(X):- write(d2). j ľ- X=l,r(X). rl X = 1 ľ i plr2 X = 1 ľ i alblr3 X = 1 ľ i no j ľ- X=O,r(X). rl X = O ľ i plr2 X = O ľ i ala2p3r2 X = O ľ i r3 X = O ľ i no j ľ- X=3,r(X). rl X=3ľi plr2 X=3ľi r(X)i-write(r1). r(X):-p(X),write(r2). r(X)I-write(r3). p(X)i-write(p1). p(X)i-aCX),b(X),i, c(X),d(X),write(p2). p(X)I-write(p3). a(X)i-write(a1). a(X)i-write(a2). b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2). c(X)i- X mod 2 =i= 0, write(c1). c(X)i- X mod S =:= 0, write(c2). d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2). I ľ- X=1,r(X). r1 X = 1 ľ i p1r2 I ľ- X=S,r(X). X = 1 ľ i r1 a1b1rS X = S ľ i X = 1 ľ i p1r2 no X = S ľ i a1b1c2d1p2r2 I ľ- X=0,r(X). X = S ľ i r1 X = 0 ľ i p1r2 X = 0 ľ i a1a2pSr2 X = 0 ľ i rS X = 0 ľ i no r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). | ?- X=1,r(X). r1 X = 1 ? ; p1r2 | ?- X=3,r(X). X = 1 ? ; r1 a1b1r3 X = 3 ? ; X = 1 ? ; p1r2 no X = 3 ? ; a1b1c2d1p2r2 | ?- X=0,r(X). X = 3 ? ; r1 d2p2r2 X = 0 ? ; X = 3 ? ; p1r2 X = 0 ? ; a1a2p3r2 X = 0 ? ; r3 X = 0 ? ; no r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r5). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p5). a(X):-write(a1). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= O, write(cl). c(X):- X mod S =:= O, write(c2). d(X):- abs(X) < 1O, write(dl). d(X):- write(d2). j ľ- X=1,r(X). r1 X = 1 ľ i p1r2 j ľ- X=5,r(X). X = 1 ľ i r1 alblrS X = S ľ i X = 1 ľ i p1r2 no X = S ľ i a1b1c2d1p2r2 j ľ- X=O,r(X). X = S ľ i rl d2p2r2 X = O ľ i X = S ľ i p1r2 rS X = O ľ i X = S ľ i a1a2pSr2 X = O ľ i rS X = O ľ i no r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pl). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > 0, write(bl). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(cl). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(dl). d(X):- write(d2). j ?- X=l,r(X). rl X = 1 ? i plr2 X = 1 ? i alblr3 X = 1 ? i no j ?- X=0,r(X). rl X = 0 ? i plr2 X = 0 ? i ala2p3r2 X = 0 ? i r3 X = 0 ? i no j ?- X=3,r(X). rl X=3?i plr2 X=3?i alblc2dlp2r2 X=3?i d2p2r2 X=3?i r3 X=3?i no r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). I ľ- X=1,r(X). r1 X = 1 ľ i p1r2 X = 1 ľ i a1b1r3 X = 1 ľ i no I ľ- X=0,r(X). r1 X = 0 ľ i p1r2 X = 0 ľ i a1a2p3r2 X = 0 ľ i r3 X = 0 ľ i no I ľ- X= -6, r(X). I ľ- X=3,r(X). r1 X = 3 ľ i p1r2 X = 3 ľ i a1b1c2d1p2r2 X = 3 ľ i d2p2r2 X = 3 ľ i r3 X = 3 ľ i no r(X)i-write(r1). r(X)i-p(X),write(r2). r(X)i-writeCrB). pCX)i-write(p1). pCX)i-aCX),bCX),!, c(X),d(X),write(p2). pCX)i-write(pB). a(X)i-writeCa1). a(X)i-writeCa2). b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2). c(X)i- X mod 2 =i= 0, write(c1). c(X)i- X mod B =i= 0, write(c2). d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2). j ľ- X=1,rCX). r1 X = 1 ľ i p1r2 X = 1 ľ i a1b1rB X = 1 ľ i no j ľ- X=0,r(X). r1 X = 0 ľ i p1r2 X = 0 ľ i a1a2pBr2 X = 0 ľ i rB X = 0 ľ i no j ľ- X=B,r(X). r1 X = B ľ i p1r2 X = B ľ i a1b1c2d1p2r2 X = B ľ i d2p2r2 X = B ľ i rB X = B ľ i no j ľ- X= -6, r(X). r1 X = -6 ľ i r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pl). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= O, write(cl). c(X):- X mod 3 =:= O, write(c2). d(X):- abs(X) < 1O, write(dl). d(X):- write(d2). j ľ- X=l,r(X). rl X = 1 ľ i plr2 X = 1 ľ i alblr3 X = 1 ľ i no j ľ- X=O,r(X). rl X = O ľ i plr2 X = O ľ i ala2p3r2 X = O ľ i r3 X = O ľ i no j ľ- X=3,r(X). rl X=3ľi plr2 X=3ľi alblc2dlp2r2 X=3ľi d2p2r2 X=3ľi r3 X=3ľi no j ľ- X= -6, r(X). rl X = -6 ľ i plr2 X = -6 ľ i r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). | ?- X=1,r(X). r1 X = 1 ? ; p1r2 X = 1 ? ; a1b1r3 X = 1 ? ; no | ?- X=0,r(X). r1 X = 0 ? ; p1r2 X = 0 ? ; a1a2p3r2 X = 0 ? ; r3 X = 0 ? ; no | ?- X=3,r(X). r1 X=3?; p1r2 X=3?; a1b1c2d1p2r2 X=3?; d2p2r2 X=3?; r3 X=3?; no | ?- X= -6, r(X). r1 X = -6 ? ; p1r2 X = -6 ? ; a1b2c1d1p2r2 X = -6 ? ; r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),i, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). | ľ- X=1,r(X). r1 X = 1 ľ i p1r2 X = 1 ľ i a1b1r3 X = 1 ľ i no | ľ- X=0,r(X). r1 X = 0 ľ i p1r2 X = 0 ľ i a1a2p3r2 X = 0 ľ i r3 X = 0 ľ i no | ľ- X=3,r(X). r1 X=3ľi p1r2 X=3ľi a1b1c2d1p2r2 X=3ľi d2p2r2 X=3ľi r3 X=3ľi no | ľ- X= -G, r(X). r1 X = -G ľ i p1r2 X = -G ľ i a1b2c1d1p2r2 X = -G ľ i d2p2r2 X = -G ľ i r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). I ľ- X=1,r(X). r1 X = 1 ľ i p1r2 X = 1 ľ i a1b1r3 X = 1 ľ i no I ľ- X=0,r(X). r1 X = 0 ľ i p1r2 X = 0 ľ i a1a2p3r2 X = 0 ľ i r3 X = 0 ľ i no I ľ- X=3,r(X). r1 X = 3 ľ i p1r2 X = 3 ľ i a1b1c2d1p2r2 X = 3 ľ i d2p2r2 X = 3 ľ i r3 X = 3 ľ i no I ľ- X= -6, r(X). r1 X = -6 ľ i p1r2 X = -6 ľ i a1b2c1d1p2r2 X = -6 ľ i d2p2r2 X = -6 ľ i c2d1p2r2 X = -6 ľ i r(X)i-write(r1). r(X):-p(X),write(r2). r(X)I-write(r3). p(X)i-write(p1). p(X)i-aCX),b(X),i, c(X),d(X),write(p2). p(X)I-write(p3). a(X)i-write(a1). a(X)i-write(a2). b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2). c(X)i- X mod 2 =i= 0, write(c1). c(X)i- X mod S =:= 0, write(c2). d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2). I ľ- X=1,r(X). r1 X = 1 ľ i p1r2 X = 1 ľ i a1b1rS X = 1 ľ i no I ľ- X=0,r(X). r1 X = 0 ľ i p1r2 X = 0 ľ i a1a2pSr2 X = 0 ľ i rS X = 0 ľ i no I ľ- X=S,r(X). r1 X = S ľ i p1r2 X = S ľ i a1b1c2d1p2r2 X = S ľ i d2p2r2 X = S ľ i rS X = S ľ i no I ľ- X= -G, r(X). r1 X = -G ľ i p1r2 X = -G ľ i a1b2c1d1p2r2 X = -G ľ i d2p2r2 X = -G ľ i c2d1p2r2 X = -G ľ i d2p2r2 X = -G ľ i r(X)i-write(r1). r(X)i-p(X),write(r2). r(X)i-writeCrB). pCX)i-write(p1). pCX)i-aCX),bCX),!, c(X),d(X),write(p2). pCX)i-write(pB). a(X)i-writeCa1). a(X)i-writeCa2). b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2). c(X)i- X mod 2 =i= 0, write(c1). c(X)i- X mod B =i= 0, write(c2). d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2). j ľ- X=1,rCX). r1 X = 1 ľ i p1r2 X = 1 ľ i a1b1rB X = 1 ľ i no j ľ- X=0,r(X). r1 X = 0 ľ i p1r2 X = 0 ľ i a1a2pBr2 X = 0 ľ i rB X = 0 ľ i no j ľ- X=B,r(X). r1 X = B ľ i p1r2 X = B ľ i a1b1c2d1p2r2 X = B ľ i d2p2r2 X = B ľ i rB X = B ľ i no j ľ- X= -6, r(X). r1 X = -6 ľ i p1r2 X = -6 ľ i a1b2c1d1p2r2 X = -6 ľ i d2p2r2 X = -6 ľ i c2d1p2r2 X = -6 ľ i d2p2r2 X = -6 ľ i rB X = -6 ľ i r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). Hana Rudová, Logické programování I, 13. kvetna 2011 | ?- X=1,r(X). r1 X = 1 ? ; p1r2 | ?- X=3,r(X). X = 1 ? ; r1 a1b1r3 X = 3 ? ; X = 1 ? ; p1r2 no X = 3 ? ; a1b1c2d1p2r2 | ?- X=0,r(X). X = 3 ? ; r1 d2p2r2 X = 0 ? ; X = 3 ? ; p1r2 r3 X = 0 ? ; X = 3 ? ; a1a2p3r2 no X = 0 ? ; r3 X = 0 ? ; no 35 | ?- X= -6, r(X). r1 X = -6 ? ; p1r2 X = -6 ? ; a1b2c1d1p2r2 X = -6 ? ; d2p2r2 X = -6 ? ; c2d1p2r2 X = -6 ? ; d2p2r2 X = -6 ? ; r3 X = -6 ? ; no Seznamy, rez Řez: maximum Je tato definice predikátu max/3 korektní? max(X,Y,X):-X>=Y,l. max(X,Y,Y). Hana Rudová, Logické programování I, 13. kvetna 2011 36 Seznamy, rez Rez: maximum Je tato definice predikátu max/3 korektní? max(X,Y,X):-X>=Y,l. max(X,Y,Y). Není, následující dotaz uspeje: ?- max(2,1,1). Uved'te dve možnosti opravy, se zachováním použití r ezu a bez. Hana Rudová, Logické programování I, 13. kvetna 2011 36 Seznamy, rez Řez: maximum Je tato definice predikátu max/3 korektní? max(X,Y,X):-X>=Y,!. max(X,Y,Y). Není, následující dotaz uspeje: ?- max(2,1,1). Uved'te dve možnosti opravy, se zachováním použití r ezu a bez. max(X,Y,X):-X>=Y. max(X,Y,Z):-X>=Y,!,Z=X. max(X,Y,Y):-Y>X. max(X,Y,Y). Problém byl v definici, v první klauzuli se tvrdilo: X=Z a X>=Y => true správná definice je: X>=Y => Z=X Pr i použití r ezu je tr eba striktne oddelit vstupní podmínky od výstupních unifikací a výpoctu. Hana Rudová, Logické programování I, 13. kvetna 2011 36 Seznamy, rez Řez: member Jaký je rozdíl mezi následujícími definicemi predikátů member/2. Ve kterých odpovědích se budou lišit? Vyzkoušejte napr. pomocí member( X, [1,2,3] ). mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(H,T). mem2(H,[H|_]) :- !. mem3(H,[K|_]) :- H==K. mem2(H,[_|T]) :- mem2(H,T). mem3(H,[K|T]) :- H\==K, mem3(H,T). Hana Rudová, Logické programování I, 13. května 2011 37 Seznamy, rez Rez: member Jaký je rozdíl mezi následujícími definicemi predikátů member/2. Ve kterých odpovědích se budou lišit? Vyzkoušejte nap r . pomocí member( X, [1,2,3] ). mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(H,T). mem2(H,[H|_]) :- !. mem3(H,[K|_]) :- H==K. mem2(H,[_|T]) :- mem2(H,T). mem3(H,[K|T]) :- H\==K, mem3(H,T). & meml/2 vyhledá všechny výskyty, p r i porovnávání hledaného prvku s prvky seznamu muže dojít k vázání promenných (může sloužit ke generování všech prvků seznamu) Hana Rudová, Logické programování I, 1S. kvetna 2O11 S7 Seznamy, rez Rez: member Jaký je rozdíl mezi následujícími definicemi predikátu member/2. Ve kterých odpovědích se budou lišit? Vyzkoušejte napr. pomocí member( X, [1,2,3] ). mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(H,T). mem2(H,[H|_]) :- !. mem3(H,[K|_]) :- H==K. mem2(H,[_|T]) :- mem2(H,T). mem3(H,[K|T]) :- H\==K, mem3(H,T). & mem1/2 vyhledá všechny výskyty, pri porovnávání hledaného prvku s prvky seznamu muže dojít k vázání promenných (může sloužit ke generování všech prvků seznamu) -í* mem2/2 najde jenom první výskyt, taky váže promenné Hana Rudová, Logické programování I, 13. kvetna 2011 37 Seznamy, rez Rez: member Jaký je rozdíl mezi následujícími definicemi predikátů member/2. Ve kterých odpovedích se budou lišit? Vyzkoušejte nap r . pomocí member( X, [1,2,3] ). mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(H,T). mem2(H,[H|_]) !. mem3(H,[K|_]) H==K. mem2(H,[_|T]) mem2(H,T). mem3(H,[K|T]) H\==K, mem3(H,T). & mem1/2 vyhledá všechny výskyty, p r i porovnávání hledaného prvku s prvky seznamu muže dojít k vázání promenných (může sloužit ke generování všech prvků seznamu) -í* mem2/2 najde jenom první výskyt, taky váže promenné & mem3/2 najde jenom první výskyt, promenné neváže (hledá pouze identické prvky) Dokážete napsat variantu, která hledá jenom identické prvky a p r itom najde všechny výskyty? Hana Rudová, Logické programování I, 13. kvetna 2011 37 Seznamy, rez Rez: member Jaký je rozdíl mezi následujícími definicemi predikátu member/2. Ve kterých odpovedích se budou lišit? Vyzkoušejte napr. pomocí member( X, [1,2,3] ). mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(H,T). mem2(H,[H|_]) :- !. mem3(H,[K|_]) :- H==K. mem2(H,[_|T]) :- mem2(H,T). mem3(H,[K|T]) :- H\==K, mem3(H,T). & mem1/2 vyhledá všechny výskyty, pri porovnávání hledaného prvku s prvky seznamu muže dojít k vázání promenných (může sloužit ke generování všech prvků seznamu) -í* mem2/2 najde jenom první výskyt, taky váže promenné -i* mem3/2 najde jenom první výskyt, promenné neváže (hledá pouze identické prvky) Dokážete napsat variantu, která hledá jenom identické prvky a pritom najde všechny výskyty? mem4(H,[K|_]) :- H==K. mem4(H,[K|T]):- mem4(H,T). Hana Rudová, Logické programování I, 13. kvetna 2011 37 Seznamy, rez Rez: delete delete( X, [X|S], S ). delete( X, [Y|S], [Y|S1] ) :- delete(X,S,S1). Napište predikát delete(X,S,S1), který odstraní všechny výskyty X (pokud se X v S nevyskytuje, tak predikát uspeje). Hana Rudová, Logické programování I, 13. kvetna 2011 38 Seznamy, rez Řez: delete delete( X, [X|S], S ). delete( X, [Y|S], [Y|S1] ) :- delete(X,S,S1). Napište predikát delete(X,S,S1), který odstraní všechny výskyty X (pokud se X v S nevyskytuje, tak predikát uspeje). delete( _X, [], [] ). delete( X, [X|S], S1 ) :- !, delete(X,S,S1). delete( X, [Y|S], [Y|S1] ) :- delete(X,S,S1). Hana Rudová, Logické programování I, 13. kvetna 2011 38 Seznamy, rez Seznamy: intersection(A,B,C) DÚ: Napište predikát pro výpoCět průniku dvou sěznamU. Nápověda: využijte predikát měmběr/2 DÚ: Napiště prědikát pro výpoCtu rozdílu dvou sěznamU. Nápověda: využijtě prědikát měmběr/2 Hana Rudová, Logické programování I, 13. května 2011 39 Sěznamy, rěz 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). 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,Prijnieni,S,V,Pr,F) , L ). Najdete jméno a p rí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, 13. kvetna 2011 41 Všechna řešení, t rídení, rozdílové seznamy Všechna reš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). Hana Rudová, Logické programování I, 13. kvetna 2011 42 Všechna rešení, trídení, rozdílové seznamy Všechna rešení Kolik žen a mužu je v databázi? ?- findall( c(PO), 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, 13. kvetna 2011 42 Všechna rešení, t rí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é programování I, 13. kvetna 2011 42 Všechna rešení, t rídení, rozdílové seznamy Všechna řešení: p ř íklady 1. Jaká jsou p r íjmení všech žen? 2. Kte rí lidé mají více než 30 roků? Naleznete jejich jméno a p ríjmení 3. Naleznete abecedne se razený seznam všech lidí. 4. Naleznete p ríjmení vyucujících ze zs_stara. 5. Jsou v databázi dva brat r i (mají stejné p r íjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zamestnance? Hana Rudová, Logické programování I, 13. kvetna 2011 43 Všechna řešení, t rídení, rozdílové seznamy Všechna řešení: příklady 1. Jaká jsou příjmení všech žen? 2. Kterí lidé mají více než 30 roku? Naleznete jejich jméno a príjmení 3. Naleznete abecedne serazený seznam všech lidí. 4. Naleznete príjmení vyucujících ze zs_stara. 5. Jsou v databázi dva bratri (mají stejné prí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). Hana Rudová, Logické programování I, 13. kvetna 2011 43 Všechna rešení, t rídení, rozdílové seznamy Všechna řešení: příklady 1. Jaká jsou p r íjmení všech žen? 2. Kte rí lidé mají více než 30 rokU? Naleznete jejich jméno a p ríjmení. 3. Naleznete abecedne se razený seznam všech lidí. 4. Naleznete p ríjmení vyucujících ze zs_stara. 5. Jsou v databázi dva brat r i (mají stejné p r íjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zamestnance? 1. findall(Prijmeni, z(_,Prijmeni,z,_,_,_), L). 2. findallOmeno-Prijmeni, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). Hana Rudová, Logické programování I, 13. kvetna 2011 43 Všechna řešení, t rídení, rozdílové seznamy Všechna rešení: príklady 1. Jaká jsou príjmení všech žen? 2. Kterí lidé mají více než 30 roků? Naleznete jejich jméno a príjmení. 3. Naleznete abecedne serazený seznam všech lidí. 4. Naleznete príjmení vyucujících ze zs_stara. 5. Jsou v databázi dva bratri (mají stejné príjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zamestnance? 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, 13. kvetna 2011 43 Všechna rešení, t rídení, rozdílové seznamy Všechna řešení: příklady 1. Jaká jsou príjmění všěch žěn? 2. Ktěrí lidé mají vícě něž 30 roku? Nalěznětě jějich jméno a príjmění. 3. Nalěznětě aběcědně sěrazěný sěznam všěch lidí. 4. Nalěznětě príjmění vyucujících zě zs_stara. 5. Jsou v databázi dva bratri (mají stějné príjmění a různá jména)? 6. Ktěré firmy v databázi mají vícě něž jědnoho zaměstnancě? 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 ). 4. findall(Prijmeni, ( z(_,Prijmeni,_,_,P,zs_stara), (P=ucitel;P=ucitelka) ), L). Hana Rudová, Logické programování I, 13. května 2011 43 Všěchna rěšění, třídění, rozdílové sěznamy Všechna rešení: príklady 1. Jaká jsou p r íjmení všech žen? 2. Kte rí lidé mají více než 30 roků? Naleznete jejich jméno a p ríjmení. 3. Naleznete abecedne se razený seznam všech lidí. 4. Naleznete p ríjmení vyucujících ze zs_stara. 5. Jsou v databázi dva brat r i (mají stejné p r íjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zamestnance? 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 ). 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, 13. kvetna 2011 43 Všechna rešení, t rídení, rozdílové seznamy bubblesort(S,Sorted) Seznam S se rad'te tak, že naleznete první dva sousední prvky X a Y v S tak, že X>Y, vymente po radí X a Y a získate S1; a se rad'te S1 pokud neexistuje žádný takový pár sousedních prvku X a Y, pak je S se razený seznam swap(S,S1) rekurzivne bubblesortem bubblesort(S,Sorted) :- swap (S,S1), !, bubblesort(S1, Sorted). bubblesort(Sorted,Sorted). % Existuje použitelný swap v S? % Jinak je seznam serazený swap([X,Y|Rest],[Y,X|Rest1]) :-X>Y. swap([X|Rest],[X|Rest1]) :-swap(Rest,Rest1). % swap prvních dvou prvků % nebo obecněji X@>Y, resp. gt(X,Y) % swap prvků až ve zbytku Hana Rudová, Logické programování I, 13. kvetna 2011 44 Všechna rešení, t rídení, rozdílové seznamy quicksort(S,Sorted) Neprázdný seznam S se rad'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 konec rekurze pro S=[] nap r . vyberte hlavu S split(X,Seznam,Small,Big) se rad'te Small do SortedSmall rekurzivne quicksortem se rad'te Big do SortedBig rekurzivne quicksortem set rídený seznam vznikne spojením SortedSmall a [X|SortedBig] append Hana Rudová, Logické programování I, 13. kvetna 2011 45 Všechna rešení, t rídení, rozdílové seznamy quicksort(S,Sorted) Neprázdný seznam S se rad'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> se rad'te Small do SortedSmall & se rad'te Big do SortedBig & set rídený seznam vznikne spojením SortedSmall a [XjSortedBig] konec rekurze pro S=[] nap r . 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, 13. kvetna 2011 45 Všechna rešení, t rídení, rozdílové seznamy quicksort(S,Sorted) Něprázdný sěznam S sěrad'tě tak, žě & vyběrtě nějaký prvěk X z S; rozděltě zbytěk S na dva sěznamy Small a Big tak, žě: v Big jsou větší prvky něž X a v Small jsou zbývající prvky J5> sěrad'tě Small do SortědSmall & sěrad'tě Big do SortědBig & sětríděný sěznam vznikně spojěním SortědSmall a [X|SortědBig] konec rekurze pro S=[] nap r. 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, 13. května 2011 45 Všechna řěšění, třídění, rozdílové sěznamy DÚ:insertsort(S,Sorted) Neprázdný seznam S=[X|T] se rad'te tak, že & se rad'te telo T seznamu S JS> vložte hlavu X do se razeného tela tak, že výsledný seznam je zase se razený. Víme: výsledek po vložení X je celý se razený seznam. konec rekurze pro S=[] rekurzivne insertsortem insert(X,SortedT,Sorted) Hana Rudová, Logické programování I, 13. kvetna 2011 46 Všechna rešení, t rídení, rozdílové seznamy DÚ:insertsort(S,Sorted) Neprázdný seznam S=[X|T] serad'te tak, že konec rekurze pro S=[] serad'te telo T seznamu S vložte hlavu X do serazeného tela tak, že výsledný seznam je zase serazený. Víme: výsledek po vložení X je celý serazený 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é programování I, 13. kvetna 2011 46 Všechna řešení, trídení, 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 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é programování I, 13. kvetna 2011 47 [1,2,3,4,5]-[] ). Všechna rešení, t rídení, 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í I, 13. kvetna 2011 48 Všechna rešení, t rídení, rozdílové seznamy reverseCSeznam, Opacny) % kvadratická složitost reverseC [], [] )■ reverseC [H j T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). % lineární složitost, rozdílové seznamy reverseC Seznam, Opacny ) :- reverse0C Seznam, ). reverse0C [], )■ reverse0C [ H j T ], ) :- reverse0C T, ). Hana Rudová, Logické programování I, 13. kvetna 2011 48 Všechna rešení, t rídení, rozdí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, Opacny-[] ). reverse0( [], S-S ). reverse0( [ H | T ], Opacny-OpacnyKonec ) :- reverse0( T, Opacny-[ H | OpacnyKonec] ). Hana Rudová, Logické programování I, 13. kvetna 2011 48 Všechna reš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; 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í* se rad'te Small do SortedSmall & se rad'te Big do SortedBig C set rí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, 13. kvetna 2011 49 Všechna reš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; 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í* se rad'te Small do SortedSmall & se rad'te Big do SortedBig C set rídený seznam vznikne spojením SortedSmall a [X|SortedBig] quicksort(S, Sorted) :- quicksort1(S,Sorted-[]). quicksort1([],Z-Z). quicksort1([X|T]l 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, 13. kvetna 2011 49 Všechna rešení, t rídení, rozdílové seznamy DÚ: palindrom(L) Napiště prědikát palindrom(Sěznam), ktěrý uspějě pokud sě Sěznam ctě stějně zězadu i zěp r ědu, p r . [a,b,c,b,a] něbo [12,15,1,1,15,12] Hana Rudová, Logické programování I, 13. května 2011 50 Všěchna rěšění, t rídění, rozdílové sěznamy DÚ: palindrom(L) Napište predikát palindrom(Seznam), který uspeje pokud se Seznam cte stejne zezadu i zep r edu, p r . [a,b,c,b,a] nebo [12,15,1,1,15,12] palindrom(Seznam) :- reverse(Seznam,Seznam). Hana Rudová, Logické programování I, 13. kvetna 2011 50 Všechna rešení, t rídení, rozdílové seznamy Vstup/výstup, databázové operace, rozklad termu Ctení ze process_file( Soubor ) :- seeing( StarySoubor ), see( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_file, i seen see( StarySoubor ). repeat. repeat :- repeat. souboru % zjištění aktivního proudu % otevrení souboru Soubor % ctění termu Term % manipulace s termem % je konec souboru? % uzavrení souboru % aktivace puvodního proudu % vestavený predikát Hana Rudová, Logické programování I, 13. května 2011 52 Vstup/výstup, databázové opěracě, rozklad těrmu Predikáty pro vstup a výstup | ?- read(A), read( ahoj(B) ), read( [C,D] ). |: ahoj. ahoj( petre ). [ ahoj( 'Petre!' ), jdeme ]. A = ahoj, B = petre, C = ahoj('Petre!'), D = jdeme | ?- write(a(1)), write('.'), nl, write(a(2)), write('.'), nl. a(1). a(2). yes C- seeing, see, seen, read -í* telling, tell, told, write -i* standardní vstupní a výstupní stream: user Hana Rudová, Logické programování I, 13. kvetna 2011 53 Vstup/výstup, databázové operace, rozklad termu Příklad: vstup/výstup Napište predikát u1oz_do_souboru( Soubor ), který nacte několik fakt ze vstupu a uloží je do souboru Soubor. | ?- u1oz_do_souboru( 'soubor.pl' ). |: fakt(mirek, 18). |: fakt(pave1,4). |: end_of_fi1e. yes | ?- consult(soubor). % consulting /home/hanka/soubor.pl... % consulted /home/hanka/soubor.pl in module user, 0 msec % 376 bytes yes | ?- 1isting(fakt/2). % pozor:1isting/1 lze použít pouze pri consult/1 (ne u compile/1) fakt(mirek, 18). fakt(pave1, 4). yes Hana Rudová, Logické programování I, 13. kvetna 2011 54 Vstup/výstup, databázové operace, rozklad termu Implementace: vstup/výstup uloz_do_souboru( Soubor ) :-seeing( StaryVstup ), telling( StaryVystup ), see( user ), tell( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_file, i ■ > seen, told, tell( StaryVystup ), see( StaryVstup ). process_term(end_of_file) :- !. process_term( Term ) :- write( Term ), write('.'), nl. Hana Rudová, Logické programování I, 13. kvetna 201 1 5 5 Vstup/výstup, databázové operace, rozklad termu Databázové operace & Databáze: specifikace množiny relací & Prologovský program: programová databáze, kde jsou relace specifikovány explicitne (fakty) i implicitne (pravidly) JS> Vestavené predikáty pro zmenu databáze behem provádení programu: assertz( Klauzule ) p r idání na konec retract( Klauzule ) smazání klauzule unifikovatelné s Klauzule JS> Pozor: retract/1 lze použít pouze pro dynamické klauzule (p r idané pomocí assert) a ne pro statické klauzule z programu -i* Pozor: nadmerné použití techto operací snižuje srozumitelnost programu assert( Klauzule ) asserta( Klauzule ) p r idání Klauzule do programu p r idání na zacátek Hana Rudová, Logické programování I, 13. kvetna 2011 56 Vstup/výstup, databázové operace, rozklad termu Databázové operace: příklad Napište predikát vytvor_program/0, který nacte nekolik klauzulí ze vstupu a uloží je do programové databáze. | ?- vytvor_program. |: fakt(pavel, 4). |: pravidlo(X,Y) :- fakt(X,Y). |: end_of_file. yes | ?- listing(fakt/2). fakt(pavel, 4). yes | ?- listing(pravidlo/2). pravidlo(A, B) :- fakt(A, B), yes | ?- clause( pravidlo(A,B), C). % clause/2 použitelný pouze pro dynamické klauzule C = fakt(A,B) ? yes Hana Rudová, Logické programování I, 13. kvetna 2011 57 Vstup/výstup, databázové operace, rozklad termu Databázové operace: implementace vytvor_program :- seeing( StaryVstup ), see( user ), repeat, read( Term ), uloz_term( Term ), Term == end_of_file, i ■ > seen, see( StaryVstup ). uloz_term( end_of_file ) :- !. uloz_term( Term ) :- assert( Term ). Hana Rudová, Logické programování I, 13. kvetna 2011 58 Vstup/výstup, databázové operace, rozklad termu Konstrukce a dekompozice termu -í* Konstrukce a dekompozice termu Term =.. [ Funktor | SeznamArgumentu ] a(9,e) =.. [a,9,e] Cil =.. [ Funktor | SeznamArgumentu ], call( Cil ) atom =.. X => X = [atom] & Pokud chci znát pouze funktor nebo nekteré argumenty, pak je efektivnejší: functor( Term, Funktor, Arita ) functor( a(9,e), a, 2 ) functor(atom,atom,0) i functor(1,1,0) arg( 2, a(9,e), e) arg( N, Term, Argument ) Hana Rudová, Logické programování I, 13. května 2011 59 Vstup/výstup, databázové operace, rozklad termu Rekurzivní rozklad termu -i* Term je seznam ([_|_]) => procházení seznamu a rozklad každého prvku seznamu ii> Term je složený (=../2, functor/3) => procházení seznamu argumentu a rozklad každého argumentu JS> Príklad: ground/1 uspeje, pokud v termu nejsou promenné; jinak neuspeje ground(Term) :- atomic(Term), !. % Term je atom nebo císlo NEBO ground(Term) :- var(Term), !, fail. % Term není promenná NEBO ground([H|T]) :- !, ground(H), ground(T). % Term je seznam a ani hlava ani telo % neobsahují promenné NEBO ground(Term) :- Term =.. [ _Funktor | Argumenty ], % je Term složený ground( Argumenty ). % a jeho argumenty % neobsahují promenné ?- ground(s(2,[a(1,3),b,c],X)). ?- ground(s(2,[a(1,3),b,c])). Hana no Rudová, Logické programování I, 13. kvetna 2011 60 yes Vstup/výstup, databázové operace, rozklad termu subterm(S,T) Napište predikát subterm(S,T) pro termy S a T bez promenných, které uspejí, pokud je S podtermem termu T. Tj. musí platit alespon jedno z & podterm S je práve term T NEBO podterm S se nachází v hlave seznamu T NEBO podterm S se nachází v tele seznamu T NEBO JS> T je složený term (compound/1) a S je podtermem nekterého argumentu T & otestujte :- subterm(1,2). pokud nepoužijeme (compound/1), pak tento dotaz cyklí otestujte :- subterm(a,[1,2]). ove r te, zda necyklí (nutný cervený rez níže) | ?- subterm(sin(3),b(c,2,[1,b],sin(3),a)). yes Hana Rudová, Logické programování I, 13. kvetna 2011 61 Vstup/výstup, databázové operace, rozklad termu subterm(S,T) Napište predikát subterm(S,T) pro termy S a T bez proměnných, které uspejí, pokud je S podtermem termu T. Tj. musí platit alespon jedno z & podterm S je práve term T NEBO podterm S se nachází v hlave seznamu T NEBO podterm S se nachází v tele seznamu T NEBO JS> T je složený term (compound/1) a S je podtermem nekterého argumentu T J> otestujte :- subterm(1,2). pokud nepoužijeme (compound/1), pak tento dotaz cyklí otestujte :- subterm(a,[1,2]). ove r te, zda necyklí (nutný cervený r ez níže) | ?- subterm(sin(3),b(c,2,[1,b],sin(3),a)). yes subterm(T,T) :- 1. subterm(S,[H|_]) :- subterm(S,H), 1. subterm(S,[_|T]) :- !, subterm(S,T). subterm(S,T) :- compound(T), T=..[_|Argumenty], subterm(S,Argumenty). Hana Rudová, Logické programování I, 13. kvetna 2011 61 Vstup/výstup, databázové operace, rozklad termu same(A,B) Napiště prědikát same(A,B), ktěrý uspějě, pokud mají těrmy A a B stějnou strukturu. Tj. musí platit právě jědno z JS* A i B jsou proměnné NEBO pokud jě jěděn z arguměntu proměnná (druhý ně), pak prědikát něuspějě, NEBO JS* A i B jsou atomic a unifikovatělné NEBO & A i B jsou sěznamy, pakjakjějich hlava tak jějich tělo mají stějnou strukturu NEBO & A i B jsou složěné těrmy sě stějným funktorěm a jějich arguměnty mají stějnou strukturu | ?- same([1,3,sin(X),s(a,3)],[1,3,sin(X),s(a,3)]). yes Hana Rudová, Logické programování I, 13. května 2011 62 Vstup/výstup, databázové opěracě, rozklad těrmu same(A,B) Napište predikát same(A,B), který uspeje, pokud mají termy A a B stejnou strukturu. Tj. musí platit práve jedno z JS* A i B jsou promenné NEBO pokud je jeden z argumentů promenná (druhý ne), pak predikát neuspeje, NEBO Jl> A i B jsou atomic a unifikovatelné NEBO -Ä* A i B jsou seznamy, pak jak jejich hlava tak jejich telo mají stejnou strukturu NEBO J5> A i B jsou složené termy se stejným funktorem a jejich argumenty mají stejnou strukturu | ?- same([1,3,sin(X),s(a,3)],[1,3,sin(X),s(a,3)]). yes same(A,B) :- var(A), var(B), 1. same(A,B) :- var(A), 1, fail. same(A,B) :- var(B), 1, fail. same(A,B) :- atomic(A), atomic(B), 1, A==B. same([HA|TA],[HB|TB]) :- 1, same(HA,HB), same(TA,TB). same(A,B) :- A=..[F|ArgA], B=..[F|ArgB], same(ArgA,ArgB). Hana Rudová, Logické programování I, 13. kvetna 2011 62 Vstup/výstup, databázové operace, rozklad termu D.Ú. unify(A,B) Napište predikát unify(A,B), který unifikuje termy A a B a provede zároven kontrolu výskytu pomocí not_occurs(Var,Term). | ?- unify([Y,3,sin(a(3)),s(a,3)],[1,3,sin(X),s(a,3)]). X = a(3) Y = 1 yes Hana Rudová, Logické programování I, 13. kvetna 2011 63 Vstup/výstup, databázové operace, rozklad termu D.Ú. unify(A,B) Napište predikát unify(A,B), který unifikuje termy A a B a provede zároveň kontrolu výskytu pomocí not_occurs(Var,Term). | ?- unify([Y,3,sin(a(3)),s(a,3)],[1,3,sin(X),s(a,3)]). X = a(3) Y = 1 yes unify(A,B) :- var(A), var(B), I, A=B. unify(A,B) :- var(A), I, not_occurs(A,B), A=B. unify(A,B) :- var(B), I, not_occurs(B,A), B=A. unify(A,B) :- atomic(A), atomic(B), I, A==B. unify([HA|TA],[HB|TB]) :- I, unify(HA,HB), unify(TA,TB). unify(A,B) :- A=..[F|ArgA], B=..[F|ArgB], unify(ArgA,ArgB). Hana Rudová, Logické programování I, 13. kvetna 2011 63 Vstup/výstup, databázové operace, rozklad termu not_occurs(A,B) Predikát not_occurs(A,B) uspeje, pokud se promenná A nevyskytuje v termu B. Tj. platí jedno z & B je atom nebo císlo NEBO JS> B je promenná různá od A NEBO & B je seznam a A se nevyskytuje ani v tele ani v hlave NEBO B je složený term a A se nevyskytuje v jeho argumentech Hana Rudová, Logické programování I, 13. kvetna 2011 64 Vstup/výstup, databázové operace, rozklad termu not_occurs(A,B) Predikát not_occurs(A,B) uspeje, pokud se promenná A nevyskytuje v termu B. Tj. platí jedno z & B je atom nebo Číslo NEBO JS> B je promenná různá od A NEBO & B je seznam a A se nevyskytuje ani v tele ani v hlave NEBO B je složený term a A se nevyskytuje v jeho argumentech not_occurs(_,B) :- atomic(B), !. not_occurs(A,B) :- var(B), !, A\==B. not_occurs(A,[H|T]) :- !, not_occurs(A,H), not_occurs(A,T). not_occurs(A,B) :- B=..[_|Arg], not_occurs(A,Arg). Hana Rudová, Logické programování I, 13. kvetna 2011 64 Vstup/výstup, databázové operace, rozklad termu Logické programování s omezujícími podmínkami Algebrogram Pr i rad'te cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: SEND + MORE MONEY M mzná písmena mají p r i razena různé cifry & S a M nejsou 0 Promenné: S,E,N,D,M,O,R,Y Domény: [1..9] pro S,M [0..9] pro E,N,D,O,R,Y 1 omezení pro nerovnost: all_distinct([S,E,N,D,M,O,R,Y]) 1 omezení pro rovnosti: 1000*S + 100*E + 10*N + D + 1000*M + 100*0 + 10*R + E #= 10000*M + 1000*0 + 100*N + 10*E + Y Hana Rudová, Logické programování I, 13. kvetna 2011 66 SEND + MORE M0NEY Omezující podmínky Jazykové prvky Nalezněte r ešení pro algebrogram DONALD + GERALD = ROBERT Struktura programu algebrogram( [D,O,N,A,L,G,E,R,B,T] ) :-domain(...), all_distinct(...), ... #= labelingC...). % domény proměnných % omezení % prohledávání stavového prostoru Knihovna pro CLP(FD) :- usě_modulě(líbrary(clpfd)). Domény promenných domaín( Seznam, MínValuě, MaxValuě ) Omezení all_dístínct( Seznam ) C Aritmetické omezení A*B + C #= D Procedura pro prohledávání stavového prostoru labělíng([],Sěznam) Hana Rudová, Logické programování I, 13. kvetna 2011 67 Omezující podmínky rešení :- use_module(library(clpfd)). donald(LD):- % domény LD=[D,0,N,A,L,G,E,R,B,T], domaín(LD,0,9), domaín([D,G,R],1,9), % omezení all_distinct(LD), 100000*D + 10000*0 + 1000*N + 100*A + 10*L + D + 100000*G + 10000*E + 1000*R + 100*A + 10*L + D #= 100000*R + 10000*0 + 1000*B + 100*E + 10*R + T, % prohledávání stavového prostoru labelíng([],LD). Hana Rudová, Logické programování I, 13. kvetna 2011 68 Omezující podmínky Disjunktivní rozvrhování (unární zdroj) -í* cumu1ative([task(Start, Duration, End, 1, Id) | Tasks]) -í* Rozvržění úloh zadaných startovním a koncovým Casěm (Start,End), dobou trvání (nezáporné Duration) a iděntifikátorěm (Id) tak, aby sě něp r ěkrývaly Hana Rudová, Logické programování I, 13. května 2011 69 Omězující podmínky Disjunktivní rozvrhování (unární zdroj) cumulative([task(Start, Duration, End, 1, Id) | Tasks]) Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nep r ekrývaly -fc p r íklad s konstantami: cumulative([task(0,2,2,1,1), task(3,1,4,1,2), task(5,1,6,1,3)]) Start, Duration, End, Id musí být doménové proměnné s konečnými mezemi nebo čelá čísla Hana Rudová, Logické programování I, 13. kvetna 2011 69 Omezující podmínky Plánování Každý úkol má stanoven dobu trvání a nejd rívejší cas, kdy muže být zahájen. Naleznete startovní cas každého úkolu tak, aby se jednotlivé úkoly nep r ekrývaly. Úkolyjsou zadány následujícím zpusobem: % ukol(Id,Doba,MinStart,MaxKonec) ukol(1,4,8,70). ukol(2,2,7,60). ukol(5,4,1,45). ukol(6,2,4,35). ukol(9,1,8,40). ukol(10,7,4,50). ukol(3,1,2,25). ukol(7,8,2,25). ukol(11,5,2,50). ukol(4,6,5,55). ukol(8,5,0,20). ukol(12,2,0,35). ukol(13,3,30,60). ukol(14,5,15,70). ukol(15,4,10,40). Kostra r ešení: ukoly(Zacatky) :- domeny(l)koly,Zacatky,Tasks), cumulative(Tasks), labeling([],Zacatky). domeny(lkoly,Zacatky,Tasks) :- findall(ukol(Id,Doba,MinStart,MaxKonec), ukol(Id,Doba,MinStart,MaxKonec), Ikoly), nastav_domeny(lkoly,Zacatky,Tasks). Hana Rudová, Logické programování I, 13. kvetna 2011 70 Omezující podmínky Plánování: výstup tiskni(Uko1y,Zacatky) :- priprav(Uko1y,Zacatky,Vstup), quicksort(Vstup,Vystup), nl, tiskni(Vystup). priprav([],[],[]). priprav([uko1(Id,Doba,MinStart,MaxKonec)|Uko1y], [Z|Zacatky], [uko1(Id,Doba,MinStart,MaxKonec,Z)|Vstup]) :-priprav(Uko1y,Zacatky,Vstup). tiskni([]) :- nl. tiskni([V|Vystup]) :- V=uko1(Id,Doba,MinStart,MaxKonec,Z), K is Z+Doba, formatC ~d: \t~d..~d \t(~d: ~d..~d)\n', [Id,Z,K,Doba,MinStart,MaxKonec] ), tiskni(Vystup). Hana Rudová, Logické programování I, 13. května 2011 71 Omězující podmínky Plánování: výstup II quicksort(S, Sorted) :- quicksortl(S,Sorted-[]). quicksortl([],Z-Z). quicksortl([X|Tail], A1-Z2) :- split(X, Tail, Small, Big), quicksortlCSmall, A1-[X|A2]), quicksort1(Big, A2-Z2). splitC_X, [], [], []). splitCX, [Y|T], [Y|Small], Big) :- greater(X,Y), !, split(X, T, Small, Big). splitCX, [Y|T], Small, [Y|Big]) :- splitCX, T, Small, Big). greaterCukolC_,_,_,_,Z1),ukolC_,_,_,_,Z2)) :- Z1>Z2. Hana Rudová, Logické programování I, 13. kvetna 2011 72 Omezující podmínky Plánování a domény Napiště prědikát nastav_domeny/3, ktěrý na základě datové struktury [uko1(Id,Doba,MinStart,MaxKonec)|Uko1y] vytvo rí doménové proměnné Zacatky pro zacátky startovních dob úkolu a strukturu Tasks vhodnou pro omězění cumulative/1, jějíž prvky jsou úlohy vě tvaru task(Zacatek,Doba,Konec,1,Id). % nastav_domeny(+Uko1y,-Zacatky,-Tasks) Hana Rudová, Logické programování I, 13. května 2011 73 Omězující podmínky Plánování a domény Napište predikát nastav_domeny/3, který na základe datové struktury [ukol(Id,Doba,MinStart,MaxKonec)|Ukoly] vytvo rí doménové promenné Zacatky pro začátky startovních dob úkolu a strukturu Tasks vhodnou pro omezení cumulative/1, jejíž prvky jsou úlohy ve tvaru task(Zacatek,Doba,Konec,1,Id). % nastav_domeny(+Ukoly,-Zacatky,-Tasks) nastav_domeny([],[],[]). nastav_domeny([ukol(Id,Doba,MinStart,MaxKonec)|Ukoly],[Z|Zacatky], [task(Z,Doba,K,1,Id)|Tasks]) :-MaxStart is MaxKonec-Doba, Z in MinStart-.MaxStart, K #= Z + Doba, nastav_domeny(Ukoly,Zacatky,Tasks). Hana Rudová, Logické programování I, 13. kvetna 2011 73 Omezující podmínky D.Ú. Plánování a precedence: precedence(Tasks) Rozši rte r ešení p r edchozího problému tak, aby umožňovalo zahrnutí precedencí, tj. jsou zadány dvojice úloh A a B a musí platit, že A má být rozvrhováno p r ed B. % prec(IdA,IdB) prec(8,7). prec(6,12). prec(2,1). Pro urcení úlohy vTasks lze použít nth1(N,Seznam,NtyPrvek) z knihovny :- use_module(library(lists)). Hana Rudová, Logické programování I, 13. kvetna 2011 74 Omezující podmínky D.Ú. Plánování a precedence: precedence(Tasks) Rozši rte r ešení p r edchozího problému tak, aby umožnovalo zahrnutí precedencí, tj. jsou zadány dvojice úloh A a B a musí platit, že A má být rozvrhováno p r ed B. % prec(IdA,IdB) prec(8,7). prec(6,12). prec(2,1). Pro urcení úlohy vTasks lze použít nth1(N,Seznam,NtyPrvek) z knihovny :- use_module(library(lists)). precedence(Tasks) :- findall(prec(A,B),prec(A,B),P), omezeni_precedence(P,Tasks). omezeni_precedence([],_Tasks). omezeni_precedence([prec(A,B)|Prec],Tasks) :- nth1(A,Tasks,task(ZA,DA,_KA,1,A)), nth1(B,Tasks,task(ZB,_DB,_KB,1,B)), ZA + DA #=< ZB, omezeni_precedence(Prec,Tasks). Hana Rudová, Logické programování I, 13. kvetna 2011 74 Omezující podmínky Kumulativní rozvrhování & cumulatíve([task(Start,Duratíon,End,Demand,TaskId) | Tasks], [límít(Límít)]) & Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duratíon), požadovanou kapacitou zdroje (Demand) a identifikátorem (Id) tak, aby se nep r ekrývaly a aby celková kapacita zdroje nikdy nep r ekrocila Límít Hana Rudová, Logické programování I, 13. kvetna 2011 75 Omezující podmínky Kumulativní rozvrhování & cumu1ative([task(Start,Duration,End,Demand,TaskId) | Tasks], [limit(Limit)]) & Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration), požadovanou kapacitou zdroje (Demand) a identifikátorem (Id) tak, aby se nepřekrývaly a aby celková kapacita zdroje nikdy neprekrocila Limit ií> Príklad s konstantami: cumu1ative([task(Q,4,4,1,1),task(1,2,3,2,2),task(3,3,6,2,3),task(4,2,6,1,4)],[1imit(3)]) 2 4 3 1 T Hana Rudová, Logické programování I, 13. května 20111 ^ 75 ^ ^ ° u Omezující podmínky Plánování a lidé Modifikujte řešení p redchozího problému tak, že £ odstraňte omezení na nep ř ekrývání úkolU JS> p ř idejte omezení umožnující ř ešení každého úkolu zadaným Clovekem (každý Clovek může zpracovávat nejvýše tolik úkolů jako je jeho kapacita) % clovek(Id,Kapacita,IdUkoly) ... clovek Id zpracovává úkoly v seznamu IdUkoly clovek(1,2,[1,2,3,4,5]). clovek(2,1,[6,7,8,9,10]). clovek(3,2,[11,12,13,14,15]). Hana Rudová, Logické programování I, 13. kvetna 2011 76 Omezující podmínky Plánování a lidé Modifikujte rešení p redchozího problému tak, že & odstrante omezení na nep r ekrývání úkolu JS> p r idejte omezení umožnující r ešení každého úkolu zadaným clovekem (každý clovek může zpracovávat nejvýše tolik úkolu jako je jeho kapacita) % clovek(Id,Kapacita,Idlkoly) ... clovek Id zpracovává úkoly v seznamu Idlkoly clovek(1,2,[1,2,3,4,5]). clovek(2,1,[6,7,8,9,10]). clovek(3,2,[11,12,13,14,15]). lide(Tasks,Lide) :- findall(clovek(Kdo,Kapacita,lkoly),clovek(Kdo,Kapacita,lkoly), Lide), omezeni_lide(Lide,Tasks). omezeni_lide([],_Tasks). omezeni_lide([clovek(_Id,Kapacita,lkolyCloveka)|Lide],Tasks) :-omezeni_clovek(lkolyCloveka,Kapacita,Tasks), omezeni_lide(Lide,Tasks). Hana Rudová, Logické programování I, 13. kvetna 2011 76 Omezující podmínky Plánování a lidé (pokračování) Napište predikát omezeni_clovek(UkolyCloveka,Kapacita,Tasks), který ze seznamu Tasks vybere úlohy urcené seznamem UkolyCloveka a pro takto vybrané úlohy sešle omezení cumulative/2 s danou kapacitou cloveka Kapacita. Pro nalezení úlohy v Tasks lze použít nth1(N,Tasks,NtyPrvek) z knihovny :- use_module(library(lists)). Hana Rudová, Logické programování I, 13. kvetna 2011 77 Omezující podmínky Plánování a lidé (pokraCování) Napište predikát omezeni_clovek(UkolyCloveka,Kapacita,Tasks), který ze seznamu Tasks vybere úlohy uníené seznamem UkolyCloveka a pro takto vybrané úlohy sešle omezení cumulative/2 s danou kapacitou cloveka Kapacita. Pro nalezení úlohy v Tasks lze použít nth1(N,Tasks,NtyPrvek) z knihovny :- use_module(library(lists)). omezeni_clovek(UkolyCloveka,Kapacita,Tasks) :- omezeni_clovek(UkolyCloveka,Kapacita,Tasks,[]). omezeni_clovek([],Kapacita,_Tasks,TasksC) :- cumulative(TasksC,[limit(Kapacita)]). omezeni_clovek([U|UkolyCloveka],Kapacita,Tasks,TasksC) :- nth1(U,Tasks,TU), omezeni_clovek(UkolyCloveka,Kapacita,Tasks,[TU|TasksC]). Hana Rudová, Logické programování I, 13. kvetna 2011 77 Omezující podmínky Stromy, grafy Stromy Uzly stromu Tree jsou reprezentovány termy -í* tree(Left,Value,Right): Left a Right jsou opet stromy, Value je ohodnocení uzlu -i* leaf(Value): Value je ohodnoceni uzlu 6 Ji Pr íklad: / \ / \ / \ 2 8 / \ / 14 7 / \ 3 5 tree(tree(leaf(1), 2, tree(leaf(3),4,leaf(5)) ), 6, tree(leaf(7),8,[]) ) Hana Rudová, Logické programování I, 13. kvetna 2011 79 Stromy, grafy Stromy: hledáni prvku in(X,T) Prědikát in(X,T) uspějě, pokud sě prvěkX nachází vě stromu T. Prvěk X sě nachází vě stromě T, jěstližě C Xjě listěm stromu T, jinak lěaf(X) & Xjě korěn stromu T, jinak trěě(Lěft,X,Right) JS* X jě měnší něž korěn stromu T, pak sě nachází v lěvém podstromu T, jinak & X sě nachází v pravém podstromu T Hana Rudová, Logické programování I, 13. května 2011 80 Stromy, grafy Stromy: hledáni prvku in(X,T) Predikát in(X,T) uspeje, pokud se prvek X nachází ve stromu T. Prvek X se nachází ve strome T, jestliže C Xje listem stromu T, jinak leaf(X) & Xje ko ren stromu T, jinak tree(Left,X,Right) -í* X je menší než ko ren stromu T, pak se nachází v levém podstromu T, jinak & X se nachází v pravém podstromu T ín(X, leaf(X)) :- 1. ín(X, tree(_,X,_)) :- 1. ín(X, tree(Left, Root, Ríght) ) :- XV, pak vznikne nový strom s ko renem V, vpravo má leaf(X) (vlevo je []) pokud T=leaf(V) a X pokud T=tree(L,V,R) a X>V, pak v novém strome L ponechej a X p r idej doprava (rekurzivne) pokud T=tree(L,V,R) a XV, pak vznikne nový strom s korenem V, vpravo má leaf(X) (vlevo je []) pokud T=leaf(V) a X pokud T=tree(L,V,R) a X>V, pak v novém strome L ponechej a X pridej doprava (rekurzivne) pokud T=tree(L,V,R) a XV, 1. add(leaf(V), X, tree(leaf(X),V,[]) ) :- 1. XV, pak vznikně nový strom s korěněm V, vpravo má lěaf(X) (vlěvo jě []) pokud T=lěaf(V) a X pokud T=trěě(L,V,R) a X>V, pak v novém stromě L poněchěj a X priděj doprava (rěkurzivně) pokud T=trěě(L,V,R) a XV, !. add(1eaf(V), X, tree(1eaf(X),V,[]) ) :- !. XV, !, add(R,X,R1). add(tree(L,V,R), X, tree(L1,V,R)) :- X iniciálne jsou argumentu termu volné promenné C- na záver je v N-tém argumentu uložen rodic N-tého uzlu (iniciální uzel oznacíme empty) 1--2 1--2 5--4 5 4 \ | \ | | | | \| \ 6--1--2--3 6--1--2--3 3 3 Uzel=4: rodic(4, 1, 2, empty, 6, 1) Uzel=2: rodic(2,empty,1) Hana Rudová, Logické programování I, 13. kvetna 2011 86 Stromy, grafy Procházení grafu do hloubky: algoritmus I Procházení grafu z uzlu Uzel Vytvo ríme term pro rodice (všichni rodici jsou zatím volné promenné) JS> Uzel Uzel má prázdného rodice a má sousedy Sousedi Procházíme (rekurzivne) všechny sousedy v Sousedi dfs(Uzel,Graf,Parents) :- functor(Graf,graf,Pocet), functor(Parents,rodíce,Pocet), arg(Uzel,Parents,empty), arg(Uzel,Graf,Sousedí), prochazej_sousedy(Sousedí,Uzel,Graf,Parents). Hana Rudová, Logické programování I, 13. kvetna 2011 87 Stromy, grafy Procházení grafu do hloubky: algoritmus II Procházení sousedů uzlu Uzel (pokud Uzel nemá sousedy, tj. Sousedi=[], končíme) 1. Uzel Vje první soused 2. Zjistíme rodiče uzlu V ... pomocí arg(V,Parents,Rodic) 3. Pokud jsme V ješte neprošli (tedy nemá rodiče a platí var(Rodic)), tak (a) nastavíme rodice uzlu V na Uzel ... pomocí arg/3 (b) rekurzivne procházej všechny sousedy uzlu V pokud jsme V prošli, dále tímto uzlem nepokracujeme, tj. celkem (var(Rodic) -> true) 4. Procházej zbývající sousedy uzlu Uzel Hana Rudová, Logické programování I, 13. kvetna 2011 88 Stromy, grafy Procházení grafu do hloubky: algoritmus II Procházení sousedu uzlu Uzel (pokud Uzel nemá sousedy, tj. Sousedi=[], koncíme) 1. Uzel Vje první soused 2. Zjistíme rodice uzlu V ... pomocí arg(V,Parents,Rodic) 3. Pokud jsme V ješte neprošli (tedy nemá rodice a platí var(Rodic)), tak (a) nastavíme rodice uzlu V na Uzel ... pomocí arg/3 (b) rekurzivne procházej všechny sousedy uzlu V pokud jsme V prošli, dále tímto uzlem nepokracujeme, tj. celkem (var(Rodic) -> true) 4. Procházej zbývající sousedy uzlu Uzel prochazej_sousedy([],_,_,_). prochazej_sousedy([V|T],Uzel,Graf,Parents) :- arg(V,Parents,Rodic), ( nonvar(Rodic) -> true ; Rodic = Uzel, arg(V,Graf,SousediV), prochazej_sousedy(SousediV,V,Graf,Parents) prochazej_sousedy(T,Uzel,Graf,Parents). Hana Rudová, Logické programování I, 13. kvetna 2011 88 Stromy, grafy DÚ: Procházení grafu do šírky Napište predikát bfs(U,G,P) pro procházení grafu G do šírky z uzlu U. Výsledkem procházení je datová struktura P, která reprezentuje strom vzniklý pri prohledávání grafu G do šírky (pro každý uzel stromu známe jeho rodice). graf([2,3],[1,3],[1,2]). graf([2,4,6],[1,3],[2],[1,5],[4,6],[1,5]). 1-- 2 \ | \| 3 1-- 2 5- -4 | | 6- -1--2--3 3 l=2: rodic(2,empty,2) 5- - 4 | 6- -1--2-- 3 l=4: rodic(4, 1, 2, empty, 4, 1) Hana Rudová, Logické programování I, 13. kvetna 2011 89 Stromy, grafy Podekování Průsviky ze cvicení byly p r ipraveny na základe materiálů d rívejších cvicících tohoto p redmetu. Speciální podekování patrí -í* Adriane Strejckové Další podklady byly p r ipraveny & Alešem Horákem JS* Miroslavem Nepilem iS> Evou Žáckovou Hana Rudová, Logické programování I, 13. kvetna 2011 90 Podekovani