IBOl 3 Logické programování I Backtracking, unifikace, aritmetika (průsvitky ze cvičení) Hana Rudová jaro 2010 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, 19. května 2010 3 Backtracking, unifikace, aritmetika Hana Rudová, Logické programování I, 19. května 2010 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, 19. května 2010 Backtracking, unifikace, aritmetika Hana Rudová, Logické programování I, 19. května 2010 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, 19. května 2010 Backtracking, unifikace, aritmetika Hana Rudová, Logické programování I, 19. května 2010 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, 19. května 2010 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, 19. května 2010 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í 1,19. května 2010 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, 19. května 2010 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 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,19. května 2010 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í 1,19. května 2010 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, 19. května 2010 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, 19. května 2010 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, 1 9. května 2010 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(sCO)) X0 = s(sCO)) ; 2' dotaz z kroku 1. nejde unifikovat s hlavou klauzule B (1. argument) Hana Rudová, Logické programování I, 19. května 2010 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, 19. května 2010 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, 19. května 2010 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, 19. května 2010 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, 19. května 2010 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í 1,19. května 2010 23 Backtracking, unifikace, aritmetika Hana Rudová, Logické programování 1,19. května 2010 24 Backtracking, unifikace, aritmetika Reprezentace seznamu Seznamy, řez 1 Seznam: [a, b, c], prázdný seznam [] 1 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 " |" 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]]r[a,b| [c] ] 1 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í I, 19. května 2010 26 Seznamy a append appendC [], S, S ). appendC [X|S1], S2, [X|S3] ) :- appendC SI, S2, S3). Napište následující predikáty pomoci append/3: ■ prefixC SI, S2 ) :- appendC SI, _S3, S2). DÚ: suffix(Sl,S2) ■ last( 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,l], [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í I, 19. května 2010 27 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ám' v těle klauzule ) % žádné rekurzivní voláni v těle klauzule pC-..) :- !, pC ■■■ )■ % řez zajišťuje determinismus 1 Tento typ rekurze lze převést na iteraci Hana Rudová, Logické programování I, 19. května 2010 28 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'' 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 ) :- AO is A + 1, lengthC T, AO, Délka ). ■ Přídavný argument se nazývá akumulátor Hana Rudová, Logické programování I, 19. května 2010 29 Seznamy, řez Výpočet faktoriálu fact(N, F) s akumulátorem: factC N, F ) :- fact C 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, 19. května 2010 31 Seznamy, řez ?- sum_listC [2,3,4], Sum ). bez akumulátoru: sum_listC [] , 0 ) . sum_listC [H|T], Sum ) :- sum_listC T, SumT ), Sum is H + SumT. s akumulátorem: sum_listC S, Sum ) :- sum_listC S, 0, Sum ). sum_listC [], Sum, Sum ). sum_listC [H|T], A, Sum ) :- Al is A + H, sum_listC T, Al, Sum). Hana Rudová, Logické programování I, 19. května 2010 30 Seznamy, řez Prozkoumejte trasy výpočtu a navracení rCX) -write Crl). např. pomocí následujících dotazů (vždy si rCX) -pCX),writeCr2). rCX) -writeCr3). středníkem vyžádejte navracení): PCX) -writeCpl) • Cl) X=l,r(X). C2) X=3,rCX). C3) X=0,rCX). C4) X= -6,r(X). PCX) -a(X),b(X), ! , cCX),dCX),writeCp2) . ■ řez v predikátu p/1 neovlivní alternativy PCX) -writeCp3). predikátu r/1 aCX) -writeCal). ■ dokud nebyl proveden řez, alternativy aCX) -writeCa2). predikátu a/l se uplatňují, př. neúspěch bCX) - X > 0, writeCbl). b/1 v dotazu (3) bCX) - X < 0, writeCb2). ■ při neúspěchu cíle za řezem se výpočet cCX) - X mod 2 =:= 0, writeCcl) navrací až k volající proceduře r/1, viz (1) cCX) - X mod 3 =:= 0, writeCc2) ■ alternativy vzniklé po provedení řezu se dCX) - absCX) < 10, writeCdl). dCX) - writeCd2). zachovávají - další možnosti predikátu c/1 viz (2) a (4) Hana Rudová, Logické programování 1,19. května 2010 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 > O, write(bl). - X < O, write(b2). X mod 2 X mod 3 write(cl) . write(c2). abs(X) < 10, write(dl). write(d2). | ?- X=l,r(X). rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; no | ?- 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, 19. května 2010 Hana Rudová, Logické programování I, 19. května 2010 Ř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] ). meml(H,[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) Řez: delete deleteC X, [X|S], S ) . deleteC X, [Y|S], [Y|S1] ) :- 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). 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, 19. května 2010 35 Seznamy, řez Hana Rudová, Logické programování I, 19. května 2010 36 Seznamy, řez 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, 19. května 2010 Všechna řešení % 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(rošti slav,1ucensky,m,50,techni k,škoda). z(alena,veselá,z,25,sekretářka,škoda). zCjana,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). zCpetra,š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) . ?- 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(zO,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). Hana Rudová, Logické programování I, 19. května 2010 39 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í 1,19. května 2010 40 Všechna řešení, třídění, rozdílové seznamy swap(S,Sl) rekurzivně bubblesortem 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 bubblesortCS,Sorted) :- swap (S,S1), !, % 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, 19. května 2010 % swap prvnich dvou prvků % nebo obecněji X@>Y, resp. gt(X,Y) % swap prvků až ve zbytku 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 ■ seřaďte tělo T seznamu S ■ vložte hlavu X do seřazeného těla tak, že výsledný seznam je zase seřazený. Víme: výsledek po vložení Xje celý seřazený seznam. insertsortC[] , []) . insertsort([X|T].Sorted) :- i nsertsort(T,SortedT), insert(X.SortedT,Sorted). insertCX,[YlSorted],[YlSortedl]) X > Y, ! , insertCX,Sorted,Sortedl). insertCX,Sorted, [X|Sorted]). konec rekurze pro S=[] rekurzivně insertsortem insert(X,SortedT,Sorted) % seřazeni těla % vloženi X na vhodné mi sto Hana Rudová, Logické programování I, 19. května 2010 Všechna řešení, třídění, rozdílové seznamy qui cksort(S,Sorted) Neprázdný seznam S seřaďte tak, že ■ vyberte nějaký prvek X z S; rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky ■ seřaďte Small do SortedSmall ■ seřaďte Big do SortedBig ■ setříděný seznam vznikne spojením SortedSmall a [XISortedBig] quicksortC[] , []) . quicksortC[X|T], Sorted) konec rekurze pro S=[] např. vyberte hlavu S split(X,Seznam,Small,Big) rekurzivně quicksortem rekurzivně quicksortem append splitCX, Tail, Small, Big), quicksortCSmall , SortedSmall), quicksortCBig, SortedBig), appendCSortedSmall , [XISortedBig], Sorted). splitCX, [], [], []). splitCX, [Y|T], [Y|Small], Big) :-X>Y, !, splitCX, T, Small, Big). splitCX, [Y|T], Small, [Y|Big]) :- splitCX, T, Small, Big). Hana Rudová, Logické programování 1,19. května 2010 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 A1 Z1 A2 Z2 L1 L2 L3 ■ ?- append( [1,2,3|Z1]-Z1, [4,5|Z2]-Z2, Al-[]). ■ append( Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 appendC [1, 2 , 3 ,4, 5] - [4, 5] , [4,5]-[], [1, 2 , 3 , 4, 5] - [] ). Hana Rudová, Logické programování 1,19. května 2010 44 Všechna řešení, třídění, rozdílové seznamy reverse(Seznam, Opacny) DÚ: pal i ndrom(L) % 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, 19. května 2010 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 [XISortedBig] quicksortCS, Sorted) :- quicksortlCS,Sorted-[]). quicksortlC[] ,Z-Z) . quicksortlC[X|T], A1-Z2) :- splitCX, T, Small, Big), quicksortlCSmall, A1-[X|A2]), quicksortlCBig, A2-Z2). appendCA1-A2, A2-Z2, A1-Z2). Hana Rudová, Logické programování I, 19. května 2010 Všechna řešení, třídění, rozdílové seznamy 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 i ndrom(Seznam) :- reverse(Seznam,Seznam). Hana Rudová, Logické programování 1,19. května 2010 Všechna řešení, třídění, rozdílové seznamy Vstup/výstup, databázové operace, rozklad termu Čtení ze souboru Predikáty pro vstup a výstup process_file( Soubor ) :- seeingC 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, 19. května 2010 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. | ?- u"loz_do_souboru( 'soubor.pl ' ). fakt(mi rek, 18). faktCpavel,4). yes | ?- 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í I, 19. května 2010 Vstup/výstup, databázové operace, rozklad termu 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 ?- wn'te(a(l)), wn'te('.'), nl, write(a(2)), wn'te('.'), ni 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, 19. května 2010 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 ) :- write(Term), writeC'.'), nl . Hana Rudová, Logické programování I, 19. května 2010 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í I, 19. května 2010 Vstup/výstup, databázové operace, rozklad termu Databázové operace: implementace vytvo r_p rog ram :- seeingC StaryVstup ), see( user ), repeat, read C Term ), uloz_term( Term ) , Term == end_of_file, i seen, see( StaryVstup ). uloz_term( end_of_file ) uloz_term( Term ) :- assertC 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). yes | ?- 1 isting(fakt/2). fakt(pavel, 4). yes | ?- listing(pravidlo/2). pravidlo(A, B) :- fakt(A, B). yes | ?- clause( pravidlo(A, B) , C) . % clause/2 použitelný pouze pro dynamické klauzule C = fakt(A.B) ? yes Hana Rudová, Logické programování I, 19. května 2010 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 ) functorC a(9,e), a, 2 ) functor(atom,atom,0) functor(l,1,0) arg( N, Term, Argument ) argC 2, a(9,e), e) Hana Rudová, Logické programování I, 19. května 2010 55 Vstup/výstup, databázové operace, rozklad termu Hana Rudová, Logické programování I, 19. května 2010 56 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 ground(Term) :- atomic(Term), !. % Term je atom nebo číslo NEBO ground(Term) :- var(Term), !, fail. % Term není proměnná NEBO groundC[H|T]) :- !, ground(H), ground(T). % Term je seznam a ani hlava ani těl % neobsahují proměnné NEBO ground(Term) :- Term =.. [ _Funktor | Argumenty ], % je Term složený groundC Argumenty ). % a jeho argumenty % neobsahují proměnné ?- ground(s(2,[a(l,3),b,c],X)). ?- ground(s(2, [a(l,3),b,c])). no yes Hana Rudová, Logické programování I, 1 9. května 2010 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 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 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, 1 9. května 2010 59 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 ■ Tje složený term (compound/1), není seznam (T\=[_|_]) , a S je podtermem některého argumentu T. ■ pokud nepoužijeme 0~\=[_|_]), pak dotaz :- subterm(a, [1]) . cyklí! ■ pokud nepoužijeme (compound/1), pak dotaz :- subterm(l,2) . cyklí! | ?- subterm(sin(3),b(c,2,[l,b],sin(3),a)). yes subterm(T.T) :- !. subtermCS,[H|_]) :- subterm(S,H), !. subtermCS,[_|T]) :- subtermCS,T),!. subtermCS,T) :- compoundCT), T\=[_|_], T=..[_|Argumenty], subtermCS.Argumenty). Hana Rudová, Logické programování I, 19. května 2010 58 Vstup/výstup, databázové operace, rozklad termu D.Ú. um" f y (A, B) Napište predikát unify(A,B), který unifikuje termy A a B a provede zároveň kontrolu výskytu. | ?- unify([Y,3,sin(a(3)),s(a,3)],[l,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) Hana Rudová, Logické programování I, 19. května 2010 60 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). Logické programování s omezujícími podmínkami Hana Rudová, Logické programování I, 19. května 2010 Vstup/výstup, databázové operace, rozklad termu 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_distinct([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 Hana Rudová, Logické programování I, 19. května 2010 63 SEND + MORE MONEY Omezující podmínky Jazykové prvky Nalezněte řešení pro algebrogram D0NALD + GERALD = R0BERT ■ Struktura programu algebrogram( [D,0,N,A,L,D,C,E,R,B,T] ) :- domain(...), % domény proměnných a"l"l_di sti nct(. . .) , ... #= % omezeni labelingC...). % prohledáváni stavového prostoru Knihovna pro CLP(FD) Domény proměnných Omezení Aritmetické omezení :- use_module("library(clpfd)) . domainC Seznam, MinValue, MaxValue ) a"l"l_distinct( Seznam ) A*B + C #= D Procedura pro prohledávání stavového prostoru labe"ling([] .Seznam) Hana Rudová, Logické programování I, 19. května 2010 Omezující podmínky Algebrogram: řešení Disjunktivní rozvrhování (unární zdroj) :- use_module(library(clpfd)) . donald(LD) :- % domény LD=[D,0,N,A,L,C,E,R,B,T] , domain(LD,0,9), domain C[D,C,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 labeling([],LD). Hana Rudová, Logické programování I, 19. května 2010 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(5,4,l,45). ukol(9,l,8,40). ukol(13,3,30,60). Kostra řešení: ukoly(Zacatky) :- ukol(2,2,7,60). ukol(6,2,4,35). ukol(10,7,4,50). ukol(14,5,15,70). ukol(3,l,2,25) . ukol(7,8,2,25) . ukol(ll,5,2,50). ukol(15,4,10,40). ukol(4,6,5,55). ukol(8,5,0,20). ukol(12,2,0,35). domeny(Ukoly,Začátky.Tasks), cumulative(Tasks), labeling([],Začátky). domény(Úkoly,Začátky.Tasks) :- findal1(ukol(Id,Doba.MinStart.MaxKonec), ukol(Id,Doba.MinStart,MaxKonec), Úkoly), nastav_domeny(Úkoly,Začátky.Tasks). Hana Rudová, Logické programování I, 19. května 2010 67 Omezující podmínky 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í I, 19. května 2010 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([], [] , []) . priprav([ukol(Id,Doba,MinStart.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 is 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, 19. května 2010 Omezující podmínky Plánování: výstup II Plánování a domény quicksort(S, Sorted) :- quicksortl(S,Sorted-[]). quicksortl([],Z-Z). quicksortl([X|Tail] , A1-Z2) :- split(X, Tail, Small, Big), quicksortlCSmall, A1-[X|A2]), quicksortl(Big, A2-Z2). split(_X, [], [], []). splitCX, [Y|T], [Y|Small], Big) :- greater(X.Y), !, split(X, T, Small, Big). splitCX, [Y|T], Small, [Y|Big]) :- split(X, T, Small, Big). greater(ukol(_,_,_,_,Zl),ukol(_,_,_,_,Z2)) :- Z1>Z2. Hana Rudová, Logické programování I, 19. května 2010 69 Omezující podmínky D.Ú. Plánování a precedence: precedence(Tasks) 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)), nthlCB,Tasks,task(ZB,_DB,_KB,1,B)), ZA + DA #=< ZB, omezeni_precedence(Prec,Tasks). Hana Rudová, Logické programování I, 19. května 2010 71 Omezující podmínky Napište predikát nastav_domeny/3, který na základě datové struktury [úkol (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 tas k(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í I, 19. května 2010 70 Omezující podmínky Kumulativní rozvrhování ■ cumulative([task(Start,Duration,End,Demand,TaskId) | Tasks], [li mi t (Limit)]) ■ 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)],[limit(3)]) 2 3 1 1 1 1 1 1 2 3 4 5 6 Hana Rudová, Logické programování 1,19. května 2010 72 Omezující podmínky Plánování a lidé Plánování a lidé (pokračování) 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]) ]ide(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í I, 19. května 2010 73 Omezující podmínky Stromy, grafy 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)). omezeni_clovek(UkolyCloveka,Kapacita,Tasks) :- omezeni_clovek(UkolyCloveka,Kapacita,Tasks,[]). omezeni_clovek([].Kapacita,_Tasks.TasksC) :- cumulativeCTasksC,[limit(Kapacita)]). omezeni_clovek([U|UkolyCloveka],Kapacita,Tasks,TasksC) :- nthlCU,Tasks,TU), omezeni_clovek(UkolyCloveka,Kapacita,Tasks,[TU|TasksC]). Hana Rudová, Logické programování I, 19. května 2010 74 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, 19. května 2010 76 Stromy, grafy Stromy: hledáni prvku in(X,T) Stromy: přidávání add(T,X,TWithX) 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(_,V,R) a XV, !. addOeaf(V), X, treeQeaf (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í 1,19. května 2010 Stromy, grafy Procházení stromů Napište predikát traverse(Tree, List), který projde traversálně strom Tree. Seznam List pak obsahuje všechny prvky tohoto stromu. Pořadí preorder: nejprve uzel, pak levý podstrom, nakonec pravý podstrom Procházení stromů ?- traverse(tree(treeOeaf (1) , 2 , treeQeaf (3) ,4,leaf(5))) ,6, treeQeaf (7) ,8, leaf (9))) , [6,2,1,4, 3 , 5 ,8,7,9]) . (preorder) t raverse(T,Pre):- t_pre(T,Pre,[]). 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, 19. května 2010 6 / \ / \ / \ 2 8 % V=2, S=[1,4,3,5|S2] /\ /\ % S=[1|SI] 1 4 7 9 % S1=[4,3,5|S2] / \ 3 5 Stromy, grafy t rave rse(T,Pre):- t_pre(T,Pre,[]). 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 / \ / \ / \ % 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, 19. května 2010 80 Stromy, grafy DÚ: Procházení stromu postorder Reprezentace grafu 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, 19. května 2010 Stromy, grafy 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]). graf([2,4,6],[1,3],[2],[1,5],[4,6],[1,5]). 1--2 \ I 5 — 4 I I 6--1--2--3 ?- functor(Graf,graf,PocetUzlu). ?- arg(Uze],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, 19. května 2010 82 Stromy, grafy Procházení grafu do hloubky Napište predikát dfs(Uzel,Craf,Parents) pro procházení grafu Graf do hloubky z uzlu Uzel. Výsledkem je datová struktura Parents, 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],[l,3],[l,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, 19. května 2010 83 Stromy, grafy Procházení grafu do hloubky: algoritmus I Procházení grafu z uzlu Uzel ■ Vytvoříme term pro rodiče (všichni rodiči jsou zatím volné proměnné) ■ Uzel Uzel má prázdného rodiče a má sousedy Sousedi ■ Procházíme (rekurzivně) všechny sousedy v Sousedi dfs(Uze],Graf,Parents) :- functor(Graf,graf,Počet), f unctor(Parents,rodiče,Počet), argCUzel,Parents,empty), argCUzel,Graf.Sousedi), prochazej_sousedy(Sousedi.Uzel,Graf,Parents) . Hana Rudová, Logické programování I, 19. května 2010 84 Stromy, grafy Procházení grafu do hloubky: algoritmus II Procházení sousedů uzlu Uzel (pokud Uzel nemá sousedy, tj. Sousedi=[], končíme) 1. Uzel V je první soused 2. Zjistíme rodiče uzlu V ... pomocí arg(V,Parents,Rodič) 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 Uzel (b) rekurzivně procházej všechny sousedy uzlu V 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,Craf.SousediV), prochazej_sousedy(SousediV,V,Graf,Parents) ), prochazej_sousedy(T,Uzel,Graf,Parents). Hana Rudová, Logické programování I, 19. května 2010 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 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],[1,3],[1,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: rodic(2,empty,2) 5— 4 I 6- -1--2--3 U=4: rodic(4, 1, 2, empty, 4, 1) Hana Rudová, Logické programování I, 19. května 2010 Stromy, grafy Hana Rudová, Logické programování I, 19. května 2010