IBOl 3 Logické programování I Backtracking, unifikace, aritmetika (průsvitky ze cvičení) Hana Rudová jaro 2011 Syntaxe logického programu Term: ■ univerzální datová struktura (slouží také pro příkazy jazyka) ■ definovaný rekurzivně ■ konstanty: číselné, alfanumerické (začínají malým písmenem), ze speciálních znaků (operátory) ■ proměnné: pojmenované (alfanumerické řetězce začínající velkým písmenem), anonymní (začínají podtržítkem) ■ složený term: funktor, arita, argumenty struktury jsou opět termy Hana Rudová, Logické programování 1,13. května 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: věty ukončené tečkou, se skládají z hlavy a těla. Prázdné tělo mají fakta, neprázdné pak pravidla, existují také klauzule bez hlavy - direktivy. Hlavu tvoří literál (složený term), tělo seznam literálů. Literálům v těle nebo v dotazu říkáme cíle. Dotazem v prostředí interpretu se spouští programy či procedury. ■ př. otec(Otec,Dite) :- rodič(Otec,Dite), muz(Otec). rodic(petr, jana). :- otec(0tec, jana). Sémantika logického programu: procedury = databáze faktů a pravidel = logické formule Hana Rudová, Logické programování 1,13. května 2011 Backtracking, unifikace, aritmetika i|»sicsm5pt*lu..r| p Debjg H V_% r» ro ■ i-f I a. ^ -ŕ. ^ I; -ft Prolog Top-level Configuration [SK Stu ä Launch ícnfiíjuľaticn T.pel] 33? Prolocj Target = call: Euffix([a,_7551,c].,läI0: = rtiy_p recti (_18I0) j Prolog Top-level Process °o Breakpoints V my_module.,pro E 50lule[mv_TQQ0lule, [m^pcedl/l, .".v iľ=ľj;3 * ^ií.ií e rr í lí 7 sitf ortir.a undefined p2*£ ajffixC?List ľSuffiicl 9 my_predl,l v my_pred2/2 true when List an J Suffi 1 i-'-i ■■■ >:i:: 5=.iFfn :■ >-uSfn ;;f Lis! H te:-m:n*te= c:-si If List is proper, and lias 1+1 solutions, Suffices are enumerated in descending order of length, (documentatior formatting will be improved later!} -=llir.zí -Ír..".--*-.'. — r- ŕľf:.:ľ = :fi /_Fied; [S, Xs) :- fl iraro 3houb nsn-tciviai aangletjon variables i foteachp:,Xsj i_i acstu: Toplevel 1 in C:/Userr,-pŕini.;!CÍ —.D-njntime-E.jlipiŕ^ppL.iíľcnJZ-My Prolog Project 51 & [IL ^ @ • ^ 2 Call: suffix I(a,7551,c],_1810) Hana Rudová, Logické programování I, 1 3. května 2011 Backtracking, unifikace, aritmetika SICStus Prolog: konzultace Otevření souboru: File->Open File Přístup k příkazové řádce pro zadávání dotazů: SICStus->Open Toplevel Načtení programu: tzv. konzultace přímo z Menu: SICStus->Consult Prolog Code (okno s programem aktivní) nebo zadáním na příkazový řádek po uložení souboru (Ctrl+S) ?- consult(rodokmen) . pokud uvádíme celé jméno případně cestu, dáváme jej do apostrofů ?- consult('D:\prolog\moje\programy\rodokmen. pl ') . V Eclipse lze nastavit Key bindings, pracovní adresář, ... SICStus Prolog: spouštění programu UNIX: module add sicstus-4.1.3 eclipse % používám' IDE SPIDER sicstus % používám' přes příkazový řádek ■ MS Windows: ■ používání IDE SPIDER: z nabídky All Programs -> IDE -> Eclipse 3.6 ■ příkazový řádek: z nabídky All Programs -> IDE -> SICStus 4.1.3 nastavíme pracovní adresář pomocí File/Working directory, v případě potřeby nastavíme font Settings/Font a uložíme nastavení Settings/Save settings. ■ Iniciální nastavení SICStus IDE v Eclipse pomocí Help->Cheat Sheets->lnitial set up of paths to installed SICStus Prolog s cestou "C:\Program Files (x86)\SICStus Prolog VC9 4.1.3\bin\sicstus.exe" návod: http: //www. si cs. se/s i est us/spider/si te/prerequi sites . html#Setti ngLIp Hana Rudová, Logické programování 1,13. května 2011 6 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 okně TopLevel, kurzor musí být na konci posledního řádku s | ?-), př. ?- predekCpetr,lenka). ?- predek(X.Y). Každý příkaz ukončujeme tečkou. Přerušení a zastavení cyklícího programu: pomocí ikony Restart Prolog "t- z okna Toplevel Hana Rudová, Logické programování I, 13. května 2011 7 Backtracking, unifikace, aritmetika Hana Rudová, Logické programování 1,13. května 2011 8 Backtracking, unifikace, aritmetika Příklad rodokmen Backtracking: příklady rodic(petr, filip). muz(petr). V pracovním adresáři vytvořte program rodokmen. rodic(petr, lenka). muz(filip). Načtěte program v interpretu (konzultujte). rodic(pavel, jan). muz(pavel). V interpretu Sicstus Prologu pokládejte dotazy: rodic(adam, petr). muz(jan) . rodicCtomas, michal). muz(adam). ■ Je Petr otcem Lenky? rodic(michal, radek). muz(tomas). ■ Je Petr otcem Jana? rodicCeva, filip). muz(michal). rodicCjana, lenka). muz(radek). ■ Kdo je otcem Petra? rodicCpavla, petr). ■ Jaké děti má Pavla? rodicCpavla, tomas). zena(eva). rodicClenka, vera). zena(lenka). ■ Ma Petr dceru? zena(pavla). ■ Které dvojice otec-syn známe? zena(jana). zena(vera). otec(Otec,Dite) :- rodič(Otec,Dite) , muz(Otec). Hana Rudová, Logické programování 1,13. května 2011 9 Backtracking, unifikace, aritmetika Hana Rudová, Logické programování 1,13. května 2011 10 Backtracking, unifikace, aritmetika Backtracking: řešení příkladů Backtracking: příklady II Středníkem si vyžádáme další řeš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 | ?- otec(0tec,Syn),muz(Syn). Syn = fi 1 i p, Otec = petr ? ; Syn = jan, Otec = pavel ? ; Syn = petr, Otec = adam ? ; Syn = michal, Otec = tomas ? ; Syn = radek, Otec = michal ? ; no I ?- Predikát potomek/2: potomek(Potomek,Předek) :- rodic(Predek,Potomek). potomek(Potomek,Předek) :- rodic(Predek.X), potomek(Potomek.X). Naprogramujte predikáty ■ prababicka(Prababicka,Pravnouce) ■ nevJastni_bratr(Nevlastni_bratr,Nevíastni_sourozenec) nápověda: využijte X \== Y (X a Y nejsou identické) Řešení: prababicka(Prababicka,Pravnouce):-rodic(Prababicka,Prarodič), zena(Prababicka), rodic(Prarodic,Rodič), rodic(Rodic,Pravnouce). Hana Rudová, Logické programování 1,13. května 2011 Backtracking, unifikace, aritmetika Hana Rudová, Logické programování 1,13. května 2011 Backtracking, unifikace, aritmetika Backtracking: řešení příkladů II Backtracking: prohledávání stavového prostoru neviastni_bratr(Bratr,Sourozenec):-rodic(X,Bratr), muz(Bratr), rodic(X,Sourozenec), /'■'•' tento test neni nutný, ale zvyšuje efektivitu '■'•'/ Bratr \== Sourozenec, rodic(Y,Bratr), Y \== X, rodic(Z,Sourozenec), Z \== X, Z \== Y. /'■'•' nevhodne umisteni testu - vypočet "bloudi" v neúspešných 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í 1,13. května 2011 Backtracking, unifikace, aritmetika Backtracking: řešení /* varianta la '■'•'/ potomek(Potomek,Předek): potomek(Potomek,Předek): -rodic(Predek,Potomek). -rodic(Predek.X),potomek(Potomek.X). /'■'•' varianta lb - jine poradi odpovedi, neprimi potomci maji přednost '■'•'/ potomek(Potomek,Předek):-rodic(Predek.X),potomek(Potomek.X). potomek(Potomek,Předek):-rodič(Předek,Potomek). /'■'•' varianta 2a - leva rekurze ve druhé klauzuli, na dotaz potomek(X, pavla) výpise odpovedi, pak cykli '■'•'/ potomek(Potomek,Předek):-rodič(Předek,Potomek). potomek(Potomek,Předek):-potomek(Potomek,X),rodic(Predek.X). /'■'•' varianta 2b - leva rekurze v prvni klauzuli, na dotaz potomek(X, pavla) hned cykli '■'•'/ potomek(Potomek,Předek):-potomek(Potomek,X),rodic(Predek.X). potomek(Potomek,Předek):-rodič(Předek,Potomek). Hana Rudová, Logické programování 1,13. května 2011 Backtracking, unifikace, aritmetika Zkuste předem odhadnout (odvodit) pořadí, vjakem budou nalezeni potomci Pavly? Jaký vliv má pořadí klauzulí a cílu v predikátu potomek/2 na jeho funkci? Nahraďte ve svých programech volání predikátu rodic/2 následujícím predikátem rodic_v/2 rodic_v(X,Y):-rodic(X,Y),print(X),print('? '). Pozorujte rozdíly v délce výpočtu dotazu nevlastni_bratr(fi"lip,X) při změně pořadí testů v definici predikátu nevlastni_bratr/2 Hana Rudová, Logické programování 1,13. května 2011 Backtracking, unifikace, aritmetika I ?- 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 I ?- nevlastni_bratr2(X,Y). petr? petr? petr? petr? eva? eva? petr? eva? petr? petr? petr? jana? eva? petr1: X = filip, Y = lenka ? ; petr? petr? petr? petr? eva? jana? petr? eva? petr? petr? petr? jana? jana? pel jana? pavel? pavel? pavel? pavel? adam? adam? adam? adam? pavla? pavla? adam? pavla? tomas? tomas? tomas? tomas? michal? michal? michal? michal? eva? eva? pf petr? eva? eva? petr? eva? jana? jana? petr? petr? jana? jana? petr? jana? pavl pavla? adam? adam? pavla? pavla? adam? pavla? pavla? adam? pavla? pavla? pavla1: pavla? pavla? pavla? adam? pavla? pavla? pavla? pavla? lenka? lenka? lenka? ler no Hana Rudová, Logické programování 1,13. května 2011 Backtracking, unifikace, aritmetika Unifikace:příklady Které unifikace jsou korektní, které ne a proč? 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,p"lus) 6. s(l,a(X,q(w)))=s(Y,a(2,Z)) 7. s(l,a(X,q(X)))=s(W,a(Z,Z)) 8. X=Y,P=R,s(l,a(P,q(R)))=s(Z,a(X,Y)) Neuspěje volání 1) a 3), ostatní ano, cyklické struktury vzniknou v případech 4),7) a 8) přestože u posledních dvou mají levá a pravá strana unifikace disjunktní množinyjmen proměnných. Hana Rudová, Logické programování 1,13. května 2011 Backtracking, unifikace, aritmetika Mechanismus unifikace I Unifikace v průběhu dokazování predikátu odpovídá předávání parametrů při provádění procedury, aleje důležité uvědomit si rozdíly. Celý proces si ukážeme na příkladu predikátu suma/3. suma(0,X,X) . /'•'••klauzule A*/ suma(sCX) ,Y,s(Z)) :-suma(X,Y,Z) . /'•••klauzule B*/ pomocí substitučních rovnic při odvozování odpovědi na dotaz ?- suma(sCO),s(0),X0). Hana Rudová, Logické programování 1,13. května 2011 Backtracking, unifikace, aritmetika Mechanismus unifikace II suma(0,X,X). /*A*/ suma(s(X),Y,s(Z)):-suma(X,Y,Z). /*B*/ ?- suma(sCO),s(0),X0). 1. dotaz unifikujeme s hlavou klauzule B, s A nejde unifikovat (1. argument) suma(sCO),s(0),X0) = suma(s(Xl),Yl,s(Zl)) ==> XI = 0, Yl = s(0), s(Zl) = X0 ==> suma(0,s(0),Z1) 2. dotaz (nový podcíl) unifikujeme s hlavou klauzule A, klauzuli B si poznačíme jako další možnost suma(0,s(0),Z1) = suma(0,X2,X2) X2 = s(0), Zl = s(0) ==> X0 = s(sCO)) X0 = s(sCO)) ; 2' dotaz z kroku 1. nejde unifikovat s hlavou klauzule B (1. argument) no Hana Rudová, Logické programování 1,13. května 2011 19 Backtracking, unifikace, aritmetika Vícesměrnost predikátů Logický program lze využít vícesměrně, například jako ■ výpočet kdo je otcem Petra? ?- otec(X, petr) . kolik je 1+1? ?- suma(s(0) ,s(0) ,X) . ■ 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ítě známe? ?-otec(X,Y) . Které X a Y dávají v součtu 2? ?- suma(X, Y, s(s(0)) ). ... ale pozor na levou rekurzi, volné proměnné, asymetrii, ajiné záležitosti Následující dotazy ?-suma(X,s(0),z). ?-suma(s(0),x,Z). nedávají stejné výsledky. Zkuste šije odvodit pomocí substitučních rovnic. Hana Rudová, Logické programování 1,13. května 2011 20 Backtracking, unifikace, aritmetika Aritmetika Zavádíme z praktických důvodů, ale aritmetické predikátyjiž nejsou vícesměrné, protože v každém aritmetickém výrazu musí být všechny proměnné instaciovány číselnou konstantou. Důležitý rozdíl ve vestavěných predikátech is/2 vs. =/2 vs. =.=12 is/2: < konstanta nebo proměnná > is < aritmetický výraz > výraz na pravé straně je nejdří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 nejdříve aritmeticky vyhodnoceny a pak porovnány Hana Rudová, Logické programování 1,13. května 2011 Backtracking, unifikace, aritmetika Aritmetika: příklady Jak se liší následující dotazy (na co se kdy ptáme)? Které uspějí (kladná odpověď), které neuspějí (záporná odpověď), a které jsou špatně (dojde k chybě)? Za jakých předpokladů by ty neúspěšné případně špatné uspěly? 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 1 3. 1 <= 2 14. 1 =< 2 1 5. sin(X) is sin(2) 16. sin(X) = sin(2+Y) 1 7. sin(X) =:= sin(2+Y) Nápověda: '='/2 unifikace, '=='/2 test na identitu, '=:='/2 aritmetická rovnost, '\=='/2 negace testu na identitu, '=\='/2 aritmetická nerovnost Hana Rudová, Logické programování 1,13. května 2011 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? sl(0,X,X). sl(s(X),Y,s(Z)):-sl(X,Y,Z). s2(X,Y,Z):- Z i s X + Y. sl/3 je vícesměrný - umí sčítat, odečítat, generovat součty, ale pracuje jen s nezápornými celými čísly s2/3 umí pouze sčítat, ale také záporná a reálná čísla Operátory Definice operátorů umožňuje přehlednější infixový zápis binárních a unárních predikátů, příklad: definice op(l 200,Y,':-') umožňuje 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/l. Vyzkoušejte display((a:-print(s(s(0))),b,c)). di splay(a+b+c-d-e*f*g-h+i). display([l,2,3,4,5]). Definice standardních operátorů najdete na konci manuálu. Hana Rudová, Logické programování I, 13. května 2011 23 Backtracking, unifikace, aritmetika Hana Rudová, Logické programování 1,13. května 2011 24 Backtracking, unifikace, aritmetika Závěr Dnešní látku jste pochopili dobře, pokud víte ■ jaký vliv má pořadí klauzulí a cílu v predikátu potomek/2 na jeho funkci, ■ jak umisťovat testy, aby byl prohledávaný prostor co nejmenší (příklad nevlastni_bratr/2), Seznamy, ŤeZ ■ k čemu dojde po unifikaci X=a(X), ■ proč neuspěje dotaz ?- X=2, sin(X) is sin(2). ■ za jakých předpokladů uspějí tyto cíle X=Y, X==Y, X=:=Y, ■ a umíte odvodit pomocí substitučních rovnic odpovedi na dotazy suma(X,s(0),Z) a suma(s(0),X,Z). Hana Rudová, Logické programování I, 1 3. května 201 1 25 Backtracking, unifikace, aritmetika Reprezentace seznamu ■ Seznam: [a, b, c],prázdný seznam [] ■ Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo) ■ všechny strukturované objekty stromy - i seznamy ■ funktordva argumenty ■ .(a, .(b, .(c, []))) = [a, b, c] ■ notace: [ Hlava | Telo ] = [a | Tel o] Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] ■ Lze psát i: [a, b | Tel o] ■ před " I "je libovolný počet 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] ■ Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S] Hana Rudová, Logické programování 1,13. května 2011 27 Seznamy, řez Cvičení: append/2 appendC [], S, S ). % (1) appendC [X|S1], S2, [X|S3] ) :- appendC SI, S2, S3). % (2) :- append([l,2],[3,4],A). I (2) I A=[1|B] :- append([2],[3,4],B) . I (2) I B=[2|C] => A=[1,2|C] :- append([],[3,4],C). I CD | C=[3,4] => A=[l,2,3,4], yes Předchůdce a následník prvku X v seznamu S hledej(S,X,Pred,Po) :- appendC _S1, [ Pred,X,Po | _S2 ], S) Hana Rudová, Logické programování 1,13. května 2011 28 Seznamy, řez Seznamy a append appendC [], S, S ). appendC [X|S1], S2, [X|S3] ) :- appendC SI, S2, S3). Napište následující predikáty pomocí append/3: ■ prefixC SI, S2 ) :- appendC SI, _S3, S2). DÚ: suffix(Sl,S2) ■ lastC X, S ) :- appendC _S1, [X], S). appendC[3,2], [6], [3,2,6]). X=6, S=[3,2,6] ■ memberC X, S ) :- appendC SI, [X|S2], S ). appendC[3,4,1], [2,6], [3,4,1,2,6]). X=2, S=[3,4,1,2,6] DÚ: adjacentCX.Y.S) ■ % sublistC+S,+ASB) sublistCS.ASB) :- appendC AS, B, ASB ), appendC A, S, AS ). POZOR na efektivitu, bez append lze často napsat efektivněji Hana Rudová, Logické programování 1,13. května 2011 29 Seznamy, řez LCO a akumulátor ■ Reformulace rekurzivní procedury, aby umožnila LCO ■ Výpočet délky seznamu length( Seznam, Délka ) lengthC [] , 0 ) . lengthC [ H | T ], Délka ) :- lengthC T, DelkaO ), Délka is 1 + DelkaO. ■ Upravená procedura, tak aby umožnila LCO: % lengthC Seznam, ZapocitanaDelka, CelkovaDelka ): % CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam'' lengthC Seznam, Délka ) :- lengthC Seznam, 0, Délka ). % pomocný predikát lengthC [] , Délka, Délka ). % celková délka = započítaná délka lengthC [ H I T ], A, Délka ) :- A0 is A + 1, lengthC T, A0, Délka ). ■ Přídavný argument se nazývá akumulátor Optimalizace posledního volání ■ Last Call Optimization (LCO) ■ Implementační technika snižující nároky na paměť ■ Mnoho vnořených rekurzivních volání je náročné na paměť ■ Použití LCO umožňuje vnořenou rekurzi s konstantními pamětovými nároky ■ Typický příklad, kdy je možné použití LCO: ■ procedura musí mít pouze jedno rekurzivní volání: v posledním cíli poslední klauzule ■ cíle předcházející tomuto rekurzivnímu volání musí být deterministické ■ pC ...):- ... % žádné rekurzivní voláni v těle klauzule pC ...):- ... % žádné rekurzivní voláni v těle klauzule pC-..) :- !, pC ■■■ )■ % řez zajišťuje determinismus ■ Tento typ rekurze lze převést na iteraci Hana Rudová, Logické programování I, 13. května 2011 30 Seznamy, řez Akumulátor a sum_l i st (S, Sum) ?- sum_listC [2,3,4], Sum ). bez akumulátoru: sum_listC [] , 0 ) . sum_listC [H|T], Sum ) :- sum_listC T, SumT ), Sum i s H + SumT. s akumulátorem: sum_listC S, Sum ) :- sum_listC S, 0, Sum ). sum_listC [], Sum, Sum ). sum_listC [H|T], A, Sum ) :- AI is A + H, sum_listC T, AI, Sum). Hana Rudová, Logické programování I, 13. května 2011 31 Seznamy, řez Hana Rudová, Logické programování 1,13. května 2011 Výpočet faktoriálu fact (N, F) s akumulátorem: fact( N, F ) :- fact C N, 1, F ). fact( 1, F, F ) :- !. fact( N, A, F ) :- N > 1, Al i s N * A, Nl i s N - 1, fact( Nl, Al, F ). Hana Rudová, Logické programování I, 1 3. května 2011 X=l,r(X). r (X) r (X) r (X) P (X) P (X) P (X) a (X) a (X) b (X) b (X) c (X) c (X) d (X) d (X) -write(rl) . -p(X),write(r2). -write(r3) . -write(pl) . -a(X),b(X),!, c(X),d(X),write(p2). -write(p3) . -write(al) . -write(a2). - X > 0, write(bl). - X < 0, write(b2). X mod 2 X mod 3 write(cl) . write(c2). abs(X) < 10, write(dl). write(d2). I ? rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; no I ?- X=0,r(X). rl X = 0 ? ; plr2 X = 0 ? ; ala2p3r2 X = 0 ? ; r3 X = 0 ? ; no I ?- X=3,r(X). rl X = 3 ? ; plr2 X = 3 ? ; alblc2dlp2r2 X = 3 ? ; d2p2r2 X = 3 ? ; r3 X = 3 ? ; no 6, rC I ?- X: rl X = -6 ? ; plr2 X = -6 ? ; alb2cldlp2r2 X = -6 ? ; d2p2r2 X = -6 ? ; c2dlp2r2 X = -6 ? ; d2p2r2 X = -6 ? ; r3 X = -6 ? ; no r(X) r (X) r (X) P (X) P (X) P (X) a (X) a (X) b (X) b (X) c (X) c (X) d (X) d (X) -write C rl). -p(X),write(r2) . -write(r3). -write(pl). -a(X),b(X), ! , c(X),d(X),write(p2) . -write(p3). -write(al). -write(a2). - X > 0, write(bl). - X < 0, write(b2). Prozkoumejte trasy výpočtu a navracení např. pomocí následujících dotazů (vždy si středníkem vyžádejte navracení): (1) X=l,r(X). (3) X=0,r(X). (2) X=3,r(X). (4) X= -6,r(X). X mod 2 X mod 3 0, write(cl). 0, write(c2). abs(X) < 10, write(dl). write(d2). Hana Rudová, Logické programování 1,13. května 2011 řez v predikátu p/1 neovlivní alternativy predikátu r/1 dokud nebyl proveden řez, alternativy predikátu a/l se uplatňují, př. neúspěch b/1 v dotazu (3) při neúspěchu cíle za řezem se výpočet navrací až k volající proceduře r/1, viz (1) alternativy vzniklé po provedení řezu se zachovávají - další možnosti predikátu c/1 viz (2) a (4) 34 Seznamy, řez Rez: maximum Je tato definice predikátu max/3 korektní? max(X,Y,X):-X>=Y,!. max(X,Y,Y). Není, následující dotaz uspěje: ?- max(2 ,1,1). Uveďte dvě možnosti opravy, se zachováním použití řezu a bez. max(X,Y,X):-X>=Y. max(X,Y,Y):-Y>X. max(X,Y,Z):-X>=Y,!,Z=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 Při použití řezu je třeba striktně oddělit vstupní podmínky od výstupních unifikací a výpočtu. Hana Rudová, Logické programování 1,13. května 2011 Hana Rudová, Logické programování 1,13. května 2011 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ř. pomocí member( X, [1,2,3] )■ memlCH,[H|_]). memlCH,[_|T]) mem2(H,[H|_]) mem2(H,[_|T]) memlCH,T). mem2(H,T). mem3(H,[K|_]) mem3(H,[K|T]) H==K. H\==K, mem3(H,T). ■ meml/2 vyhledá všechny výskyty, při porovnávání hledaného prvku s prvky seznamu může dojít k vázání proměnných (může sloužit ke generování všech prvků seznamu) ■ mem2/2 najde jenom první výskyt, taky váže proměnné ■ mem3/2 najde jenom první výskyt, proměnné neváže (hledá pouze identické prvky) Dokážete napsat variantu, která hledá jenom identické prvky a přitom najde všechny výskyty? mem4(H,[K|_]) :- H==K. mem4(H,[K|T]) :- mem4(H,T). Hana Rudová, Logické programování 1,13. května 2011 37 Seznamy, řez deleteC X, [X|S], S ) . deleteC X, [Y|S], [Y|S1] ) Rez: delete delete(X,S,Sl) . Napište predikát delete(X,S, SI), který odstraní všechny výskyty X (pokud se X v S nevyskytuje, tak predikát uspěje). deleteC _X, [] , [] ) . deleteC X, [X|S], SI) :- !, delete(X,S,Sl). deleteC X, [Y|S], [Y|S1] ) :- delete(X,S,Sl). Hana Rudová, Logické programování 1,13. května 2011 Seznamy: i nte rsecti on (A, B, C) DÚ: Napište predikát pro výpočet průniku dvou seznamů. Nápověda: využijte predikát member/2 DÚ: Napište predikát pro výpočtu rozdílu dvou seznamů. Nápověda: využijte predikát member/2 Všechna řešení, třídění, rozdílové seznamy Hana Rudová, Logické programování I, 1 3. května 2011 Všechna řešení Všechna řešení % zOmeno, Při jmen i , Pohlavi, Vek, Prače, Fi rma) zCpetr,novak.m,30,skladni k,škoda). z(pavel,novy,m,40.mechani k,škoda). z(rošti slav,1ucensky,m,50,techni k,škoda). z(alena,veselá,z,25,sekretářka,škoda). z(jana,dankova,z,35,asi stentka,škoda). z(lenka,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). z(petra,špičková,z,45,uklizecka,zs_stara). ■ Najděte jméno a příjmení všech lidí. ?- findall Qmeno-Pri jmeni , zQmeno, Pri jmeni ,_,_,_,_), L) . ?- bagof( Jmeno-Prijmeni, [S,V,Pr,F] A zQmeno, Pri jmeni, S, V, Pr, F) , L). ?- bagof( 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 ?- findall( cQ,P,Firma), ( zQ , P,Fi rma) , ( Firma=skoda ; Firma=cs ) ), ?- bagof( J-P, [S,V,Pr]A(z(],P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). ?- setof( P-J, [S,V,Pr]A(z(],P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). Kolik žen a mužů je v databázi? ?- findalK c(P,J), z(P,],z,_,_ ?- findalK c(P,J), z(P,],m,_,_ _), L), length(L.N). _), L), length(L.N). ?- bagof(c(P,J), [Ve,Pr,Fi]Az(P,J,S,Ve,Pr,Fi), L) , length(L.N). ?- findalK S-N, ( bagof(c(P,J), [Ve,Pr,Fi]Az(P,J,S,Ve,Pr,Fi), L) , length(L,N) ), Dvoj ice ). Hana Rudová, Logické programování 1,13. května 2011 Všechna řešení, třídění, rozdílové seznamy Hana Rudová, Logické programování 1,13. května 2011 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. setof(P-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, 1 3. května 2011 43 Všechna řešení, třídění, rozdílové seznamy bubblesort(S,Sorted) Seznam S seřaďte tak, že ■ nalezněte první dva sousední prvky X a Y v S tak, že X>Y, vyměňte pořadí X a Y a získate SI; a seřaďte SI ■ pokud neexistuje žádný takový pár sousedních prvků X a Y, pak je S seřazený seznam swap(S,Sl) rekurzivně bubblesortem bubblesort(S,Sorted) :- swap (S,SI), !, bubblesort(Sl, Sorted). bubblesort(Sorted,Sorted). swap([X,Y|Rest],[Y,X|Restl]) :-X>Y. swap([X|Rest],[X|Restl]) :-swap(Rest,Restl). Hana Rudová, Logické programování 1,13. května 2011 % 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 44 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, 1 3. května 2011 45 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, 1 3. května 2011 47 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í 1,13. května 2011 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í 1,13. května 2011 Všechna řešení, třídění, rozdílové seznamy quicksort pomocí rozdílových seznamů DÚ: pal i ndrom(L) 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(Al-A2, A2-Z2, A1-Z2). Hana Rudová, Logické programování I, 1 3. května 2011 49 Všechna řešení, třídění, rozdílové seznamy Vstup/výstup, databázové operace, rozklad termu 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 indrom(Seznam) :- reverse(Seznam,Seznam). Hana Rudová, Logické programování 1,13. května 2011 Všechna řešení, třídění, rozdílové seznamy Čtení ze souboru process_file( Soubor ) :- seeing( StarySoubor ), see( Soubor ), repeat, read( Term ), process_term( Term ) , Term == end_of_file, % zjištění aktivního proudu % otevření souboru Soubor % čtení termu Term % manipulace s termem % je konec souboru? seen, see( StarySoubor ). % uzavření souboru % aktivace původního proudu repeat. repeat repeat. % vestavěný predikát Hana Rudová, Logické programování 1,13. května 2011 Vstup/výstup, databázové operace, rozklad termu Predikáty pro vstup a výstup Příklad: vstup/výstup I ?- read(A), read( ahoj(B) ), read( [C,D] ). |: ahoj. ahoj( petre ). [ ahoj( 'Petre!' ), jdeme ]. A = ahoj, B = petre, C = ahoj('Petre!'), D = jdeme I ?- write(a(l)), write('.'), nl, write(a(2)), write('.'), nl. a(l). a(2). yes ■ seeing, see, seen, read ■ telling, tell, told, write ■ standardní vstupní a výstupní stream: user Hana Rudová, Logické programování 1,13. května 201 1 53 Vstup/výstup, databázové operace, rozklad termu Napište predikát uloz_do_souboru( Soubor ), který načte několik fakt ze vstupu a uloží je do souboru Soubor. I ?- u"loz_do_souboru( 'soubor.pl ' ). I: faktCmi rek, 18). I: faktCpavel,4). I: end_of_file. yes I ?- consult(soubor). % Consulting /home/hanka/soubor.pl... % consulted /home/hanka/soubor.pl in module user, 0 msec % 376 bytes yes I ?- 1 istingCfakt/2) . % pozor:listing/1 lze použít pouze při consult/1 (ne u compile/1) fakt(mi rek, 18). faktCpavel, 4). yes Hana Rudová, Logické programování 1,13. května 2011 54 Vstup/výstup, databázové operace, rozklad termu Implementace: vstup/výstup uloz_do_souboru( Soubor ) :-seeingC StaryVstup ), tellingC StaryVystup ), see( user ), tel 1 C 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 ) :- writeC Term ), writeC'.'), nl. Hana Rudová, Logické programování I, 1 3. května 201 1 55 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 explicitně (fakty) i implicitně (pravidly) ■ Vestavěné predikáty pro změnu databáze během provádění programu: assert( Klauzule ) přidání Klauzule do programu asserta( Klauzule ) přidání na začátek assertz( Klauzule ) přidání na konec retract( Klauzule ) smazání klauzule unifikovatelné s Klauzule ■ Pozor: retract/1 lze použít pouze pro dynamické klauzule (přidané pomocí assert) a ne pro statické klauzule z programu ■ Pozor: nadměrné použití těchto operací snižuje srozumitelnost programu Hana Rudová, Logické programování 1,13. května 2011 56 Vstup/výstup, databázové operace, rozklad termu Databázové operace: příklad Databázové operace: implementace Napište predikát vytvor_program/0, který načte několik klauzulí ze vstupu a uloží je do programové databáze. | ?- vytvor_program. |: faktCpavel, 4). |: praviďlo(X,Y) :- fakt(X.Y). |: end_of_file. yes | ?- 1 isting(fakt/2). faktCpavel, 4). yes | ?- listingCpravidlo/2) . pravidlo(A, B) :- fakt(A, B). yes | ?- clauseC pravidloCA, B) , C) . % clause/2 použitelný pouze pro dynamické klauzule C = fakt(A,B) ? yes Hana Rudová, Logické programování 1,13. května 2011 57 Vstup/výstup, databázové operace, rozklad termu Konstrukce a dekompozice termu ■ Konstrukce a dekompozice termu Term =.. [ Funktor | SeznamArgumentu ] aC9,e) =.. [a,9,e] Cil =.. [ Funktor | SeznamArgumentu ], callC Cil ) atom =. . X => X = [atom] ■ Pokud chci znát pouze funktor nebo některé argumenty, pak je efektivnější: functor( Term, Funktor, Arita ) functorC aC9,e), a, 2 ) functorCatom,atom.O) functorCl,1,0) arg( N, Term, Argument ) argC 2, aC9,e), e) Hana Rudová, Logické programování I, 1 3. května 2011 59 Vstup/výstup, databázové operace, rozklad termu vytvo r_p rog ram :- seeingC StaryVstup ), seeC user ) , repeat, read C Term ), uloz_termC Term ), Term == end_of_file, i seen, seeC StaryVstup ). uloz_termC end_of_file ) :- !. uloz_termC Term ) :- assertC Term ). Hana Rudová, Logické programování 1,13. května 2011 58 Vstup/výstup, databázové operace, rozklad termu Rekurzivní rozklad termu ■ Term je proměnná (var/l), atom nebo číslo (atomic/1) => konec rozkladu ■ Term je seznam ([_|_]) => procházení seznamu a rozklad každého prvku seznamu ■ Term je složený (=../2 , functor/3) => procházení seznamu argumentů a rozklad každého argumentu ■ Příklad: ground/1 uspěje, pokud v termu nejsou proměnné; jinak neuspěje groundCTerm) :- atomicCTerm), !. % Term je atom nebo čislo NEBO groundCTerm) :- varCTerm), !, fail. % Term neni proměnná NEBO groundC[H|T]) :- !, groundCH), groundCT). % Term je seznam a ani hlava ani těl % neobsahuji proměnné NEBO groundCTerm) :- Term =.. [ _Funktor | Argumenty ], % je Term složený groundC Argumenty ). % a jeho argumenty % neobsahuji proměnné ?- groundCsC2,[aCl,3),b,c],X)). ?- groundCsC2,[aCl,3),b,c])). no yes Hana Rudová, Logické programování 1,13. května 2011 60 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é uspějí, pokud je S podtermem termu T. Tj. musí platit alespoň jedno z ■ podterm S je právě term T NEBO ■ podterm S se nachází v hlavě seznamu T NEBO ■ podterm S se nachází v těle seznamu T NEBO ■ T je složený term (compound/1) a S je podtermem některého argumentu T ■otestujte :- subterm(l,2). pokud nepoužijeme (compound/1), pak tento dotaz cyklí ■otestujte :- subterm(a, [1,2]) . ověřte, zda necyklí (nutný červený řez níže) | ?- subterm(sin(3),b(c,2,[l,b],sin(3) ,a)) . yes subterm(T.T) :- !. subterm(S,[H|_]) :- subterm(S.H) , !. subterm(S, [_|T]) :- !, subterm(S,T) . subterm(S.T) :- compound(T), T=..[_|Argumenty], subterm(S.Argumenty). Hana Rudová, Logické programování 1,13. května 2011 61 Vstup/výstup, databázové operace, rozklad termu D.Ú. um'fy(A,B) Napište predikát uni fy(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), !, A=B. unify(A,B) :- var(A), !, not_occurs(A,B), A=B. unify(A,B) :- var(B), !, not_occurs(B,A), B=A. unify(A,B) :- atomic(A), atomic(B), !, A==B. unify([HA|TA],[HB|TB]) :- !, unify(HA,HB), unify(TA,TB). unify(A,B) :- A=..[F|ArgA], B=..[F|ArgB], unify(ArgA,ArgB). same(A,B) Napište predikát same(A, B), který uspěje, pokud mají termy A a B stejnou strukturu. Tj. musí platit právě jedno z ■ A i B jsou proměnné NEBO ■ pokud je jeden z argumentů proměnná (druhý ne), pak predikát neuspěje, NEBO ■ A i B jsou atomic a unifikovatelné NEBO ■ A i B jsou seznamy, pak jak jejich hlava tak jejich tělo mají stejnou strukturu NEBO ■ A i B jsou složené termy se stejným funktorem a jejich argumenty mají stejnou strukturu | ?- same([l,3,sin(X),s(a,3)],[l,3,sin(X),s(a,3)]). yes same(A.B) :- var(A), var(B), !. same(A.B) :- var(A), !, fail. same(A.B) :- var(B), !, fail. same(A.B) :- atomic(A), atomic(B), !, A==B. same([HA|TA],[HB|TB]) :- !, same(HA.HB), same(TA,TB). same(A.B) :- A=..[F|ArgA], B=..[F|ArgB], same(ArgA,ArgB). Hana Rudová, Logické programování 1,13. května 2011 62 Vstup/výstup, databázové operace, rozklad termu not_occurs(A,B) Predikát not_occurs(A, B) uspěje, pokud se proměnná A nevyskytuje v termu B. Tj. platí jedno z ■ B je atom nebo číslo NEBO ■ B je proměnná různá od A NEBO ■ B je seznam a A se nevyskytuje ani v těle ani v hlavě 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, 1 3. května 2011 63 Vstup/výstup, databázové operace, rozklad termu Hana Rudová, Logické programování 1,13. května 2011 64 Vstup/výstup, databázové operace, rozklad termu Logické programování s omezujícími podmínkami Jazykové prvky Nalezněte řešení pro algebrogram DONALD + CERALD = ROBERT ■ Struktura programu algebrogram( [D,0,N,A,L,C,E,R,B,T] ) :- domain(...), % domény proměnných all_distinct(...)■ ...#=..., % omezeni % prohledávám' stavového prostoru labelingC.. .) . Knihovna pro CLP(FD) Domény proměnných Omezení Aritmetické omezení :- use_module(library(clpfd)). domainC Seznam, MinValue, MaxValue ) all_distinct( Seznam ) A* B + C #= D Procedura pro prohledávání stavového prostoru Hana Rudová, Logické programování 1,13. května 2011 labeling([].Seznam) Omezující podmínky Algebrogram Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: SEND + MORE MONEY ■ různá písmena mají přiřazena různé cifry ■ S a M nejsou 0 Proměnné: S,E,N,D,M,0,R,Y Domény: [1 ..9] pro S,M [0..9] pro E,N,D,0,R,Y 1 omezení pro nerovnost: a"l"l_di stinct([S, E, N,D,M,0, 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 SEND + MORE MONEY Hana Rudová, Logické programování 1,13. května 2011 Omezující podmínky Algebrogram: řešení :- use_module(library(clpfd)). donald(LD):- % domény LD=[D,0,N,A,L,G,E,R,B,T], domain(LD,0,9), domain([D,G,R],1,9), % omezeni all_distinct(LD), 100000*D + 10000*0 + 1000*N + 100*A + 10*L + D + 100000*C + 10000*E + 1000*R + 100*A + 10*L + D #= 100000*R + 10000*0 + 1000*B + 100*E + 10*R + T, % prohledáváni stavového prostoru labeling([] , LD). Hana Rudová, Logické programování 1,13. května 2011 Omezují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 časem (Start, End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly ■ příklad s konstantami: cumulative([task(0,2,2,l ,1), task(3,l ,4,1,2), task(5,l ,6,1,3)]) Start, Duration, End, Id musí být doménové proměnné s konečnými mezemi nebo celá čísla Hana Rudová, Logické programování 1,13. května 2011 Omezující podmínky Plánování Každý úkol má stanoven dobu trvání a nejdřívější čas, kdy může být zahájen. Nalezněte startovní čas každého úkolu tak, aby se jednotlivé úkoly nepřekrývaly. Úkolyjsou zadány následujícím způsobem: % ukol(Id,Doba,MinStart,MaxKonec) ukol(l,4,8,70). ukol(2,2,7,60) . ukol(3,1,2,25). ukol(4,6,5,55). ukol(5,4,l,45). ukol(6,2,4,35) . ukol(7,8,2,25). ukol(8,5,0,20). ukol(9,l,8,40). ukol(10,7,4,50). ukol(11,5,2,50). ukol(12,2,0, 35) . ukol(13,3,30,60). ukol(14,5,15,70). ukol(15,4,10,40). Kostra řešení: ukoly(Zacatky) :- domeny(Ukoly,Začátky,Tasks), cumulative(Tasks), labeling([],Začátky). domény(Ukoly,Začátky,Tasks) :- findal1(ukol(Id,Doba,MinStart.MaxKonec), ukol(Id,Doba,MinStart,MaxKonec), Úkoly), nastav_domeny(Ukoly,Začátky,Tasks). Hana Rudová, Logické programování 1,13. května 2011 70 Omezující podmínky Plánování: výstup tiskni(Úkoly,Začátky) :- priprav(Ukoly,Začátky,Vstup), quicksort(Vstup,Vystup), nl, tiskni(Vystup). priprav([] , [] , []) . při prav([ukol(Id,Doba,Mi nStart.MaxKonec)|Úkoly], [Z|Začátky], [ukol(Id,Doba,MinStart,MaxKonec,Z)IVstup]) :-priprav(Ukoly,Začátky,Vstup). tiskni ([]) :- nl . tiskni([V|Vystup]) :- V=ukol(Id,Doba,MinStart,MaxKonec,Z), K i s Z+Doba, formatC ~d: \t~d..~d \t(~d: ~d..~d)\n', [Id,Z,K,Doba,MinStart,MaxKonec] ), ti skni(Vystup). Hana Rudová, Logické programování I, 13. května 2011 71 Omezují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), quicksortl(Small, A1-[X|A2]), quicksortl(Big, A2-Z2). split(_X, [], [], []). split(X, [Y|T], [Y|Small], Big) :- greater(X,Y), !, split(X, T, Small, Big). split(X, [Y|T], Small, [Y|Big]) :- split(X, T, Small, Big). greater(ukol(_,_,_,_,Zl),ukol(_,_,_,_,Z2)) :- Z1>Z2. Hana Rudová, Logické programování 1,13. května 2011 72 Omezující podmínky Plánování a domény D.Ú. Plánování a precedence: precedence(Tasks) Napište predikát nastav_domeny/3, který na základě datové struktury [ukol (Id ,Doba,MinStart,MaxKonec) | Úkoly] vytvoří doménové proměnné Začátky pro začátky startovních dob úkolů a strukturu Tasks vhodnou pro omezení cumulative/1, jejíž prvky jsou úlohy ve tvaru task(Začátek,Doba,Konec,1,Id). % nastav_domeny(+Ukoly,-Začátky,-Tasks) nastav_domeny( [],[],[]). nastav_domeny([ukol(Id,Doba,Mi nStart.MaxKonec)|Úkoly],[Z|Začátky], [task(Z,Doba,K,l,Id)ITasks]) :-MaxStart is MaxKonec-Doba, Z in MinStart..MaxStart, K #= Z + Doba, nastav_domeny(Úkoly,Začátky.Tasks). Hana Rudová, Logické programování 1,13. května 2011 73 Omezující podmínky Kumulativní rozvrhování ■ cumulative([task(Start,Duration,End,Demand,Taskld) | Tasks], [li mi t (Li mi t)]) ■ Rozvržení úloh zadaných startovním a koncovým časem (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 nepřekročila Limit ■ Příklad s konstantami: cumulative([task(0,4,4,l,l),task(l,2,3,2,2),task(3,3,6,2,3),task(4,2,6,l,4)],[li mi t(3)]) 2 3 1 1 1 1 1 1 2 3 4 5 6 Hana Rudová, Logické programování 1,13. května 2011 75 Omezující podmínky Rozšiřte řešení př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řed B. % prec(IdA.IdB) prec(8,7). prec(6,12). prec(2,l). Pro určení úlohy v Tasks lze použít nthl(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) :- nthl(A,Tasks,task(ZA,DA,_KA,l,A)), nthl(B,Tasks,task(ZB,_DB,_KB,1,B)), ZA + DA #=< ZB, omezeni_precedence(Prec,Tasks). Hana Rudová, Logické programování 1,13. května 2011 74 Omezující podmínky Plánování a lidé Modifikujte řešení předchozího problému tak, že ■ odstraňte omezení na nepřekrývání úkolů ■ přidejte omezení umožňující řešení každého úkolu zadaným člověkem (každý člověk 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(l,2,[1,2,3,4,5]). clovek(2,l,[6,7,8,9,10]). clovek(3,2,[11,12,13,14,15]) 1ide(Tasks,Lide) :- findall(clovek(Kdo,Kapacita,Úkoly),clovek(Kdo,Kapacita,Úkoly), Lide) , omezeni_lide(Lide,Tasks). omezeni_lide([],_Tasks) . omezeni_1ide([clovek(_Id,Kapacita.UkolyCloveka)|Lide],Tasks) : -omezeni_clovek(UkolyCloveka,Kapaci ta,Tasks), omezeni_lide(Lide,Tasks). Hana Rudová, Logické programování 1,13. května 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 určené seznamem UkolyCloveka a pro takto vybrané úlohy sešle omezení cumulative/2 s danou kapacitou člověka Kapacita. Pro nalezení úlohy v Tasks lze použít nthl(N,Tasks,NtyPrvek) z kni hovny :- use_module(library(lists)) . omezen i _clovek (UkolyCloveka, Kapacita, Tas ks) : - omezeni_clovek(UkolyCloveka,Kapacita,Tasks,[]). omezeni_clovek([],Kapacita,_Tasks.TasksC) :- cumulative(TasksC,[limit(Kapacita)]). omezeni_clovek([U|UkolyCloveka],Kapacita,Tasks,TasksC) :- nthlCU,Tasks,TU), omezeni_clovek(UkolyCloveka,Kapacita,Tasks,[TU|TasksC]). Hana Rudová, Logické programování 1,13. května 2011 Omezující podmínky Stromy Uzly stromu Tree jsou reprezentovány termy ■ tree(Left,Value,Right): Left a Right jsou opět stromy, Value je ohodnocení uzlu ■ leaf(Value): Value je ohodnoceni uzlu ■ Příklad: 6 / \ / \ / \ 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, 1 3. května 2011 Stromy, grafy Stromy, grafy Stromy: hledáni prvku in(X,T) Predikát in(X,T) uspěje, pokud se prvek X nachází ve stromu T. Prvek X se nachází ve stromě T, jestliže ■ Xje listem stromu T, jinak leaf(X) ■ Xje kořen stromu T, jinak tree(i_eft,x,Right) ■ Xje menší než kořen stromu T, pak se nachází v levém podstromu T, jinak ■ X se nachází v pravém podstromu T in(X, leaf(X)) :- !. in(X, tree(_,X,_)) :- !. in(X, tree(Left, Root, Right) ) :- XV, pak vznikne nový strom s kořenem V, vpravo má leaf(X) (vlevo je []) pokud T=leaf(V) a XV, pak v novém stromě L ponechej a X přidej doprava (rekurzivně) pokud T=tree(L,V,R) a XV, !. add(leaf(V), X, tree(leaf (X) ,V, []) ) :- !. XV, !, add(R,X,Rl). add(tree(L,V,R), X, tree(Ll,V,R)) :-X true) 4. Procházej zbývající sousedy uzlu Uzel prochazej_sousedy([],_,_,_). prochazej_sousedy([V|T],Uzel,Graf,Parents) :- arg(V,Parents,Rodič), ( nonvar(Rodic) -> true ; Rodič = Uzel, arg(V,Graf.SousediV), prochazej_sousedy(SousediV,V,Graf,Parents) ), prochazej_sousedy(T,Uzel,Graf,Parents). Hana Rudová, Logické programování I, 13. května 2011 88 Stromy, grafy DÚ: Procházení grafu do šířky Napište predikát bfs(U,C,P) pro procházení grafu C do šířky z uzlu U. Výsledkem procházení je datová struktura P, která reprezentuje strom vzniklý při prohledávání grafu C do šířky (pro každý uzel stromu známe jeho rodiče). graf([2,3],[l,3],[l,2]). graf([2,4,6],[1,3],[2],[1,5], [4,6],[1,5]). 1--2 1—2 5—4 \ I I II \| | 6-1-2-3 3 3 U=2: rodič(2,empty,2) 5— 4 I 6- -1--2--3 U=4: rodič(4, 1, 2, empty, 4, 1) Poděkování Průsviky ze cvičení byly připraveny na základě materiálů dřívějších cvičících tohoto předmětu. Speciální poděkování patří ■ Adrianě Strejčkové Další podklady byly připraveny ■ Alešem Horákem ■ Miroslavem Nepilem ■ Evou Žáčkovou Hana Rudová, Logické programování I, 13, května 201 1 Stromy, grafy Hana Rudová, Logické programování I, 13, května 201 1