IB01 3 Logické programování I (průsvitky ze cvičení) Hana Rudová jaro 2009 Backtracking, unifikace, aritmetika 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í I, 20. května 2009 3 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. Sémantika logického programu: procedury = databáze faktů a pravidel = logické formule Hana Rudová, Logické programování I, 20. května 2009 4 Backtracking, unifikace, aritmetika Sicstus Prolog minimum I ■ Spuštění interpretu: V unixu přidáme modul module add sicstus a spustíme příkazem si cstus Pracovním adresářem je aktuální (tam kde byl spuštěn). V MS Windows standardně z nabídky Start/Programs 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. Hana Rudová, Logické programování I, 20. května 2009 5 Backtracking, unifikace, aritmetika Sicstus Prolog minimum II ■ 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řípona .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 6 Backtracking, unifikace, aritmetika Sicstus Prolog minimum III ■ Spouštění programů/procedur/predikátů je zápis dotazů, př. ?- muj_predikat(X,Y). ?- suma(l,2,Y), vypis('Výsledek je ',Y). Každý příkaz ukončujeme tečkou. ■ Přerušení a zastavení cyklícího programu: Ctrl-C ■ Ukončení interpretu příkazem ?- halt. Hana Rudová, Logické programování I, 20. května 2009 7 Backtracking, unifikace, aritmetika Příklad rodokmen rodic(petr, filip). muz(petr). rodic(petr, lenka). muz(filip). rodi c(pavel, j an). muz(pavel). rodic(adam, petr). muz(jan). rodic(tomas, michal). muz(adam). rodic(michal, radek). muz(tomas). rodic(eva, filip). muz(mi chal). rodic(jana, lenka). muz(radek). rodic(pavla, petr). rodi c(pavla, tomas). zena(eva). rodic(lenka, vera). zena(lenka). zena(pavla). zena(jana). zena(vera). otec(Otec,Dite) :- rodic(Otec,Dite), muz(Otec). Hana Rudová, Logické programování I, 20. května 2009 8 Backtracking, unifikace, aritmetika Backtracking: pří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? ■ 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 9 Backtracking, unifikace, aritmetika Backtracking: řešení příkladů 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(Otec,Syn),muz(Syn). Syn = fi lip, Otec = petr ? ; Syn = jan, Otec = pavel ? ; Syn = petr, Otec = adam ? ; Syn = mi chal, Otec = tomas ? ; Syn = radek, Otec = michal ? ; no I ?- Hana Rudová, Logické programování I, 20. května 2009 10 Backtracking, unifikace, aritmetika Backtracking: příklady II Predikát potomek/2: potomek(Potomek,Předek) :- rodic(Předek,Potomek). potomek(Potomek,Předek) :- rodic(Predek,X), potomek(Potomek,X). Naprogramujte predikáty ■ prababicka(Prababicka,Pravnouce) ■ neviastni_bratr(Neviastni_bratr,Nevíastni_sourozenec) Řešení: prababicka(Prababicka,Pravnouce):-rodic(Prababička,Prarodič), zena(Prababicka), rodi c(Prarodi c,Rodi c), rodi c(Rodi c,Pravnouce). Hana Rudová, Logické programování I, 20. května 2009 Backtracking, unifikace, aritmetika Backtracking: řešení příkladů II nevlastni_bratr(Bratr,Sourozenec):-rodi c_v(X,Bratr), muz(Bratr), rodic_v(X,Sourozenec), /* tento test neni nutný, ale zvyšuje efektivitu */ Bratr \== Sourozenec, rodi c_v(Y,Bratr), Y \== X, rodic_v(Z,Sourozenec), Z \== X, Z \== Y. /* nevhodné umisteni testu - vypočet "bloudi" v neúspěšných větvich nevíastni_bratr2(Bratr,Sourozenec):- rodi c_v(X,Bratr), rodic_v(X,Sourozenec), rodi c_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 12 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 rodic/2 následujícím predikátem rodic_v/2 rodic_v(X,Y):-rodič(X,Y),print(X),print('? '). Pozorujte rozdíly v délce výpočtu dotazu nevlastni_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 Backtracking: řešení III /* varianta la */ potomek(Potomek,Předek):-rodic(Predek,Potomek) . potomek(Potomek,Předek):-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):-rodic(Predek,Potomek). /* varianta 2a - leva rekurze ve druhé klauzuli, na dotaz potomek(X,pavla) výpise odpovedi, pak cykli */ potomek(Potomek,Předek):-rodic(Predek,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):-rodic(Predek,Potomek). Hana Rudová, Logické programování I, 20. května 2009 14 Backtracking, unifikace, aritmetika I ?- nevlastni_bratr(X,Y). petr? petr? petr? petr? eva? petr? jana? X = fi lip, 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? petr? X = fi lip, 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, 20. května 2009 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,plus) 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(s(X),Y,s(Z)):-suma(X,Y,Z). /-klauzule B*/ pomocí substitučních rovnic při odvozování odpovědi na dotaz ?- suma(s(0),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(s(X),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(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(s(0)) ; 2' dotaz z kroku 1. nejde unifikovat s hlavou klauzule B (1. argument) no Hana Rudová, Logické programování I, 20. května 2009 18 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) . kolikje 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áty již 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. =:=/2 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 7. 1 + 1 = 1 + 1 13. 1 <= 2 2. X is Y + 1 8. 1 + 1 is 1 + 1 3. X = Y 9. 1 + 2 =:= 2 + 1 4. X == Y 10. X \== Y 5. 1 + 1 = 2 1 1. X =\= Y 6. 2 = 1 + 1 1 2. 1 + 2 =\= 1 - 2 17. sin(X) =:= sin(2+Y) 14. 1 =< 2 1 5. sin(X) is sin(2) 16. 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 21 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 is 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 22 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:-přint(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:-přint(s(s(0))),b,c)). d i s play(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, 20. května 2009 23 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 24 Backtracking, unifikace, aritmetika Seznamy, řez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) :- append( SI, S2, S3). Napište následující predikáty pomocí append/3: ■ last( X, S ) :- append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] ■ prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2) ■ member( X, S ) :- append( 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) ■ % sublist(+S,+ASB) sublist(S,ASB) :- append( AS, B, ASB ), append( 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, řez Seznamy a delete delete( X, [X|S], S ). delete( X, [Y|S], [Y|S1] ) :- delete(X,S,SI). 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). delete( _X, [] , [] ). delete( X, [X|S], SI) :- !, delete(X,S,SI). delete( X, [Y|S], [Y|S1] ) :- delete(X,S,SI). Hana Rudová, Logické programování I, 20. května 2009 27 Seznamy, řez 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é ■ p( ...):- ... % žádné rekurzivní voláni v těle klauzule p( ...):- ... % žádné rekurzivni voláni v těle klauzule p(...) :- !, p( ... ). % řez zajišťuje determinismus ■ Tento typ rekurze lze převést na iteraci Hana Rudová, Logické programování I, 20. května 2009 28 Seznamy, řez LCO a akumulátor Reformulace rekurzivní procedury, aby umožnila LCO Výpočet délky seznamu length( Seznam, Délka ) length( [] , 0 ) . length( [ H | T ], Délka ) :- length( T, DelkaO ), Délka is 1 + DelkaO. Upravená procedura, tak aby umožnila LCO: % length( Seznam, ZapocitanaDelka, CelkovaDelka ): % CelkovaDelka = ZapocitanaDelka + počet prvků v Seznam'' length( Seznam, Délka ) :- length( Seznam, 0, Délka ). % pomocný predikát length( [] , Délka, Délka ). % celková délka = započítaná délka length( [ H | T ], A, Délka ) :- A0 is A + 1, length( T, A0, Délka ). Přídavný argument se nazývá akumulátor Hana Rudová, Logické programování I, 20. května 2009 29 Seznamy, řez Akumulátor a sum_l i st(S, Sum) ?- sum_list( [2,3,4], Sum ). bez akumulátoru: sum_li st( [], 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 ). sunuli st( [H|T], A, Sum ) :- AI is A + H, sum_list( T, AI, Sum). Hana Rudová, Logické programování I, 20. května 2009 30 Seznamy, řez Výpočet faktoriálu fact(N, F) s akumulátorem: fact( N, F ) :- fact (N, 1, F ). fact( 1, F, F ) :- !. fact( N, A, F ) :- N > 1, Al is N * A, Nl is N - 1, fact( Nl, Al, F ). Hana Rudová, Logické programování I, 20. května 2009 31 Seznamy, řez r (X) r (X) r (X) -wri te(rl) . -p(X),write(r2) -wri te(r3) . 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). (2) X=3,r(X). (3) X=0,r(X). (4) X= -6,r(X) p(X):-write(pl). p(X):-a(X),b(X),!, c(X),d(X),write(p2). ■ fez 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ňuji, pr. neúspech b(X):- X > 0, write(bl). b/1 v dotazu (3) b(X):- X < 0, write(b2). 1 při neúspěchu cíle za řezem se výpočet navrací až k volající proceduře r/1, viz (1) 1 alternativy vzniklé po provedení řezu se 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 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):-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 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- 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 I ?- X= -6, r rl X = -6 ? ; plr2 X = -6 ? ; alb2cldlp2r2 X = -6 ? ; d2p2r2 X = -6 ? ; c2dlp2r2 X = -6 ? ; d2p2r2 X = -6 ? ; r3 X = -6 ? ; no Hana Rudová, Logické programování I, 20. května 2009 33 Seznamy, řez Ř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 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, Z) : -X>=Y, ! ,Z=X. max(X,Y,Y):-Y>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 34 Seznamy, řez 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] ). meml(H,[H|_]). meml(H,[_|T]) :- meml(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). mem2(H,[H|_]) mem2(H,[_|T]) mem2(H,T). mem3(H,[K|_]) :- H==K. mem3(H,[K|T]) :- H\==K, mem3(H,T). Hana Rudová, Logické programování I, 20. května 2009 35 Seznamy, řez Seznamy: 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 Hana Rudová, Logické programování I, 20. května 2009 36 Seznamy, řez Všechna řešení, třídění, rozdílové seznamy Všechna řešení % z(Jmeno, Při jmeni ,Pohlavi,Vek,Prače, Fi rma) z(petr,novak,m,30,skladnik,škoda). z(pavel,novy,m,40,mechanik,š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,uci telka,zs_stara). z(davi d,novy,m,30,uci tel,zs_stara). z(petra,spi ckova,z,45,uklizecka,zs_stara). ■ Najděte jméno a příjmení všech lidí. ?- findal1(Jmeno-Prijmeni, zQmeno, Pri jmeni,_,_,_,_), L) ■ ?- bagof( Jmeno-Prijmeni, [S,V,Pr,F] a z(Jmeno,Prijmeni,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( c O, P, Firma), ( z O , P, Fi rma) , ( Firma=skoda ; Fi rma=cs ) ), ?- 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, 20. května 2009 38 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. findal1(Přijmeni, z(_,Přijmeni,z,_,_,_), L). 2. findal1(Jmeno-Prijmeni, ( z(Jmeno,Přijmeni,_,Vek,_,_), Vek>30 ), L). 3. setofCP-J, [S,V,Pr,F]Az(J,P,S,V,Pr,F), L ). 4. findal1(Přijmeni, ( z(_,PřijmeniP,zs_stara), (P=ucitel;P=ucitelka) ), L). 5. findall(b(Jl-P,J2-P), ( z(Jl, 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) 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; swap(S,Sl) a seřaďte SI rekurzivně bubblesortem ■ pokud neexistuje žádný takový pár sousedních prvků X a Y, pak je S seřazený seznam bubblesort(S,Sorted) :- swap (S,S1), !, % Existuje použitelný swap v S? bubblesort(Sl, Sorted). bubblesort(Sorted,Sorted). % Jinak je seznam seřazený swap([X,Y|Rest],[Y,X|Restl]) :-X>Y. swap([Z|Rest],[Z|Restl]) :-swap(Rest,Restl). % swap prvnich dvou prvků % nebo obecněji X@>Y, resp. gt(X,Y) % swap prvků až ve zbytku Hana Rudová, Logické programování I, 20. května 2009 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 [X|SortedBig] konec rekurze pro S=[] např. vyberte hlavu S spi it(X, Seznam, Small,Big) rekurzivně quicksortem rekurzivně quicksortem append qui cksort ([] , []) . quicksort([X|T], Sorted) :- split(X, Tail, Small, Big), quicksort(Smal1, SortedSmall), quicksort(Big, SortedBig), append(SortedSmall, [X|SortedBig], Sorted) split(X, [], [], []). split(X, [Y|T], [Y|Small], Big) :- X>Y, !, split(X, T, Small, Big). split(X, [Y|T], Small, [Y|Big]) :- split(X, T, Small, Big). Hana Rudová, Logické programování I, 20. května 2009 41 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 konec rekurze pro S=[] ■ seřaďte tělo T seznamu S rekurzivně insertsortem ■ vložte hlavu X do seřazeného těla tak, insert(X,SortedT,Sorted) že výsledný seznam je zase seřazený. Víme: výsledek po vložení X je celý seřazený seznam. insertsort([], []) . insertsort([X|T],Sorted) :- insertsort(T,SortedT), % seřazeni těla insert(X,SortedT,Sorted). % vloženi X na vhodné místo insert(X,[Y|Sorted],[Y|Sortedl]) :-X > Y, !, i nsert(X,Sorted,Sortedl). insert(X,Sorted,[X|Sorted]). Hana Rudová, Logické programování I, 20. května 2009 42 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 Z1 A2 ?- append( [1,2,3|Zl]-Zl, [4,5|Z2]-Z2, S ). append( Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 append( [l,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 reverse(Seznam, Opacny) % kvadratická složitost reverse( [] , [] ) . reverse( [ H | T ], Opacny ) :- reverse( T, OpacnyT ), append( OpacnyT, [ H ], Opacny ). % lineárni složitost, rozdilové seznamy reverse( Seznam, Opacny ) :- reverseO( Seznam, Opacny-[] ). reverseO( [], S-S ). reverseO( [ H | T ], Opacny-OpacnyKonec ) :- reverseO( T, Opacny-[ H | OpacnyKonec] ). Hana Rudová, Logické programování I, 20. května 2009 44 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 45 Všechna řešení, třídění, rozdílové seznamy 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 [X|SortedBig] quicksort(S, Sorted) :- quicksortl(S,Sorted-[]). quicksortl([],Z-Z). quicksortl([X|T], A1-Z2) :- spi i t(X, T, Small, Big), qui cksortKSmal 1 , AI- [X | A2]) , quicksortl(Big, A2-Z2). append(Al-A2, A2-Z2, A1-Z2) . Hana Rudová, Logické programování I, 20. května 2009 46 Všechna řešení, třídění, rozdílové seznamy Vstup/výstup, databázové operace, rozklad termu Ctení ze souboru process_file( Soubor ) :- seeing( StarySoubor ), see( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_fi1e, i ■ » seen, see( StarySoubor ). repeat. repeat :- repeat. % zjištěni aktivního proudu % otevřeni souboru Soubor % čteni termu Term % manipulace s termem % je konec souboru? % uzavřeni souboru % aktivace původniho proudu % vestavěný predikát Hana Rudová, Logické programování I, 20. května 2009 48 Vstup/výstup, databázové operace, rozklad termu Predikáty pro vstup a 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 Příklad: vstup/výstup Napište predikát uloz_do_souboru( Soubor ), který načte několik fakt ze vstupu a uloží je do souboru Soubor. I ?- uloz_do_souboru( 'soubor.pl' ). I: fakt(mi rek, 18). I: fakt(pavel,4). I : yes I ?- [soubor]. % consulting /home/hanka/soubor.pl... % consulted /home/hanka/soubor.pl in module user, O msec % 376 bytes yes I ?- listing(fakt/2). fakt(mirek, 18). fakt(pavel, 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 ) :-seeing( StaryVstup ), tellingC StaryVystup ), see( user ), tell( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_fi1 e, i ■ > seen, told, tell( StaryVystup ), see( StaryVstup ). process_term(end_of_file) :- !. process_term( Term ) :- write( Term ), writeC .') , nl. Hana Rudová, Logické programování I, 20. května 2009 51 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: assertC 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: nadměrné použití těchto operací snižuje srozumitelnost programu Hana Rudová, Logické programování I, 20. května 2009 52 Vstup/výstup, databázové operace, rozklad term Databázové operace: příklad Napište predikát vytvor_program/0, který načte několik klauzulí ze vstupu a uloží je do programové databáze. | ?- vytvor_program. |: fakt(pavel, 4). |: pravidlo(X,Y) :- fakt(X,Y). I : yes | ?- listing(fakt/2). fakt(pavel, 4). yes | ?- listing(pravidlo/2). pravidlo(A, B) :- fakt(A, B). yes | ?- clause( pravidlo(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 Databázové operace: implementace vytvo r_p rog ram :- seeing( StaryVstup ), see( user ), repeat, read( Term ), uloz_term( Term ), Term == end_of_fi1 e, i ■ > seen, see( StaryVstup ). uloz_term( end_of_file ) :- !. uloz_term( Term ) :- assert( Term ). Hana Rudová, Logické programování I, 20. května 2009 54 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 některé argumenty, pak je efektivnější: functor( Term, Funktor, Arita ) functor( a(9,e), a, 2 ) functor(atom,atom,0) ) functor(l,l,0) arg( 2, a(9,e), e) arg( N, Term, Argument ) Hana Rudová, Logické programování I, 20. května 2009 55 Vstup/výstup, databázové operace, rozklad termu Rekurzivní rozklad termu Term je proměnná (var/1), 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 , f unctor/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 ground(Term) :- atomic(Term), !. % Term je atom nebo číslo NEBO ground(Term) :- var(Term), !, fail. % Term není proměnná NEBO ground([H|T]) :- !, ground(H), ground(T). % Term je seznam a ani hlava ani těl ground(Term) % neobsahuji proměnné NEBO Term =.. [ _Funktor | Argumenty ], % je Term složený ground( Argumenty ). % a jeho argumenty % neobsahuji proměnné ?- ground(s(2,[a(l,3),b,c],X)). ?- ground(s(2,[a(l,3),b,c])). no Hana Rudová, Logické programování I, 20. května 2009 56 yes 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,[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\=[_|_], T=..[_|Argumenty], subterm(S,Argumenty). Hana Rudová, Logické programování I, 20. května 2009 57 Vstup/výstup, databázové operace, rozklad termu 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 u n ifi kováte Iné 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 I ?- 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=..[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 unify(A,B) Napište predikát unify(A, B), který unifikuje termy A a B. I ?- unify([Y,3,sin(a(3)),s(a,3)],[l,3,sin(X),s(a,3)]) X = a(3) Y = 1 yes um uni uni uni uni fy(A,B) fy(A,B) fy(A,B) fy(A,B) - var(A), var(B), !, A=B. - var(A), !, not_occurs(A,B), A=B. - var(B), !, not_occurs(B,A), B=A. - atomic(A), atomic(B), !, A==B. fy([HAITA],[HBITB]) :- !, unify(HA,HB), unify(TA,TB). unify(A,B) :- A=..[FA|ArgA], B=..[FB|ArgB], FA==FB, unify(ArgA,ArgB) Hana Rudová, Logické programování I, 20. května 2009 59 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 60 Vstup/výstup, databázové operace, rozklad termu Logické programování s omezujícími podmínkami Algebrogram ■ Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: ■ různá písmena mají přiřazena různé cifry ■ S a M nejsou 0 ■ Proměnné: S,E,N,D,M,O,R,Y ■ Domény: [1 ..9] pro S,M [0..9] pro E,N,D,0,R,Y ■ 1 omezení pro nerovnost: all_di sti nct([S, E,N, D,M,0, R, Y]) ■ 1 omezení pro rovnosti: SEND + MORE MONEY 1000*S + 100*E + 10*N + D SEND + 1000*M + 100*0 + 10*R + E + MORE #= 10000*M + 1000*0 + 100*N + 10*E + Y MONEY Hana Rudová, Logické programování I, 20. května 2009 62 Omezující podmínky Jazykové prvky Nalezněte řešení pro algebrogram D0NALD + GERALD = R0BERT ■ Struktura programu algebrogramC Cifry ) :-domai n(...), constrai nts(...), labeling(...)■ ■ Knihovna pro CLP(FD) :- use_module(library(clpfd)) . ■ Domény proměnných domain( Seznam, MinValue, MaxValue ) ■ Omezení all_distinct( Seznam ) ■ Aritmetické omezení A*B + c #= D ■ Procedura pro prohledávání stavového prostoru labeling([], [Xl, X2, X3]) Hana Rudová, Logické programování I, 20. května 2009 63 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*G + 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í I, 20. května 2009 64 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. Úkoly jsou zadány následujícím způsobem: % ukol(Id,Doba,Mi nStart,MaxKonec) ukol(1,4,8,70). ukol(2,2,7,60). ukol(3,1,2,25). ukol(4,6,5,55). ukol(5,4,1,45). ukol(6,2,4,35). ukol(7,8,2,25) . ukol(8,5,0,20). ukol(9,1,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) :- domény(Ukoly,Zacatky,Doby), se ri ali zed(Začátky,Doby), 1abeli ng([],Začátky). domeny(Ukoly,Zacatky,Doby) :- findall(ukol(Id,Doba,MinStart,MaxKonec), ukol(Id,Doba,Mi nStart,MaxKonec), Ukoly), nastav_domeny(Ukoly,Začátky,Doby). Hana Rudová, Logické programování I, 20. května 2009 65 Omezující podmínky Plánování: výstup tiskni(Úkoly,Začátky) :- připrav(Ukoly,Začátky,Vstup), quicksort(Vstup,Vystup), nl, tiskni(Vystup). priprav([], [] , []) . připrav([ukol(Id,Doba,MinStart,MaxKonec)|Úkoly], [Z|Zacatky], [ukol(Id,Doba,MinStart,MaxKonec,Z)IVstup]) :-připrav(Ukoly,Začátky,Vstup). ti skni([]) :- nl . tiskni([V|Vystup]) :- V=ukol(Id,Doba,Mi nStart,MaxKonec,Z), K is Z+Doba, formatC ~d: \t~d..~d \t(~d: ~d..~d)\n', [Id,Z,K,Doba,Mi nStart,MaxKonec] ), ti skni(Vystup). Hana Rudová, Logické programování I, 20. května 2009 66 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í I, 20. května 2009 67 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,Mi nStart,MaxKonec), MaxStart i s MaxKonec-Doba, Z in MinStart..MaxStart, nastav_domeny(Ukoly,Začátky,Doby). Hana Rudová, Logické programování I, 20. května 2009 68 Omezující podmínky Plánování a precedence 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(Zacatky,Doby) :- findall(prec(A,B),prec(A,B),P), omezeni_precedence(P,Začátky,Doby). omezeni_precedence([],_Zacatky,_Doby). omezeni_precedence([prec(A,B)|Přec],Zacatky,Doby) :- nth(A,Zacatky,ZA), nth(B,Zacatky,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é 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]). 1 ide(Začátky,Doby,Lide) :- findall(clovek(Kdo,IdUkoly),clovek(Kdo,IdUkoly), Lide), omezeni_li de(Li de,Začátky,Doby). omezeni_lide([],_Zacatky,_Doby). omezeni_lide([Clovek|Lide],Začátky,Doby) :- Clovek=clovek(_Id,IdUkoly), omezeni_clovek(IdUkoly,Začátky,Doby), omezeni_li de(Li de,Začátky,Doby). Hana Rudová, Logické programování I, 20. května 2009 70 Omezující podm Plánování a lidé (pokračování) omezeni_clovek(IdUkoly,Začátky,Doby) :- omezeni_clovek(Idllkoly,Zacatky,Doby, [],[]). % omezeni_clovek(IdUkoly,Začátky,Doby,ClovekZ,ClovekD) omezeni_clovek([],_Zacatky,_Doby,ClovekZ,ClovekD) :- serialized(ClovekZ,ClovekD). omezeni_clovek([U|IdUkoly],Zacatky,Doby,ClovekZ,ClovekD) :- nth(U,Zacatky,Z), nth(U,Doby,D), omezeni_clovek(IdUkoly,Zacatky,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 li de(Začátky,Doby,Lide) :- findall(clovek(Kdo,Kapacita,IdUkoly),clovek(Kdo,Kapacita,IdUkoly), Lide), omezeni_lide(Lide,Začátky,Doby). omezeni_lide([],_Zacatky,_Doby). omezeni_lide([clovek(_Id,Kapacita,IdUkoly)|Lide],Zacatky,Doby) :-omezeni _clovek(IdUkoly,Kapaci ta,Začátky,Doby), omezeni_lide(Lide,Zacatky,Doby). omezeni_clovek(IdUkoly,Kapacita,Začátky,Doby) :- omezeni_clovek(IdUkoly,Kapacita,Začátky,Doby,[],[]). omezeni_clovek([],Kapacita,_Zacatky,_Doby,ClovekZ,ClovekD) :- 1ength(ClovekZ,Délka), 1 istOfl(Delka,ListOf1), cumulati ve(ClovekZ,ClovekD,Li stOf1,Kapaci ta). omezeni_clovek([U|IdUkoly],Kapacita,Začátky,Doby,ClovekZ,ClovekD) :- nth(U,Zacatky,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 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(l), 2, tree(~leaf (3) ,4,leaf (5)) ), 6, tree(leaf (7) ,8, []) ) Hana Rudová, Logické programování I, 20. května 2009 74 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 ■ X je 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,Ll). Hana Rudová, Logické programování I, 20. května 2009 76 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 ?- traverse(tree(tree(leaf(1),2,tree(leaf(3),4,leaf(5))),6, tree(leaf(7),8,leaf(9))), [6,2,1,4,3,5,8,7,9]). (preorder) traverse(T,Pre):- t_pre(T,Pre,[]) t_pre([] ,S,S). t_pre(leaf(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] 14 7 9% S1=[4,3,5|S2] / \ Použit princip rozdílových seznamů Hana Rudová, Logické programování I, 20. května 2009 77 Stromy, grafy Procházení stromů traverse(T,Pře):- t_pre(T,Pře,[]). 6 / \ t_pre([],S,S). / \ t_pre(leaf(V),[V|S],S). / \ t_pre(tree(L,V,R),[V|S],S2):- 2 8 t_pre(L,S,Sl), / \ / t_pre(R,Sl,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_i n(1eaf(V),[V|S],S). t_in(tree(L,V,R),S,S2):- t_in(L,S,[V|Sl]), t_in(R,Sl,S2). Hana Rudová, Logické programování I, 20. května 2009 78 Stromy, grafy % V=2, S=[1,4,3,5|S2] % S=[1|S1] % S1=[4,3,5|S2] 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_post(leaf(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 Hana Rudová, Logické programování I, 20. května 2009 79 Stromy, grafy 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],[1,3],[1,2]). graf([2,4,6],[1,3],[2],[1,5],[4,6], [1,5]) . 1--2 5—4 \ I II \| 6--1--2--3 3 ?- functor(Graf,graf,PocetUzlu). ?- arg(Uzel,Graf,Sousedi). (Orientovaný) ohodnocený graf [Soused-Ohodnoceni|Sousedi] graf([2-1,3-2],[1-1,3-2],[1-2,2-2]). graf([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,G,P) pro procházení grafu G 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 \l 6--1--2--3 6--1--2--3 3 3 U=4: rodič(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) :- functor(G,graf,Počet), functor(P,rodice,Počet), arg(U,G,Sousedi), arg(U,P,empty), prochazej_sousedy(Sousedi,U,G,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,G,P) :- arg(V,P,Rodič), ( nonvar(Rodic) -> ; Rodič = U, arg(V,G,Sousedi V), prochazej_sousedy(SousediV,V,G,P) ), prochazej_sousedy(T,U,G,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,G,P) pro procházení grafu G do šířky z uzlu U. Výsledkem procházení je datová struktura P, která reprezentuje strom vzniklý při prohledávání grafu G do šířky (pro každý uzel stromu známe jeho rodiče). 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 I II I \| | 6--1--2--3 6--1--2--3 3 3 11=4: rodic(4, 1, 2, empty, 4, 1) U=2: rodič(2,empty,2) Hana Rudová, Logické programování I, 20. května 2009 84 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 Poděkováni