IB013 Logické programovanie: zbierka príkladov Hana Rudová Fakulta informatiky, Masarykova univerzita 11. marca 2013 Obsah I Zadania úloh 3 1 Unifikácia 3 2 Backtracking, rez 3 3 Aritmetika 4 4 Zoznamy 5 5 Vstup a výstup 6 6 Dekompozícia termu 6 7 Všetky riešenia 7 8 Rezolúcia ^ 9 Negácia v logickom programovaní 9 10 Logické programovanie s obmedzujúcimi podmienkami 9 11 DC gramatiky H 12 Rôzne 12 II Riešenia úloh 12 1 Unifikácia 12 2 Backtracking, rez 13 3 Aritmetika 13 4 Zoznamy 14 5 Vstup a výstup I5 6 Dekompozícia termu 15 7 Všetky riešenia 16 IB013 Logické programovanie: zbierka príkladov_11. marca 2013 8 Rezolúcia 16 9 Negácia v logickom programovaní 19 10 Logické programovanie s obmedzujúcimi podmienkami 20 11 D C gramatiky 23 12 Rôzne 24 Podekovanie Materiály v zbierke boli prvotne pripravené Markom Klučárom. Hana Rudová, Fakulta informatiky Masarykova univerzita 2 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 Časť I Zadania úloh 1 Unifikácia 1. Pre každú z nasledujúcich unifikácií rozhodnite, či uspeje. Ak áno, zapíšte výslednú substitúciu (a) pondelok = pondelok (b) 'Pondelok' = pondelok (c) 'pondelok' = pondelok (d) Pondelok = pondelok (e) pondelok = utorok (f) den(pondelok) = pondelok (g) den(pondelok) = X (h) den(X) = den(pondelok) (i) den(pondelok,X) = den(Y,utorok) (j) den(pondelok,X,streda) = den(Y,utorok,X) (k) den(pondelok,X,streda) = den(Y,štvrtok) (1) den(D) = D (m) vikend(den(sobota),den(nedela)) = vikend(X,Y) (n) vikend(den(sobota),X) = vikend(X,den(nedela)) 2 Backtracking, rez Fibonacciho postupnosť je postupnosť čísel, ktorej prvé dva členy sú rovné 1 a každý ďalší člen je súčtom dvoch predchádzajúcich (fíb(í) — 1, fib(2) — 1, fib(n) — fib(n — 1) + fib(n — 2), n > 2). 1. Nižšie uvedený logický program obsahuje predikát f ib/2, ktorý vypočíta n-tý člen Fibonacciho postupnosti. Program však nie je úplne korektný. Správnu hodnotu síce vypočíta, no ak si po jej nájdení vyžiadame pomocou ; ďalšie riešenia, program sa zacyklí (správne by mal skončiť s odpoveďou no). Pridajte do programu na správne miesta operátory rezu tak, aby program v takýchto prípadoch necyklil. fib(N,l) :- N =< 2. fib(N,X) :- Nl is N-2, fib(Nl,1,1,X). fib(0,_A,X,X). fib(N,A,B,X) :- Nl is N-l, C is A+B, fib(Nl,B,C,X). 2. Zamyslite sa a zdôvodnite, prečo nasledujúci logický program, ktorý počíta n-tý člen Fibonacciho postupnosti priamo podľa definície, nie je vhodný (napriek tomu, že výsledok vypočíta vždy korektne) fib(l,l). fib(2,l). fib(N,X) :- N>2, Nl is N-l, N2 is N-2, fib(Nl,Y),fib(N2,Z),X is Y+Z. Hana Rudová, Fakulta informatiky, Masarykova univerzita 3 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 3. Napíšte predikát convert/2, ktorý prevedie svoj prvý argument (prirodzené číslo) na reprezentáciu daného čísla pomocou následníkov. Napr.: ?-convert(3,X). X = s(s(s(0))) 4. Napíšte predikát geq/2, ktorý ako argumenty dostane 2 čísla zadané pomocou následníkov a uspeje, ak prvé číslo je väčšie alebo rovné druhému. Napr.: ?-geq(s(0),s(s(0))). no 5. Napíšte predikát sucet/3, ktorý vypočíta súčet dvoch čísel zadaných pomocou následníkov. Napr.: ?- sucet(s(0),s(s(0)),X). X = s(s(s(0))) 6. Napíšte predikát sucin/3, ktorý vypočíta súčin dvoch čísel zadaných pomocou následníkov. Napr.: ?- sucin(s(s(0)),s(s(0)),X) . X = s(s(s(s(0)))) 7. Zadaná je databáza faktov v tvare priamacesta(a,b), ktoré hovoria o tom, že existuje priama (jednosmerná) cesta z miesta a do miesta b. Napíšte predikát cesta/2 tak, že cesta(a,b). uspeje, ak existuje nejaká cesta (ktorá môže prechádzať cez ľubovolný počet miest) z miesta a do miesta b. Môžete predpokladať, že cesty netvoria cykly (tzn. ak raz odídete z nejakého miesta, už sa tam nedá vrátiť) Rozšírenie 1: Upravte vaše riešenie tak, že cesta(a,b,S). uspeje, ak existuje nejaká cesta a S je zoznam miest, cez ktoré táto cesta prechádza (ideálne v poradí, v akom ich prechádzame) Rozšírenie 2: Upravte vaše riešenie tak, aby fungovalo aj v prípade, že cesty tvoria cykly. 3 Aritmetika 1. Rozhodnite, ktoré z nasledujúcich dotazov uspejú a ktoré nie: 15 is 3*5. 14 =\= 3*5. 15 = 3*5. 15 == 3*5. 15 =\= 3*5. 15 =:= 3*5. 3*5 == 3*5. 3*5 == 5*3. 3*5 =;= 3*5. 10-3 =\= 9-2. 2. Napíšte predikát mocnina/l, ktorý uspeje ak číslo zadané ako argument je mocninou dvojky (využite fakt, že mocniny dvojky je možné opakovane bez zvyšku deliť dvomi až kým nedostaneme jednotku) 3. Napíšte predikát sucet/2, ktorý spočíta súčet prvých N prirodzených čísel. Napr.: ?- sucet(5,X). X = 15 Hana Rudová, Fakulta informatiky, Masarykova univerzita 4 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 4. Napíšte predikát nsd/3, ktorý vypočíta najväčšieho spoločného delitel'a dvoch čísel. Napr.: ?- nsd(21,49,X). X = 7 Využite Euklidov algoritmus, ktorý je založený na pozorovaní, že najväčší spoločný deliteľ čísel a, b kde a > b je rovnaký ako najväčší spoločný deliteľ čísel (a — b), b 5. Napíšte predikát cif sucet/2, ktorý spočíta ciferný súčet zadaného čísla. Napr.: ?- cifsucet(12345,X). X = 15 4 Zoznamy 1. Ktoré z nasledujúcich zápisov predstavujú korektný zápis zoznamu? Aký počet prvkov majú v týchto prípadoch príslušné zoznamy? [II[2,3,4]] [1,2,31 []] [112,3,4] [II [21 [31 [4]]]] [1,2,3,41 []] [[] I []] [[1,2] 14] [[1,2],[3,4]I[5,6,7]] 2. Napíšte predikát dvojnasobok/2, ktorý uspeje ak prvky v druhom zozname sú dvojnásobkami prvkov prvého zoznamu. napr. dvojnasobok( [5,3,2] , [10,6,4] ) uspeje, ale dvojnasobok( [1,2,3] , [2,4,5] ) neuspeje 3. Napíšte predikát f ilter/2, ktorý zo zoznamu odstráni všetky nečíselné hodnoty, napr.: ?- filter([5,s(0),3,a,2,A,7] ,X). X = [5,3,2,7] 4. Napíšte predikát cifry/2, ktorý zo zoznamu cifier vybuduje číslo, napr.: ?- cifry([2,8,0,7],X). X = 2807 5. Napíšte predikát nty/3, ktorý vráti n-tý prvok zoznamu, napr.: ?- nty(4,[5,2,7,8,0],N). N = 8 6. Napšte predikát rovnaju_sa/2, ktorý uspeje, ak sa dva zadané zoznamy rovnajú. V prípade, že sa zoznamy nerovnajú, vypíšte dôvod, prečo je to tak (jeden zoznam je kratší ako druhý, výpis prvých 2 prvkov, ktoré sa nerovnajú...) Môžete predpokladať, že zoznamy neobsahujú premenné. Napríklad: ?- rovnaju_sa([5,3,7],[5,3,7]). yes ?- rovnaju_sa([5,3,7],[5,3,7,2]). 1. zoznam je kratsi no ?- rovnaju_sa([5,3,7],[5,2,3,7]). 3 sa nerovná 2 no Hana Rudová, Fakulta informatiky, Masarykova univerzita 5 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 7. Napíšte predikát priemer/2, ktorý vypočíta aritmetický priemer zadaného zoznamu. Napr.: ?- priemer([1,2,3,4,5,6],X). X = 3.5 8. Napíšte predikát zip/3, ktorý z dvoch zoznamov vytvorí nový spojením príslušných prvkov do dvojíc. Napr.: zip([l,2,3],[4,5,6],S). S = [1-4,2-5,3-6] 9. Napíšte predikát insert/3, ktorý do usporiadaného zoznamu čísel vloží ďalšie číslo tak, aby aj výsledný zoznam bol usporiadaný. Napr.: ?- insert(7,[1,2,3,10,12],X). X = [1,2,3,7,10,12] 10. Napíšte predikát merge/3, ktorý spojí 2 vzostupne usporiadané zoznamy čísel tak, aby výsledný zoznam bol opäť vzostupne usporiadaný. 5 Vstup a výstup 1. Napíšte predikát wordcount/2, ktorý ako prvý parameter dostane názov textového súboru obsahujúci slová vo formáte slovo. a ako svoj druhý argument vráti zoznam slov a počet ich výskytov v texte. Každé slovo sa má vo výslednom zozname nachádzať práve raz. Výsledný zoznam teda môže vyzerať napríklad takto: [a-10,ahoj-4, . . .]. 2. Napíšte predikát lettercount/2, ktorý ako prvý parameter dostane názov textového súboru a ako svoj druhý argument vráti zoznam obsahujúci počet výskytov jednotlivých písmen abecedy (pre jednoduchosť predpokladajme, že súbor obsahuje len malé písmená). Ostatné znaky by mali byť ignorované, (formát výstupného zoznamu si zvoľte podľa vlastného uváženia) 6 Dekompozícia termu 1. Napíšte predikát map/3 tak, že zavolanie map (Funkcia, Z1,Z2) aplikuje funkciu Funkcia postupne na všetky prvky zoznamu Zl a výsledky vloží do zoznamu Z2. Ak napríklad máme dvoj násobok (X, Y) :- Y is 2*X. potom po zavolaní map (dvojnásobok, [5,3,2] , S) . dostaneme S = [10,6,4]. Pri definícii využite konštrukciu pomocou = . . a predikát call/1. 2. Napíšte predikát nahrad/4 tak, že náhrad (TI, T2,T3,T4) (kde T1,T2,T3,T4 sú termy bez premenných) uspeje práve ak T4 vznikol z TI nahradením každého výskytu T2 termom T3. Napríklad: ?- nahrad(a(a(a)),a,b,X). X = a(a(b)) ?- náhrad( [sin(pi/4),sqrt(sin(pi/2)*2+4),2*sin(pi/2)],sin(pi/2),1,X). X = [sin(pi/4),sqrt(1*2+4),2*1] 3. Napíšte predikát position(Subterm,Term,Position) kde Position je zoznam identifikujúci prvú pozíciu termu Subterm v terme Term. Napríklad: ?- position(5,2*f(5),X). X = [2,1] pretože f (5) je druhý argument pre operátor * a 5 je prvý argument f 4. Napíšte predikát copy/2, tak, že copy (TI,T2) uspeje ak term T2 je kópiou termu TI. Tzn. termy majú rovnakú štruktúru, ale používajú rôzne premenné (f (X,g(X)) je kópiou Hana Rudová, Fakulta informatiky, Masarykova univerzita 6 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 f (Y, g (Y)) ale nieje kópiou f (X, g (X)) ani f (U, g (V))). Snažte sa, aby sa chovanie predikátu copy čo najviac podobalo na chovanie zabudovaného predikátu copy_term/2. Nápověda: použite pomocný zoznam na zapamätanie si premenných v pôvodnom terme a v kópii. 7 Všetky riešenia 1. Uvažujme nasledujúcu databázu faktov: f(a,b). f(a,c). f (a, d) . f(e,c) . f(g,h), f(g,b), f(i,a). Zistite bez použitia Prologu aká bude odpoveď na dotaz: (a) findall(X,f(a,X),List). (b) findall(X,f(X,b),List). (c) findall(X,f(X,Y),List). (d) bagof(X,f(X,Y),List). (e) setof(X,Y~f(X,Y),List). 2. Napíšte predikát subsets/2, ktorý pre danú množinu vygeneruje množinu všetkých jej podmnožin (množinou rozumieme zoznam, v ktorom sa prvky neopakujú). Na poradí podmnožin nezáleží. Môžete si skúsiť napísať aj predikát isset/1 ktorý uspeje ak zadaný zoznam korektne reprezentuje množinu, tzn. neobsahuje duplicitné prvky. 3. Napíšte predikát permutations/2, ktorý pre daný zoznam vygeneruje zoznam všetkých jeho permutácií v lexikografickom poradí. Napr.: :- permutations([1,2,3] ,S) . S = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2] , [3,2,1]] Môžete použiť zabudovaný predikát permutation/2 z library(lists) 4. Napíšte predikát variations(+S, +K,-Z) tak, že Z bude obsahovať všetky K-prvkové variácie zoznamu S. 8 Rezolúcia 1. Nájdite (ak existuje) najobecnejší uniŕikátor a nasledujúcich literálov: (a) p(X) ap(/(y)) (b) p(X,f(X)) ap(f(X),Y) (c) p(X,Y) ap(Z,Z) (d) p(X,8) &p(Y,Y) (e) p(f(X)) ap(Z,Y) (f) p(f(Z),g(X))ap(Y,g(Y)) (g) p(X,g(Z),X) ap(f(Y),Y,W) Hana Rudová, Fakulta informatiky, Masarykova univerzita 7 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 2. Na literáloch C\, C2 vykonajte rezolúciu a nájdite rezolventu, jednotlivé kroky (premenovanie premenných, nájdenie naj obecnejšieho uniŕikátora, rezolučný princíp) rozpíšte: (a) d = {q(X),MY),p(f(Z),f(Z))} a C2 = {n(Y),^r(W),^p(f(W), f(W))} (b) Ci = {q(X),^r(Y),p(X,Y)} a C2 = {n(y), -^r(W), -y(f(W), f(W))} 3. Pomocou lineárnej rezolúcie vyvraťte S = {{^t(X)}, {s(í)}, {c(l), c(2), ^(1)}, {í(0), -c(l)}, {í(l), -c(l)}, {í(0),^c(2)}, {í(2),^c(2)}} 4. Prepíšte nasledujúci program v prologovskej notácii ako množinu klauzulí. Následne na cieli ?- a. demonštrujte lineárnu rezolúciu. a :- b,c,d. b :- f. c. d. f. 5. Pomocou rezolučného princípu vyvraťte S — {{a, b}, {c, ^b}, {^c}, {^a, d}, {^e}, {e, ^d}}. Existuje viacero možných riešení, skúste nájsť čo najviac z nich. 6. Uvážme nasledujúci Prologovský program a dotaz ?- a. Nakreslite zodpovedajúci SLD strom. a :- b,c. a :- d. b. b :- d. c. d :- e. d. 7. Uvážme nasledujúci Prologovský program a dotaz ?- p (X, X). Nakreslite zodpovedajúci SLD strom. p(X,Y) :- q(X,Z), r(Z,Y). p(X,X) :- s(X). q(X,b). q(b,a). q(X,a) :- r(a,X). r (b,a) . s(X) :- t(X,a). s(X) :- t(X,b). s(X) :- t(X,X). t(a,b). t(b,a). 8. Do programu z predchádzajúcej úlohy pridajte 1 operátor rezu, tak aby výsledný program uspel práve dvakrát (pomôžte si nakresleným stromom z predchádzajúcej úlohy). Hana Rudová, Fakulta informatiky, Masarykova univerzita 8 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 9 Negácia v logickom programovaní 1. Rozhodnite, či nasledujúce programy sú stratiŕikované. Ak áno, nájdite nejakú ich stratifikáciu: (a) p(X):-q(X), \+ r(X). p(X):-q(X), \+ t(X). r(X):-s(X), \+ t(X), t (a). s (a), s (b). q(a). (b) p :- q, \+ r r :- s, \+ p q- s. (c) p :- \+ q, \+ r q :- \+ s r :- \+ t s. t. 2. Uvážme logický program: f(X) :- \+ g(X). g(X) :- \+ f(X). g(5). Pre ciele :- f(5) a :- -> f(5) rozhodnite, či existuje ich odvodenie (a) podľa closed world assumption (b) podľa negation as failure 3. Uvažujme nasledujúci logický program: a(X) :- c(X), Y is X+l, \+ d(Y). a(X) :- c(X), \+ d(X). b(X) :- X > 0. c(X) :- d(X), Y is X+l, \+ c(Y). d(l). d(2). a dotaz : - a(P). Napíšte množinu SLDNF odvodení pre tento dotaz a uveďte o aký typ odvodenia sa jedná. 10 Logické programovanie s obmedzujúcimi podmienkami 1. Napíšte predikát labeling/1 ktorý ako aktuálnu premennú vyberá premennú s najmenšou veľkosťou domény a hodnoty priraďuje vzostupne (pomocou indomain) 2. Zistite aké budú domény A,B,C po AC-3 pre domain([A,B,C] ,1,10), A#=2*B+1, C# n (pomôcka: vyskúšajte najprv jazyk slov v tvare anbn) 4. Napíšte DCG pre jazyk slov v tvare anb2n. 5. Napíšte DCG pre jazyk slov v tvare a™6™+1c™+2. 6. Preveďte nasledujúcu gramatiku na predikáty s rozdielovými klauzulami: s —> np, vp. np —> det, n. vp —> tv, np. vp —> v. det — > [the] . det — > [a] . det —> [every]. n —> [man] . n —> [woman]. n —> [park] . tv —> [loves]. tv —> [likes]. v —> [walks]. 7. Nakreslite derivačný strom pre nejakú vetu rozpoznávanú gramatikou z predchádzajúcej úlohy. 8. Napíšte, aké termy zodpovedajú nasledujúcim derivačným stromom: Hana Rudová, Fakulta informatiky, Masarykova univerzita 11 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 Exp S Sub Yesterday NP VP Add Num I A A John V NP Exp Exp 4 saw Det NP Num Mul a Adj NP 5 Exp Exp good N Num Num movie 7 2 9. Pre prvý strom z predchádzajúcej úlohy zostrojte zodpovedajúcu gramatiku s vytváraním derivačného stromu (tzn. tak aby derivačný strom vety "Yesterday John saw a good movie" zodpovedal znázornenému - overte si to v Prologu). Nevadí, ak vaša gramatika bude generovať aj iné, nezmyselné vety. 12 Rôzne 1. Zistite čo robí nasledujúci zámerne škaredo napísaný predikát a prepíšte ho tak, aby bol zrozumiteľnejší (pri zachovaní logickej ekvivalencie s pôvodnou definíciou). Pri zisťovaní, čo program robí, využite trasovanie v Prologu (predikát trace/0). foo(X) :- (\+ (X = 1)),(X=2;X=3;foo(X,X)). foo(X,Y) :- (Y=X -> (Z is X-l,foo(X,Z)); (Y=l ; (P is (X // Y) * Y, \+(P=X), Z is Y-l, foo(X,Z)))). Časť II Riešenia úloh 1 Unifikácia 1. výsledky si ľahko overíte v prologu Hana Rudová, Fakulta informatiky, Masarykova univerzita 12 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 2 Backtracking, rez 1. fib(N,l) :- N =< 2, ! . fib(N,X) :- Nl is N-2, fib(Nl,1,1,X). fib(0,_A,X,X) :- !. fib(N,A,B,X) :- Nl is N-l, C is A+B, fib(Nl,B,C,X). 2. Program je veľmi neefektívny (až exponenciálna zložitosť), pretože hodnoty predchádzajúcich členov postupnosti sa počítajú opakovane. Najlepšie to uvidíte, ak si nakreslíte strom výpočtu pre nejaké malé N, napr. 6. Takto zapísaný program navyše neumožňuje optimalizáciu posledného volania. 3. convert(0,0). convert(X,s(Y)) :- XI is X-l, convert(XI,Y). 4. geq(_,0). geq(s(X),s(Y)) :- geq(X,Y). 5. sucet(0,X,X). sucet(s(X),Y,s(Z)):-sucet(X,Y,Z). 6. sucin(_X,0,0). sucin(X,s(Y),Z) :- sucin(X,Y,Zl), sucet(X,Zl,Z). 7. Riešenie, ktoré zahŕňa obe rozšírenia: (1) :- dynamic navstivene/1. (2) cesta(A,A,[A]). (3) cesta(A,B,[A|S]) :- (4) assert(navstivene(A)), (5) priamacesta(A,X), (6) \+ navstivene(X), (7) cesta(X,B,S). (8) cesta(A,_B,_S) :- retract(navstivene(A)), fail. Pre riešenie bez druhého rozšírenia stačí vynechať riadky 1,4,6,8. Alernatívne by sme mohli druhé rozšírenie riešiť pridaním ďalšieho argumentu - zoznamu už navštívených vrcholov. Ak by sme nechceli riešiť ani prvé rozšírenie, môžeme z predikátov odstrániť tretí argument. Stojí za zmienku, že úloha bez rozšírení je v podstate ekvivalentá úlohe z cvičení s faktami v tvare rodic(x,y). a s predikátom potomek/2. 3 Aritmetika 1. Výsledky si ľahko overíte v prologu. 2. mocnina(l). mocnina(X) :- X mod 2 =:= 0, XI is X // 2, mocnina(Xl). 3. Funkčné riešenie: sucet(N,S) :- sucet(N,0,S). sucet(0,S,S) :- ! . sucet(N,X,S) :- Nl is N-l, XI is X+N, sucet(Nl,Xl,S). Hana Rudová, Fakulta informatiky, Masarykova univerzita 13 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 Lepšie riešenie (využíva vzorec pre súčet aritmetickej postupnosti): sucet(N,S) :- S is (N*(N+D) // 2. 4. nsd(X,X,X). nsd(A,B,X) :- A>B, Al is A-B, nsd(Al,B,X). nsd(A,B,X) :- B>A, BI is B-A, nsd(A,Bl,X). Dodajme, že existuje efektívnejšia verzia využívajúca zvyšky po delení. 5. cifsucet(N,CS) :- cifsucet(N,0,CS). cifsucet(0,CS,CS) :- !. cifsucet(N,X,CS) :- XI is X + N mod 10, Nl is N //10, cifsucet(Nl,Xl,CS). 4 Zoznamy 1. Výsledky si ľahko overíte v Prologu, na zistenie počtu prvkov zoznamu môžete použiť length/2 2. dvoj násobok ([],[]) . dvojnasobok([Xl|Tl],[X2IT2]) :- X2 is 2*X1, dvojnasobok(Tl,T2). 3. filter([],[]). filter([X|Tl],[X|T2]) :- number(X), !, filter(Tl,T2). filter([_X|Tl],T2) :- filter(Tl,T2). 4. cifry(S,X) :- cifry(S,0,X). cifry([] ,X,X) . cifry( [AIT],P,X) :- PI is 10*P + A, cifry(T,Pl,X). 5. nty(N,[X|_T],Y) :- N =< 1, !, X = Y. nty(N,[_X|T],Nty) :- Nl is N-l, nty(Nl,T,Nty). 6. rovnaju_sa( [],[]). rovnaju_sa([XlTl] ,[X|T2]) :- !, rovnaju_sa(Tl,T2). rovnaju_sa([],_S) :- write('l. zoznam je kratsi'), !, fail. rovnaju_sa(_S,[]) :- write('2. zoznam je kratsi'), !, fail. rovnaju_sa([X|_T1],[Y|_T2]) :- write(X), write(' sa nerovná '), write(Y), !, fail. Pre úplnosť dodajme, že ak by sme nepožadovali výpis dôvodu nerovnosti, vystačili by sme si s faktom rovnaju_sa(S,S). (ak S neobsahuje premenné) 7. priemer(S,X) :- priemer(S,0,0,X). priemer([],Sum,Count,X) :- X is Sum/Count. priemer([H|T],Sum,Count,X) :- Suml is Sum+H, Countl is Count+1, priemer(T,Suml,Countl,X). 8. zip([Hl|Tl],[H2IT2],[H1-H2IT]) :- zip(Tl,T2,T), !. zip(_,_,[]). 7«aspon 1 zoznam je prázdny 9. insert (X, [] , [X] ) . insert (X, [H I T] , [X, HI T] ) :-X= (Y is X+l, retract(slovo(C,X))); Y is 1), assert(slovo(C,Y)), C == end_of_file, retract(slovo(end_of_file, 1)) , i seen, see(Current), findall(Z-Count,slovo(Z,Count),S). 2. :- dynamic znak/2. lettercount(File,S) :- retractall(znak(_,_)), seeing(Current), see(File), repeat, get_char(C), (znak(C,X) -> (Y is X+l, retract(znak(C,X))); Y is 1), (member(C,[a,b,c,d,e,f,g,h,i,j,k,1,m,n,o,p,q,r,s,t,u,v,w,x,y,z]) -> assert(znak(C,Y)); true), C == end_of_file, i seen, see(Current), setof(Z-Count,znak(Z,Count), S). 6 Dekompozícia termu 1. map(_Funkcia, [] , [] ) . map(Funkcia, [Hli TI], [H2|T2]) :- F =.. [Funkcia, Hl, H2] , call(F), map(Funkcia, TI, T2). 2. nahrad(X,_,_,X) :-var(X),!. náhrad(Co,Co,Cim,Cim) :- !. nahrad(S,_,_,S) :- atomic(S), !. nahrad([X|T],Co,Cim,[XllTl]) :- nahrad(X,Co,Cim,Xl),nahrad(T,Co,Cim,Tl),!. nahrad(X,Co,Cim,Xl) :- compound(X), X =.. [HIT], nahrad(T,Co,Cim,Tl), XI =.. [H|T1]. 3. position(S,S,[]) :- !. position(S,[H|_],[11 T]) :- position(S,H,T),!. position(S, [_I T],[XIIT1]) :- position(S,T,[X2|T1]),X1 is X2+1, !. position(S,T,L) :- compound(T), T =..[_H|A], position(S,A,L). Hana Rudová, Fakulta informatiky, Masarykova univerzita 15 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 4. copy(A,B,Z):-cp(A,[],B,Z). cp(A,Vars,A,Vars):- atomic(A). cp(V,Vars,NV,NVars):- var(V),register_var(V,Vars,NV,NVars). cp(Term,Vars,NTerm,NVars):- compound(Term), Term=. . [F I Args] , 7« decompose term cp_args(Args,Vars,NArgs,NVars), NTerm=. . [F I NArgs] . 7« construct copy term cp_args([HIT],Vars,[NHI NT],NVars):- cp(H,Vars,NH,SVars), cp_args(T,SVars,NT,NVars) . cp_args([],Vars,[] ,Vars) . register_var(V,[X/H|T],N,[X/H|NT] ):- V\==X, 7 different variables register_var(V,T,N,NT). register_var(V,[X/H|T],H,[X/H|T]):- V==X. 7 same variables register_var(V,[],N,[V/N]). 7 Všetky riešenia 1. Výsledky si ľahko overíte v Prológu 2. subsets(X,S) :- isset(X), findall(Y,subset(X,Y),S). isset ( [] ) . isset([X|T]) :- \+ member(X,T), isset(T). subset ([] , []) . subset([_X|T],S) :- subset(T,S), subset([X I T],[X|S]) :- subset(T,S). 3. :- use_module(library(lists)). permutations(S,Z) :- setof(X, permutation(S,X), Z). 4. :- use_module(library(lists)). variations(S,K,Z) :- findall(Y, (subset(S,X), length(X,K), permutation(X,Y)), Z) 8 Rezolúcia 1. (a) o = [X/f (Y)] (b) neexistuje (c) a — [X/Z, Y/Z] (d) f (5) (b) Odvodenie neexistuje ani pre jeden z cieľov, odvodenia sú blokované. Problémom je, že program nie je stratiŕikovaný. a{P) c{P),Y is P + l,\ + d(Y) d(P),YÍ is P + 1, \ + c(YÍ),Y is P + 1, \d(Y) c(P),\ + d(P) fail viď poznámka [P=l]=>yiis 1 + 1,... [P = 2] => Yl is 2 + l, \ + c(2), Y is 1 + 1, \ + d(Y) \ + c(3), Y is 2 + 1, \ + d(Y) fail Y is 2 + í,\ + d(Y) \ + d(3) □ Hana Rudová, Fakulta informatiky, Masarykova univerzita 19 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 c(2) d(2),Y is 2 + l,\ + c(y) Y is 2+ l,\ + c(Y) \ + c(3) □ ^> \ + c(2) neúspešné c(3) d(3),Y is 3 + l,\ + c(T) /azž =^ \ + c(3) úspešné Poznámka: časť stromu bola pre nedostatok miesta vynechaná. V príslušnej vetve ale nikdy nenastane úspech, keďže v ďalšom kroku dostaneme cieľ v tvare d(P), . . ., \+d(P). Vo vlastnom záujme si však chýbajúcu časť stromu nakreslite. 10 Logické programovanie s obmedzujúcimi podmienkami 1. labeling( [] ) . labeling(Vars) :- sortByDomainSize(Vars,SortedVars) , SortedVars=[First I Rest] , indomain(First), label(Rest). Kde sortByDomainSize je nejaký radiaci algoritmus, ktorý namiesto porovnania X>Y používa fd_size(X,SizeX), fd_size(Y,SizeY), SizeX>SizeY 2. A in {3,5,7,9}, B in 1..4, C in 1..8 3. A in 3..9, B in 1..4, C in 1..8 4. Označme si dané odmedzenia postupne cl a c2. Dolný index pri hodnote označuje obmedzenie, ktoré bolo porušené, prípadne je OK ak bolo nájdené splňujúce priradenie (a) Hana Rudová, Fakulta informatiky, Masarykova univerzita 20 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 loif loif %ok (c) Pred samostatným prehľadávaním zaistíme hranovú konzistenciu pomocou AC3 - dostávame A in 3..4, B in 2..3, C in 1..2 3 ^>ci B — 2 =^>c2 C — í 4 ^>d B — 3 2 3 Iok Iok 2ok 5. alg([K,C,I,0,A,M,L]) :- domain([K,1,0,A,L],1,9), domain([C,M],0,9), all_distinct([K,C,I,0,A,M,L]), 10*K + C + I #= 10*0 + K, A + A #= 10*K + M, 10*0 + L + 10*K + 0 #= 10*L + I, 10*K + C + A #= 10*0 + L, I + A #= 10*K + 0, 10*0 + K + 10*K + M #= 10*L + I, labeling([],[K,C,1,0,A,M,L]). 6. Riešenie bez výpisu: sudoku4([A1,A2,A3,A4, Hana Rudová, Fakulta informatiky, Masarykova univerzita 21 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 B1,B2,B3,B4, C1,C2,C3,C4, D1,D2,D3,D4]) :- Vals = [A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,D3,D4], domain(Vals,l,4), all_distinct([A1,A2,A3,A4]), all_distinct([BI,B2,B3,B4] ) , all_distinct([C1,C2,C3,C4]), all_distinct([Dl,D2,D3,D4]), all_distinct([Al,B1,Cl,D1]), all_distinct([A2,B2,C2,D2]), all_distinct([A3,B3,C3,D3]), all_distinct([A4,B4,C4,D4]), all_distinct([Al,A2,BI,B2]), all_distinct([A3,A4,B3,B4]), all_distinct([Cl,C2,Dl,D2] ) , all_distinct([C3,C4,D3,D4] ), labeling([],Vals) . 7. Nápověda: Domy si môžeme očíslovať zľava doprava číslami 1 až 5. Pre každú národnosť, farbu, zviera, nápoj a cigarety si vytvoríme premennú, ktorá bude nadobúdať hodnoty 1 až 5 podľa príslušného domu. Následne môžeme napríklad obmedzenie "človek z prostredného domu pije mlieko" zapísať ako Mlieko #= 3 a obmedzenie "Brit býva v červenom dome" ako Brit #= Červeny. Kompletné riešenie: einstein([Nor,Brit,Sved,Dan,Nemec, Červeny,Zeleny,Zity,Modry,Biely, Caj,Kava,Mlieko,Pivo,Voda, Pes,Vták,Macka,Kon,Ryba, Pallmall,Dunhill,Blend,Bluemaster,Prince]):-Vals = [Nor,Brit,Sved,Dan,Nemec, Červeny,Zeleny,Zity,Modry,Biely, Caj,Kava,Mlieko,Pivo,Voda, Pe s,Vtak,Macka,Kon,Ryba, Pallmall,Dunhill,Blend,Bluemaster,Prince], domain(Vals,1,5), all_distinct([Nor,Brit,Sved,Dan,Nemec]), all_distinct([Červeny,Zeleny,Zity,Modry,Biely]), all_distinct([Caj,Kava,Mlieko,Pivo,Voda] ), all_distinct([Pes,Vták,Macka,Kon,Ryba] ), all_distinct([Pallmall,Dunhill,Blend,Bluemaster,Prince]), 7«Brit byva v červenom dome. Brit #= Červeny, 7«Sved chova psa. Sved #= Pes, 7«Dan pije caj . Dan #= Caj, 7«Zeleny dom stoji hned vlavo od bieleho. Zeleny #= Biely - 1, Hana Rudová, Fakulta informatiky, Masarykova univerzita 22 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 7«Majitel zeleného domu pije kavu. Zeleny #= Kava, 7«Ten, kto fajči Pall Mail, chova vtáka. Pallmall #= Vták, 7«Majitel zlteho domu fajči Dunhill. Zity #= Dunhill, 7«clovek z prostredného domu pije mlieko. Mlieko #= 3, 7«Nor byva v prvom dome. Nor #= 1, °/«Ten, kto fajči Blend, byva vedia toho, kto chova macku. (Blend #= Macka+1 ; Blend #=Macka-l), 7«Ten, kto chova kone, byva vedia toho, kto fajči Dunhill. (Kon #= Dunhill+1 ; Kon#=Dunhill-l), 7«Ten, kto fajči Blue Master, pije pivo. Bluemaster #= Pivo, "/oNemec fajči Prince. Nemec #= Prince, 7«Nor byva vedia modrého domu. (Nor #= Modry + 1 ; Nor #= Modry-1 ), y«Ten, kto fajči Blend, ma suseda, ktorý pije vodu. (Blend #= Voda + 1; Blend#= Voda-1), labeling([],Vals). 11 D C gramatiky 1. Párne čísla sú práve tie, ktorých binárny zápis končí nulou. Daná DCG môže vyzerať napríklad nasledovne: parne —> [0] . parne —> [1], parne. parne —> [0], parne. 2. Výsledná gramatika môže vyzerať takto: palindrom —> [] . palindrom —> [a] . palindrom —> [b] . palindrom —> [X],palindrom,[X], {member(X,[a,b])}. (posledný riadok je možné nahradiť dvoma rozpísaním možných hodnôt X) 3. Pre jazyk anbn napíšeme gramatiku an_bn —> [] . an_bn —> [a],an_bn,[b]. Gramatiku pre jazyk anbm kde m > n potom môžeme zadefinovať nasledujúcim spôsobom: an_bm —> an_bn, same(b). Pričom same definujeme ako Hana Rudová, Fakulta informatiky, Masarykova univerzita 23 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 same(_X) —> [] . same(X) —> [X],same(X). (teda trochu inak ako bol definovaný na cvičeniach) 4. an_b2n — > [] . an_b2n —> [a],an_bn,[b],[b]. 5. Jedno z možných riešení je veľmi podobné riešeniu pre jazyk anbncn, ktoré bolo uvedené na cvičeniach. Nižšie uvedené riešenie je založené na rovnakej myšlienke (tzn. pomocou následníkov), avšak je zapísané stručnejším spôsobom pomocou pomocného neterminálu repeat: abc —> repeat(a,X), repeat(b,s(X)), repeat(c,s(s(X))). repeat(_,0) —> [] . repeat(A,s(X)) —> [A],repeat(A,X). 6. s(S0,S) :- np(S0,Sl), vp(Sl,S). np(S0,S) :- det(S0,Sl), n(Sl,S). vp(S0,S) :- tv(S0,Sl), np(Sl,S). vp(S0,S) :- v(S0,S). det([the|S],S). det([a|S],S). det([every I S],S). n([man|S],S). n([woman I S],S) . n([park|S],S). tv([loves I S],S). tv([likes IS],S) . v([walks I S],S) . 7. závisí od vybranej vety 8. S (Ad {Yesterday), SI (NP ( N {John) ), VP (V {saw), NP (Det (a), NP (Adj {good), NP (N (movie))))))) Exp( Sub(Exp( Add(Expr(Num(5)),Exp( Mul(Expr(Num(7)),Exp( Num(2))))))),Exp( Num(4))) 9. sentence(s(Ad,S)) —> adverb(Ad), sentencel(S). adverb(ad(yesterday)) —> [yesterday]. sentencel(sl(NP,VP)) —> noun_phrase(NP), verb_phrase(VP). noun_phrase(np(N)) —> noun(N). noun_phrase(np(Det,NP)) —> determiner(Det), noun_phrase(NP). noun_phrase(np(Adj,NP)) —> adjective(Adj), noun_phrase(NP). determiner(det(a)) —> [a], adjective(adj(good)) —> [good], noun(n(john)) —> [john]. noun(n(movie)) —> [movie]. verb_phrase(vp(V,NP)) —> verb(V), noun_phrase(NP). verb(v(saw)) —> [saw]. 12 Rôzne 1. foo(X). uspeje práve ak X je prvočíslo. Program môžeme prepísať ako: Hana Rudová, Fakulta informatiky, Masarykova univerzita 24 IB013 Logické programovanie: zbierka príkladov 11. marca 2013 prime(X) :- X =\= 1, XI is X-l, test(X,Xl). test(_X,l) :- !. test(X,Y) :- X mod Y > 0, Yl is Y-l, test(X,Yl). Hana Rudová, Fakulta informatiky, Masarykova univerzita 25