IBOl 3 Logické programování I Backtracking, unifikace, aritmetika (průsvitky ze cvičení) Hana Rudová jaro 2009 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 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. Sémantika logického programu: procedury = databáze faktů a pravidel = logické formule Hana Rudová, Logické programování I, 20. května 2009 3 Backtracking, unifikace, aritmetika Hana Rudová, Logické programování I, 20. května 2009 4 Backtracking, unifikace, aritmetika Sicstus Prolog minimum I Sicstus Prolog minimum II Spuštění interpretu: V unixu přidáme modul module add sicstus a spustíme příkazem sicstus Pracovním adresářem je aktuální (tam kde byl spuštěn). V MS Windows standardně z nabídky Start/Program s nebo pomocí ikony, 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. ■ Načtení programu: tzv. konzultace Editor není integrován, takže program editujeme externě ve svém oblíbeném editoru. Pak ho načteme z příkazové řádky v interpretu příkazem ?- consult(jmeno) . nebo pomocí zkrácené syntaxe ?- [jméno]. % (předpokládá se připona .pl) pokud uvádíme celé jméno případně cestu, dáváme jej do apostrofů ?- ['D:\prolog\moje\programy\jméno.pl'] . V MS Windows lze také pomocí nabídky File/Consult Hana Rudová, Logické programování I, 20. května 2009 Backtracking, unifikace, aritmetika Hana Rudová, Logické programování I, 20. května 2009 Backtracking, unifikace, aritmetika Sicstus Prolog minimum Příklad rodokmen Spouštění programů/procedur/predikátů je zápis dotazů, př. rodn cCpetr, filip). muz(petr) . rodn cCpetr, lenka). muz(fi lip). ?- muj_predikat(X,Y). rodn cCpavel, jan). muz(pavel). ?- suma(l,2,Y), vypisC'Vysledek je ',Y). rodn c(adam, petr). muz(jan) . Každý příkaz ukončujeme tečkou. rodn cCtomas, michal). muz(adam). rodn c(michal, radek). muz(tomas). Přerušení a zastavení cyklícího programu: Ctrl-C rodn c(eva, filip). muz(michal) Ukončení interpretu příkazem rodn cCjana, lenka). muz(radek). rodn cCpavla, petr). ?- halt. rodn cCpavla, tomas). zena(eva). rodn cClenka, vera). zena(lenka) otec(Otec,Dite) zena(pavla). zena(jana). zena(vera). rodič(Otec,Dite), muz(Otec). Hana Rudová, Logické programování I, 20. května 2009 Backtracking, unifikace, aritmetika Hana Rudová, Logické programování I, 20. května 2009 Backtracking, unifikace, aritmetika Backtracking: příklady Backtracking: řešení příkladů 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? ■ Kdo je otcem Petra? ■ Jaké děti má Pavla? ■ Ma Petr dceru? ■ Které dvojice otec-syn známe? Hana Rudová, Logické programování I, 20. května 2009 Backtracking, unifikace, aritmetika Backtracking: příklady II Predikát potomek/2: potomekCPotomek,Předek) :- rodic(Predek,Potomek). potomekCPotomek,Předek) :- rodic(Predek,X), potomekCPotomek,X). Naprogramujte predikáty ■ prababicka(Prababicka,Pravnouce) ■ nevíastni_bratr(NevJastni_bratr,Nevlastni_sourozenec) Řešení: prababicka(Prababicka,Pravnouce):-rodic(Prababicka,Prarodič), zena(Prababicka), rodič(Prarodič,Rodič), rodic(Rodic,Pravnouce). Hana Rudová, Logické programování I, 20. května 2009 Backtracking, unifikace, aritmetika Středníkem si vyžádáme další řešení I ?- otecCpetr,lenka). yes I ?- otecCpetr,jan). no I ?- otec(Kdo,petr). Kdo = adam ? ; no I ?- rodic(pavla.Dite). Dite = petr ? ; Dite = tomas ? ; no I ?- otecCpetr,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 ?- Hana Rudová, Logické programování I, 20. května 2009 Backtracking, unifikace, aritmetika Backtracking: řešení příkladů II nevlastni_bratr(Bratr,Sourozenec):-rodic_v(X,Bratr), muz(Bratr), rodic_v(X,Sourozenec) , /'■'•' tento test neni nutný, ale zvyšuje efektivitu '■'•'/ Bratr \== Sourozenec, rodic_v(Y,Bratr), Y \== X, rodic_v(Z,Sourozenec), Z \== X, Z \== Y. /'■'•' nevhodné umisteni testu - vypočet "bloudi" v neúspěšných vetvich nevíastni_bratr2(Bratr.Sourozenec):- rodic_v(X,Bratr), rodic_v(X,Sourozenec), rodic_v(Y,Bratr), rodic_v(Z,Sourozenec), Y \== X, Z \== X, Z \== Y, muz(Bratr). Hana Rudová, Logické programování I, 20. května 2009 Backtracking, unifikace, aritmetika Backtracking: prohledávání stavového prostoru ■ Zkuste předem odhadnout (odvodit) pořadí, v jakém 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 rodi c/2 následujícím predikátem rodic_v/2 rodic_v(X,Y):-rodic(X,Y),print(X),přint('? '). Pozorujte rozdíly v délce výpočtu dotazu nevJastni_bratr(filip,X) při změně pořadí testů v definici predikátu nevlastni_bratr/2 Hana Rudová, Logické programování I, 20. května 2009 13 Backtracking, unifikace, aritmetika | ?- nevlastni_bratrCX,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? 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? pe 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í I, 20. května 2009 15 Backtracking, unifikace, aritmetika Backtracking: řešení III /* varianta la '■'•'/ potomekCPotomek,Předek):-rodic(Predek,Potomek). potomekCPotomek,Předek):-rodic(Predek.X),potomekCPotomek,X). /'■'•' varianta lb - jine poradi odpovedi, neprimi potomci maji přednost '■'•'/ potomekCPotomek,Předek):-rodicCPredek.X),potomekCPotomek,X). potomekCPotomek,Předek):-rodicCPredek,Potomek). /'■'•' varianta 2a - leva rekurze ve druhé klauzuli, na dotaz potomekCX, pavla) výpise odpovedi, pak cykli '■'•'/ potomekCPotomek,Předek):-rodicCPredek,Potomek). potomekCPotomek,Předek):-potomekCPotomek,X),rodicCPredek.X). /'■'•' varianta 2b - leva rekurze v prvni klauzuli, na dotaz potomekCX, pavla) hned cykli '■'•'/ potomekCPotomek,Předek):-potomekCPotomek,X),rodicCPredek.X). potomekCPotomek,Předek):-rodicCPredek,Potomek). Hana Rudová, Logické programování I, 20. května 2009 14 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íus) 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í I, 20. května 2009 16 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í I, 20. května 2009 Backtracking, unifikace, aritmetika Mechanismus unifikace II suma(0,X,X). /*A*/ ?- suma(sCO),s(0),X0). s uma(s(X),Y,s(Z)):-s uma(X,Y,Z). /*B*/ 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(s(0)) X0 = s(sCO)) ; 2' dotaz z kroku 1. nejde unifikovat s hlavou klauzule B (1. argument) Hana Rudová, Logické programování I, 20. května 2009 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, 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 šije odvodit pomocí substitučních rovnic. Hana Rudová, Logické programování I, 20. května 2009 19 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í I, 20. května 2009 20 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 1 1. X =\= Y 12.1+2 =\= T - 2 13. 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í I, 20. května 2009 Backtracking, unifikace, aritmetika 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 :-Ca,,CprintCs(sC0))),,Cb,c))). Prefixovou notaci lze získat predikátem display/l. Vyzkoušejte display((a:-print(s(s(0))),b,c)). d i s p 1 ay ( 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. 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 Hana Rudová, Logické programování I, 20. května 2009 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), ■ 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, 20. května 2009 23 Backtracking, unifikace, aritmetika Hana Rudová, Logické programování I, 20. května 2009 24 Backtracking, unifikace, aritmetika 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 Seznamy, řez lastC X, S ) :- appendC _S1, [X], S). append([3,2] , [6], [3,2,6]). X=6, S=[3,2,6] ' prefix( SI, S2 ) :- appendC SI, _S3, S2). DÚ: suffix(Sl,S2) 1 memberC X, S ) :- appendC SI, [X|S2], S ). append([3,4,l], [2,6], [3,4,1,2,6]). X=2, S=[3,4,1,2,6] DÚ: adjacent(X,Y,S) 1 % 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í I, 20. května 2009 26 Seznamy a delete deleteC X, [X|S], S ). deleteC X, [Y|S], [Y|S1] ) :- deleteCX,S,S1). 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, [] , [] ) . deleteCX, [X|S], SI) :- !, deleteCX,S,SI) . deleteCX, [Y|S], [Y|S1] ) :- deleteCX,S,SI). 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, 20. května 2009 27 Seznamy, řez Hana Rudová, Logické programování I, 20. května 2009 LCO a akumulátor Akumulátor a sum_l i st (S, Sum) ■ 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'' length C Seznam, Délka ) :- length ( Seznam, 0, Délka ). % pomocný predikát length C [] , Délka, Délka ). % celková délka = započítaná délka lengthC [ H | T ], A, Délka ) :- AO is A + 1, lengthC T, AO, Délka ). ■ Přídavný argument se nazývá akumulátor Hana Rudová, Logické programování I, 20. května 2009 29 Seznamy, řez Výpočet faktoriálu fact(N, F) s akumulátorem: fact( N, F ) :- fact (N, 1, F ). factC 1, F, F ) :- !. factC N, A, F ) :- N > 1, Al is N * A, Nl is N - 1, factC Nl, Al, F ). Hana Rudová, Logické programování I, 20. května 2009 31 Seznamy, řez ?- 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 ) :- Al is A + H, sum_list( T, Al, Sum). Hana Rudová, Logické programování I, 20. května 2009 30 Seznamy, řez Prozkoumejte trasy výpočtu a navracení r(X) -write Crl). např. pomocí následujících dotazů (vždy si r(X) -p(X),write(r2). r(X) -write(r3). středníkem vyžádejte navracení): P(X) -write(pl). (1) X=l,r(X). (2) X=3,r(X). (3) X=0,r(X). (4) X= -6,r(X). P(X) -a(X),b(X), ! , c(X),d(X),write(p2) . ■ řez v predikátu p/1 neovlivní alternativy P(X) -write(p3). predikátu r/1 a(X) -write(al). ■ dokud nebyl proveden řez, alternativy a(X) -write(a2). predikátu a/l se uplatňují, př. neúspěch b(X) - X > 0, write(bl). b/1 v dotazu (3) b(X) - X < 0, write(b2). ■ při neúspěchu cíle za řezem se výpočet c(X) - X mod 2 =:= 0, write(cl) navrací až k volající proceduře r/1, viz (1) c(X) - X mod 3 =:= 0, write(c2) ■ alternativy vzniklé po provedení řezu se d(X) - abs(X) < 10, write(dl). d(X) - write(d2). zachovávají - další možnosti predikátu c/1 viz (2) a (4) Hana Rudová, Logické programování I, 20. května 2009 32 Seznamy, řez -write(rl) . -p(X),write(r2). -write(r3) . -write(pl) . -a(X),b(X),!, c(X) ,d(X) ,wn'te(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, wn'te(dl). write(d2). I ?- X=l,r(X). 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 X= 6, rC I ? rl X = -6 ? ; plr2 X = -6 ? ; alb2cldlp2r2 X = -6 ? ; d2p2r2 X = -6 ? ; c2dlp2r2 X = -6 ? ; d2p2r2 X = -6 ? ; r3 X = -6 ? ; no 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í verzi se tvrdilo: X=Z a X>=Y => Z=X 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í I, 20. května 2009 Hana Rudová, Logické programování I, 20. května 2009 Ř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 např. pomocí member( X, [1,2,3] ). memlCH,[H|_]). memlCH,[_|T]) :- meml(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ř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) Seznamy: i intersection (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 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í I, 20. května 2009 35 Seznamy, řez Hana Rudová, Logické programování I, 20. května 2009 36 Seznamy, řez Všechna řešení Všechna řešení, třídění, rozdílové seznamy % zOmeno, Při jmen i, Pohlavi , Vek, Prače, Fi rma) z(petr,novak.m,30, skladni k,škoda). z(pavel,novy,m,40.mechani k,škoda). z(rostislav,lucensky,m,50, techni k, škoda) . z(alena,veselá,z, 25, sekretářka, škoda) . zCjana, dankova, z, 35 , asistentka, škoda) . zOenka.meri nska, z, 35 , ucetni , škoda) . z(roman, maly,m,35.manažer,cs). z(alena,novotna,z,40,učitelka,zs_stara). z(david,novy,m,30,učitel,zs_stara). zCpetra,špičková,z,45,uklizečka,zs_stara). ■ Najděte jméno a příjmení všech lidí. ?- findall Qmeno-Pri jmeni, zQmeno, Pri jmeni ,_,_,_,_), L) . ?- bagofC Jmeno-Prijmeni, [S,V,Pr,F] A zQmeno, Pri jmeni , S, V, Pr, F) , L). ?- bagofC Jmeno-Prijmeni, [V,Pr,F] A zQmeno, Pri jmeni , S, V, Pr, F) , L ). ■ Najděte jméno a příjmení všech zaměstnanců firmy škoda a cs ?- findallC cQ,P,Firma), ( zQ , P, Fi rma) , ( Firma=skoda ; Fi rma=cs ) ), ?- bagofC >P, [S,V,Pr]A(zO,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). ?- setofC P-J, [S,V,Pr]A(z(],P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). Hana Rudová, Logické programování I, 20. května 2009 Všechna řešení, třídění, rozdílové seznamy Všechna řešení: příklady 1. Jaká jsou příjmení všech žen? 2. Kteří lidé mají více než 30 roků? Nalezněte jejich jméno a příjmení. 3. Nalezněte abecedně seřazený seznam všech lidí. 4. Nalezněte příjmení vyučujících ze zs_stara. 5. Jsou v databázi dva bratři (mají stejné příjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zaměstnance? 1. findall(Prijmeni, z(_,Prijmeni,z,_,_,_), L). 2. findall Qmeno-Pri jmeni , ( zQmeno, Pri jmeni ,_,Vek,_,_) , Vek>30 ), L) . 3. setofCP-J, [S,V,Pr,F]Az(],P,S,V,Pr,F), L). 4. findall(Prijmeni, ( z(_,PrijmeniP,zs_stara), (P=ucitel;P=ucitelka) ), L). 5. findall(b(]l-P,]2-P), ( zQl, P,m,_,_,_) ,zQ2 , P,m,_,_,_) , J1@l ), S). Hana Rudová, Logické programování I, 20. května 2009 39 Všechna řešení, třídění, rozdílové seznamy bubblesort(S,Sorted) swap(S,Sl) rekurzivně bubblesortem 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 bubblesortCS,Sorted) :- swap CS.Sl), !, % Existuje použitelný swap v S? bubblesortCSl, Sorted). bubblesortCSorted,Sorted). % Jinak je seznam seřazený swap([X,Y|Rest],[Y,X|Restl]) :-X>Y. swap([Z|Rest],[Z|Restl]) :-swapCRest,Restl). Hana Rudová, Logické programování I, 20. května 2009 % swap prvnich dvou prvků % nebo obecněji X@>Y, resp. gt(X,Y) % swap prvků až ve zbytku 40 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, 20. května 2009 41 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, S ). ■ 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, 20. května 2009 43 Všechna řešení, třídění, rozdílové seznamy DÚ:insertsort(S,Sorted) Neprázdný seznam S=[X|T] seřaďte tak, že ■ seřaďte tělo T seznamu S ■ vložte hlavu X do seřazeného těla tak, že výsledný seznam je zase seřazený. Víme: výsledek po vložení X je celý seřazený seznam. insertsortC[], []) . insertsort([X|T].Sorted) :- i nsertsort(T,SortedT), insert(X,SortedT,Sorted). insertCX,[YlSorted],[Y|Sortedl]) X > Y, ! , insertCX,Sorted,Sortedl). insertCX,Sorted,[XlSorted]). konec rekurze pro S=[] rekurzivně insertsortem insert(X,SortedT,Sorted) % seřazeni těla % vloženi X na vhodné mi sto Hana Rudová, Logické programování I, 20. května 2009 Všechna řešení, třídění, rozdílové seznamy reverse(Seznam, Opacny) % kvadratická složitost reverseC [], [] ) • reverseC [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). % lineárni složitost, rozdílové seznamy reverseC Seznam, Opacny ) :- reverseOC Seznam, Opacny-[] ). reverseOC [] , S-S ) . reverseOC [ H | T ], Opacny-OpacnyKonec ) :- reverseOC T, Opacny-[ H | OpacnyKonec] ). Hana Rudová, Logické programování I, 20. května 2009 Všechna řešení, třídění, rozdílové seznamy DÚ: pal i ndrom(L) Napište predikát palindrom(Seznam), který uspěje pokud se Seznam čte stejně zezadu i zepředu, př. [a,b,c,b,a] nebo [1 2,1 5,1,1,1 5,1 2] pal indrom(Seznam) :- reverse(Seznam,Seznam). Hana Rudová, Logické programování I, 20. května 2009 Všechna řešení, třídění, rozdílové seznamy Vstup/výstup, databázové operace, rozklad termu quicksort pomocí rozdílových seznamů Neprázdný seznam S seřaďte tak, že ■ vyberte nějaký prvek X z S; rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky ■ seřaďte Small do SortedSmall ■ seřaďte Big do SortedBig ■ setříděný seznam vznikne spojením SortedSmall a [XISortedBig] quicksortCS, Sorted) :- quicksortl(S,Sorted-[]). quicksortl([],Z-Z). quicksortl([X|T], A1-Z2) :- splitCX, T, Small, Big), quicksortlCSmall, A1-[X|A2]), quicksortl(Big, A2-Z2). append(A1-A2, A2-Z2, A1-Z2). Hana Rudová, Logické programování I, 20. května 2009 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í I, 20. května 2009 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í I, 20. května 2009 49 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 : yes I ?- [soubor]. % Consulting /home/hanka/soubor.pl... % consulted /home/hanka/soubor.pl in module user, 0 msec % 376 bytes yes I ?- listingCfakt/2). fakt(mi rek, 18). faktCpavel, 4). yes Hana Rudová, Logické programování I, 20. května 2009 50 Vstup/výstup, databázové operace, rozklad termu Implementace: vstup/výstup uloz_do_souboru( Soubor ) :-seeingC StaryVstup ), tellingC StaryVystup ), see( user ), tel 1( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_file, seen, told, tellC StaryVystup ), see( StaryVstup ). process_term(end_of_file) :- !. process_term( Term ) :- writeC Term ), writeC'.'), nl. Hana Rudová, Logické programování I, 20. května 2009 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 ) asserta( Klauzule ) assertz( Klauzule ) retract( Klauzule ) přidání Klauzule do programu přidání na začátek přidání na konec smazání klauzule unifikovatelné s Klauzule Pozor: nadměrné použití těchto operací snižuje srozumitelnost programu Hana Rudová, Logické programování I, 20. května 2009 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). |: pravidloCX.Y) :- fakt(X.Y). I : yes | ?- 1 isting(fakt/2). faktCpavel, 4). yes | ?- listing(pravidlo/2). pravidlo(A, B) :- fakt(A, B). yes | ?- clauseC praviďlo(A.B) , C) . C = fakt(A,B) ? yes Hana Rudová, Logické programování I, 20. května 2009 53 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, 20. května 2009 55 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í I, 20. května 2009 54 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í I, 20. května 2009 56 Vstup/výstup, databázové operace, rozklad termu subterm(S,T) Napište predikát subterm(S,T) pro termy S aT 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), není seznam (T\=[_|_]), a S je podtermem některého argumentu T. | ?- subterm(sin(3),b(c,2,[1,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\=[_|_], T=..[_|Argumenty], subterm(S.Argumenty). Hana Rudová, Logické programování I, 20. května 2009 57 Vstup/výstup, databázové operace, rozklad termu uni f y (A, B) Napište predikát uni fy(A, B), který unifikuje termy A a B. | ?- 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=..[FA|ArgA], B=..[FB|ArgB], FA==FB, 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 C[1,3,si n(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 C[HA|TA],[HB|TB]) :- !, same(HA,HB), same(TA,TB). same(A.B) :- A=..[FA|ArgA], B=..[FB|ArgB], FA==FB, same(ArgA,ArgB). Hana Rudová, Logické programování I, 20. května 2009 58 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, 20. května 2009 59 Vstup/výstup, databázové operace, rozklad termu Hana Rudová, Logické programování I, 20. května 2009 60 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( Cifry ) :-domai n(...), constraints(...) , TabelingC.. .) . ■ Knihovna pro CLP(FD) ■ Domény proměnných ■ Omezení ■ Aritmetické omezení :- use_module(libraryCclpfd)). domain C Seznam, MinValue, MaxValue ) a"l"l_di sti nct( Seznam ) A* B + C #= D Procedura pro prohledávání stavového prostoru labe1ing([], [xi, X2, X3]) Hana Rudová, Logické programování I, 20. května 2009 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í I, 20. května 2009 Omezující podmínky Algebrogram: řešení :- use_module(libraryCclpfd)). donald(LD):- % domény LD=[D,0,N,A,L,C,E,R,B,T], domain(LD,0,9), domain([D,G,R],1,9), % omezeni a"l"l_distinct(l_D) , 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 TabelingCC] , LD). Hana Rudová, Logické programování I, 20. května 2009 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). uko"l(3 ,1,2 ,25) . uko"l(4,6, 5 , 55) . ukol(6,2,4,35). úkol (7,8,2,25) . uko"l(8, 5 ,0,20) . ukol(10,7,4,50). ukol(11,5,2,50). ukol(12,2,0,35). ukol(14,5,15,70). ukol(15,4,10,40). ukol(5,4,l,45) . ukol(9,l,8,40). ukol(13,3,30,60). Kostra řešení: ukoly(Zacatky) domény(Úkoly,Začátky,Doby), seriál ized(Začátky,Doby), labeling([],Začátky). domény(Úkoly,Začátky,Doby) :- findal1(ukol(Id,Doba,MinStart.MaxKonec) , ukol(Id,Doba,MinStart,MaxKonec), Úkoly), nastav_domeny(Úkoly,Začátky,Doby). Hana Rudová, Logické programování I, 20. května 2009 65 Omezující podmínky Plánování: výstup II quicksort(S, Sorted) :- quicksortl(S,Sorted-[]). quicksortl([],Z-Z). quicksortl([X|Tail], A1-Z2) :- spi i t(X, Tail, Small, Big), quicksortKSmall , A1-[X|A2]), quicksortl(Big, A2-Z2). split(_X, [], [], []). split(X, [Y I T], [Y I Small], Big) :- split(X, [YIT], Small, [Y|Big]) :- greater(X.Y), !, split(X, T, Small, Big). split(X, T, Small, Big). greater(ukol(_ ,Zl),ukol(_ ,Z2)) Z1>Z2. Hana Rudová, Logické programování I, 20. května 2009 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([], [] , []) . pri 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([VIVystup]) :- 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, 20. května 2009 66 Omezující podmínky Plánování a domény nastav_domeny( [] ,[],[]). nastav_domeny([U|Úkoly],[Z|Začátky],[Doba|Doby]) U=ukol(_Id,Doba,MinStart,MaxKonec), MaxStart is MaxKonec-Doba, Z in MinStart..MaxStart, nastav_domeny(Úkoly,Začátky,Doby). Hana Rudová, Logické programování I, 20. května 2009 Omezující podmínky Plánování a precedence Plánování a lidé 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 zjištění parametrů úlohy lze použít např. nth(N,Seznam,NtyPrvek) z knihovny :- use_module(library(lists)) . precedence(Začátky,Doby) :- findall(prec(A,B),prec(A,B),P), omezeni_precedence(P,Začátky,Doby). omezeni_precedence([],_Zacatky,_Doby). omezeni_precedence([prec(A,B)|Prec],Začátky,Doby) :- nth(A,Začátky,ZA), nth(B,Začátky,ZB), nth(A,Doby,DA), ZA + DA #< ZB, omezeni_precedence(Prec,Začátky). Hana Rudová, Logické programování I, 20. května 2009 69 Omezující podmínky Plánování a lidé (pokračování) omezeni_clovek(IdUkoly, Začátky, Doby) : - omezeni_clovek(IdUkoly,Začátky,Doby, [] , []) . % omezeni_clovek(IdUkoly,Začátky,Doby,ClovekZ,ClovekD) omezeni_clovek([],_Zacatky,_Doby,ClovekZ,ClovekD) :- serialized(ClovekZ,ClovekD). omezeni_clovek([U|IdUkoly],Začátky,Doby,ClovekZ,ClovekD) :- nth(U,Začátky,Z), nth(U,Doby,D), omezeni_clovek(IdUkoly,Začátky,Doby,[Z|ClovekZ],[D|ClovekD]). Rozšiřte řešení problému tak, aby mohl každý člověk zpracovávat několik úkolů dle jeho zadané kapacity. % clovek(Id,Kapacita,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]). Hana Rudová, Logické programování I, 20. května 2009 71 Omezující podmínky 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 jeden úkol) % clovek(Id,IdUkoly) ... clovek Id zpracovává úkoly v seznamu IdUkoly clovekCl, [1,2,3,4,5]). clovek(2,[6,7,8,9,10]). clovek(3,[11,12,13,14,15]). li de(Začátky,Doby,Li de) :- fi ndal1(clovek(Kdo,IdUkoly),clovek(Kdo,IdUkoly), Li de), omezeni_1i de(Li de,Začátky,Doby). omezeni_lide([],_Zacatky,_Doby). omezeni_1i de([Clovek|Lide],Začátky,Doby) :- Clovek=clovek(_Id,IdUkoly), omezeni_clovek(IdUkoly,Začátky,Doby), omezeni_1i de(Li de,Začátky,Doby). Hana Rudová, Logické programování I, 20. května 2009 70 Omezující podmínky 1 i de(Začátky,Doby,Lide) :- fi ndal1(clovek(Kdo,Kapacita,IdUkoly),clovek(Kdo,Kapacita,IdUkoly), Li dc omezeni_1i de(Li de,Začátky,Doby). omezeni_lide([],_Zacatky,_Doby). omezeni_1ide([clovek(_Id,Kapacita,IdUkoly)|Lide],Začátky,Doby) :-omezeni_clovek(IdUkoly,Kapaci ta,Začátky,Doby), omezeni_1i de(Li de,Začátky,Doby). omezeni_clovek(IdUkoly,Kapacita,Začátky,Doby) :- omezeni_clovek(IdUkoly,Kapacita,Začátky,Doby,[],[]). omezeni_clovek([],Kapacita,_Zacatky,_Doby,ClovekZ,ClovekD) :- 1ength(ClovekZ,Delka), 1 i stOfl(Delka,Li stOf1), cumulative(ClovekZ,ClovekD,Li stOf1,Kapacita). omezeni_clovek([U|IdUkoly],Kapacita,Začátky,Doby,ClovekZ,ClovekD) :- nth(U,Začátky,Z), nth(U,Doby,D), omezeni_clovek(IdUkoly.Kapacita,Začátky,Doby,[Z|ClovekZ],[D|ClovekD]). listOf1(0,[]) :- !. list0fl(D,[1|L]) :- Dl i s D-l, 1 istOf1(D1,L). Hana Rudová, Logické programování I, 20. května 2009 72 Omezující podmínky Stromy, grafy Stromy: hledáni prvku in(X.Tree) Napište predikát in(X,Tree), který uspěje, pokud se prvek X nachází v Tree. 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 má nový strom kořen V a vpravo se nachází 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(_,V,R) a XV, !. add(leaf(V), X, tree(leaf(X),V,[]) ) :- !. add(tree(L,V,R), X, tree(L,V,Rl)) :- X>V, !, add(R,X,Rl). add(tree(L,V,R), X, tree(Ll,V,R)) :- add(L,X,LI). Hana Rudová, Logické programování I, 20. května 2009 Stromy, grafy Procházení stromů Napište predikát traverse(Tree, List), který projde traversálně strom Tree a v seznamu List pak obsahuje všechny prvky tohoto stromu. Pořadí preorder: nejprve uzel, pak levý podstrom, nakonec pravý podstrom (preorder) Procházení stromů ?- traverse(tree(treeOeaf (1) , 2 , treeOeaf (3) ,4,leaf(5))) ,6 tree(]eaf(7) ,8,leaf(9))) , [6,2,1,4,3,5,8,7,9]) traverse(T,Pře):- t_pre(T,Pře,[]). t_pre([],S,S). t_preOeaf(V) , [V|S] ,S) . t_pre(tree(L,V,R),[V|S],S2):- t_pre(L,S,Sl), t_pre(R,Sl,S2) . Použit princip rozdílových seznamů Hana Rudová, Logické programování I, 20. května 2009 6 / \ / \ / \ 2 8 % V=2, S=[1,4,3,5|S2] /\ /\ % S=[1|S1] 1 4 7 9 % S1=[4,3,5|S2] / \ 3 5 Stromy, grafy traverse(T,Pře):- t_pre(T,Pře,[]). t_pre([],S,S). t_preOeaf(V) , [V|S] ,S) . t_pre(tree(L,V,R),[V|S],S2):- t_pre(L,S,Sl), t_pre(R,Sl,S2). 6 / \ / \ / \ 2 8 % V=2, S=[1,4,3,5|S2] / \ / \ % S=[1|S1] 1 4 7 9 % S1=[4,3,5|S2] / \ 3 5 Modifikuje algoritmus tak, aby byly uzly vypsány v pořadí inorder (nejprve levý podstrom, pak uzel a nakonec pravý podstrom), tj. [1,2,3,4,5,6,7,8,9] traverse(T,In):- t_in(T,In,[]). t_pre([],S,S). t_in(leaf(V) , [V|S] ,S) . t_in(tree(L,V,R),S,S2) :- t_in(L,S,[V|S1]), t_in(R,Sl,S2). Hana Rudová, Logické programování I, 20. května 2009 78 Stromy, grafy DÚ: Procházení stromu postorder Modifikuje algoritmus tak, aby byly uzly vypsány v pořadí postorder (nejprve levý podstrom, pak pravý podstrom a nakonec uzel), tj. [1,3,5,4,2,7,9,8,6] traverse_post(T,Post):- t_post(T,Post,[]). t_pre([],S,S). t_postOeaf(V) , [V|S] ,S) . t_post(tree(L,V,R),S,S2):-t_post(L,S,Sl) , t_post(R,Sl,[V|S2]). 6 / \ / \ / \ 2 8 / \ / \ 14 7 9 / \ 3 5 Reprezentace grafu Reprezentace grafu: pole následníků uzlů Grafy nebudeme modifikovat, tj. pro reprezentaci pole lze využít term (Orientovaný) neohodnocený graf graf([2,3],[l,3],[l,2]). 1--2 \ I graf([2,4,6],[1,3],[2],[1,5],[4,6],[1,5]). 5— 4 I I 6- -1--2--3 Hana Rudová, Logické programování I, 20. května 2009 Stromy, grafy ?- functorCCraf,graf,PocetUzlu). ?- argCUzel,Graf.Sousedi). 1 (Orientovaný) ohodnocený graf [Soused-Ohodnoceni|Sousedi] graf([2-l,3-2],[1-1,3-2],[1-2,2-2]). grafC[2-1,4-3,6-1],[1-1,3-2],[2-2],[1-3,5-1],[4-1,6-2],[1-1,5-2]). Hana Rudová, Logické programování I, 20. května 2009 80 Stromy, grafy Procházení grafu do hloubky Napište predikát dfs(U,C,P) pro procházení grafu C do hloubky z uzlu U. Výsledkem procházení je datová struktura P, která reprezentuje strom vzniklý při prohledávání do hloubky (pro každý uzel stromu známe jeho rodiče). Datová struktura pro rodiče uzlů: ■ při reprezentaci rodičů lze využít term s aritou odpovídající počtu uzlů ■ iniciálně jsou argumentu termu volné proměnné ■ na závěr je v N-tém argumentu uložen rodič N-tého uzlu (iniciální uzel označíme empty) graf([2,3],[1,3],[1,2]). graf([2,4,6],[1,3],[2],[1,5],[4,6],[1,5]). 1--2 1—2 5—4 5 4 \ I \ II II \| \ 6--1--2--3 6--1--2--3 3 3 U=4: rodic(4, 1, 2, empty, 6, 1) U=2: rodič(2,empty,1) Hana Rudová, Logické programování I, 20. května 2009 81 Stromy, grafy Procházení grafu do hloubky: algoritmus I Procházení grafu z uzlu U ■ Vytvoříme term pro rodiče (všichni rodiči jsou zatím volné proměnné) ■ Uzel U má prázdného rodiče a má sousedy S ■ Procházíme (rekurzivně) všechny sousedy v S dfs(U,G,P) :- f unctor(C,graf,Počet), f unctor(P,rodiče,Počet), argCU.C,Sousedi), argCU,P,empty), prochazej_sousedy(Sousedi,U,C,P). Hana Rudová, Logické programování I, 20. května 2009 82 Stromy, grafy Procházení grafu do hloubky: algoritmus II Procházení sousedů S uzlu U 1. Uzel Vje první soused 2. Zjistíme rodiče uzlu V 3. Pokud jsme V ještě neprošli (tedy nemá rodiče a platí var(Rodic)), tak (a) nastavíme rodiče uzlu V na U (b) rekurzivně procházej všechny sousedy uzlu V 4. Procházej zbývající sousedy uzlu U prochazej_sousedy([],_,_,_). prochazej_sousedy([V|T],U,C,P) :- arg(V,P,Rodič), ( nonvar(Rodic) -> ; Rodič = U, arg(V,G,SousediV), prochazej_sousedy(Sousedi V,V,C,P) ), prochazej_sousedy(T,U,C,P). Hana Rudová, Logické programování I, 20. května 2009 83 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,4,6],[1,3],[2],[1,5],[4,6],[1,5]). graf([2,3],[l,3],[l,2]). 1--2 1--2 \ I I \l I 3 3 U=2: rodic(2,empty,2) 5—4 5--4 I I I 6__!__2--3 6__i__2 —3 11=4: rodic(4, 1, 2, empty, 4, 1) Hana Rudová, Logické programováni I, 20. května 2009 Stromy, grafy 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, 20. května 2009 85