Neprocedurální programování, cvičení

• Domů
• O cvičení
• Zápočty
• Poznámky ze cvičení
• Domácí úkoly
• Přihlášení studenti

Připomenutí k zápočtovým úlohám

• Termín pro zápočtové úlohy je pátek 8.7.2011. Nezapomeňte, že program je nutné i osobně předvést. Proto, pokud v červenci neplánujete být v Praze, pošlete program dříve!

Náhradní domácí úkoly

• Testíky z posledního cvičení již jsou opravené a započítané.
• Studenti, kterým chybí za testíky a domácí úlohy více než 10 bodů, nemají nárok na zápočet. Ostatní mohou vypracovat náhradní úlohy, aby body dorovnali.
• Studenti, kterým chybí maximálně 4 body, si mohou vybírat z následujících náhradních úloh (podrobnější zadání úloh v případě zájmu doplním).
• Studenti, kterým chybí více než 4 body, ale méně než 10, musí vypracovat náhradní úlohy za alespoň 4 body. Navíc si zvolí náhradní úlohu (z Haskellu nebo Prologu) rozsahu menšího zápočtového programu (podle počtu chybějících bodů). Na tématu se můžeme domluvit emailem.
• U náhradních úloh lze uznat jen úplné, bezchybné a efektivní řešení.
• Termín pro poslání náhradních úloh je úterý 28.6.2011, 13:00.
• Je možné poslat i opravu (maximálně dvakrát).
• Haskell - matice (za 1 bod)
• Řídká matice je reprezentována jako trojice (m,n,s), kde m je počet řádek, n je počet sloupců a s je seznam trojic (i,j, a_ij), kde i je číslo řádky, j je číslo sloupce a a_ij je nenulová hodnota. Seznam trojic je přitom uspořádaný vzestupně podle i a uvnitř řádek pomocí j. Definujte funkce, které v této reprezentaci realizují:
• matice a) transpozici matic
• matice b) násobení matic
• matice c) sčítání matic
• matice d) "chytré" (efektivní) umocňování matic
• Řešení by mělo být odladěné a doplněné o testovací příklady.
• Haskell - datové typy (úplné řešení je za 1 bod)
• Definujte datový typ pro reprezentace výrokových formulí a definujte následující funkce:
• formule a) vyhodnot f
• formule b) tautologie f
• formule c) splnitelna f
• Řešení by mělo být odladěné a doplněné o testovací příklady.
• Haskell - dynamické programování (úplné řešení je za 1 bod)
• Dokončete řešení úloh s mincemi a mřížkou, které jsme rozpracovali na cvičení. Řešení pomocí pole (Array).
• Řešení by mělo být odladěné a doplněné o testovací příklady.
• SCHEME - AVL strom (za 1 bod)
• Navrhněte vhodnou reprezentaci AVL-stromu a definujte pro něj základní operace:
• avl a) vyvažování
• avl b) insert
• avl c) delete
• avl d) vyhledávání
• avl e) postavení ze seznamu hodnot
• Řešení by mělo být odladěné a doplněné o testovací příklady.
• Prolog - permutace (za 1 bod)
• Pokračování dom. úlohy č.5. Napište procedury pro násobení a umocňování permutací reprezentovaných pomocí seznamu cyklů nebo seznamu obrazů. Součin permutací P1 a P2 je permutace P3, tž. P3(x)=P1(P2(x)):
• perm a) permmul(+P1, +P2, -P3) - násobení
• perm b) permpow(+P1, +N, -P2) - mocnění
• perm c) cykmul(+PC1, +PC2, -PC3) - násobení
• perm d) cykpow(+PC1, +N, -PC2) - mocnění
• Řešení by mělo být odladěné a doplněné o testovací příklady.
• Prolog - grafy (řešení dvou podúloh je za 1 bod)
• Navrhněte vhodnou reprezentaci grafu a implementujte dva z těchto algoritmů:
• grafy a) Dijkstrův algoritmus
• grafy b) Kruskalův nebo Jarníkův algoritmus
• grafy c) Algoritmus pro topologické uspořádání uzlů
• grafy c) Algoritmus pro obarvení vrcholů grafu
• Řešení by mělo být odladěné a doplněné o testovací příklady.

11. domácí úkol 11.5.2011

• Termín na dom. úlohy je kvůli rektorskému dni tentokrát 14 dnů.
• Nezapomeňte na (správnou) typovou signaturu u všech funkcí. Důležitá je i časová složitost algoritmů.
• HASKELL a) (za 1,25 bodu) Stromy
• Uvažujme binární vyhledávací strom definovaný pomocí:
  data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Eq)
  v jehož uzlech je uložena informace nějakého typu (podtřídy Ord).
• (za 0,25 bodu) Definujte funkci delete a x, která z binárního vyhledávacího stromu x vypustí uzel s hodnotou a (není-li tam, bude to identita).
• (za 0,5 bodu) Definujte funkci deleteRange a b x, která z binárního vyhledávacího stromu x vypustí uzly patřící do zadaného intervalu [a,b] (nejsou-li tam žádné, bude to identita). Řešení by mělo být efektivní (tedy ne (b-a+1)-krát delete).
• (za 0,5 bodu) Uvažujme obecný strom definovaný pomocí:
  data RTree a = REmptyTree | RNode a [RTree a] deriving (Show, Eq)
  v jehož uzlech je uložena informace nějakého typu. Definujte funkci odlisti x, která vrátí dvojici - seznam listů stromu a odlistěný strom (za list se považuje uzel s prázdným seznamem podstromů)
• HASKELL b) (za 0,5 bodu) -- Definice vlastního typu
• Napište definici datového typu Zlomek, který obsahuje hodnoty čitatele a jmenovatele (jakéhokoliv celočíselného datového typu). Vytvořte z typu Zlomek instanci tříd Eq a Num (definujte funkce (==), (+), (-), (*) pro zlomky). Nezapomeňte u operací zlomky krátit!!
• HASKELL c) (za 0,5 bodu) -- Třídy ekvivalence
• Definujte funkci tridy ekv seznam:
  tridy :: (a -> a -> Bool) -> [a] -> [[a]]
  která vrátí třídy rozkladu na množině zadané seznamem podle relace ekvivalence zadané binární funkcí ekv.
• Příklady dotazů a správných odpovědí pro a:
  > odlisti (RNode 7 [RNode 8 [], RNode 9 [RNode 10 []]])
  ([8,10],RNode 7 [RNode 9 []])
  > odlisti (RNode 7 [])
  ([7],REmptyTree)
  > odlisti (RNode 7 [RNode 8 [], RNode 9 [], RNode 10 []])
  ([8,9,10],RNode 7 [])
  > odlisti (RNode 7 [RNode 8 [RNode 1 [], RNode 2 [], RNode 3 [] ], RNode 9 [], RNode 5 [], RNode 10 [RNode 1 []]])
  ([1,2,3,9,5,1],RNode 7 [RNode 8 [],RNode 10 []])
  > deleteRange 1 10 (Node 2 (Node 1 EmptyTree EmptyTree) (Node 3 EmptyTree (Node 5 EmptyTree EmptyTree)))
  EmptyTree
  > deleteRange 2 7 (Node 3 (Node 1 EmptyTree EmptyTree) (Node 8 (Node 6 EmptyTree EmptyTree) EmptyTree))
  Node 1 EmptyTree (Node 8 EmptyTree EmptyTree)
  > deleteRange 7 10 (Node 3 (Node 1 EmptyTree EmptyTree) (Node 8 (Node 6 EmptyTree EmptyTree) EmptyTree))
  Node 3 (Node 1 EmptyTree EmptyTree) (Node 6 EmptyTree EmptyTree)
  > deleteRange 9 10 (Node 3 (Node 1 EmptyTree EmptyTree) (Node 8 (Node 6 EmptyTree EmptyTree) EmptyTree))
  Node 3 (Node 1 EmptyTree EmptyTree) (Node 8 (Node 6 EmptyTree EmptyTree) EmptyTree)
  > delete 9 (Node 3 EmptyTree (Node 8 (Node 6 EmptyTree EmptyTree) EmptyTree))
  Node 3 EmptyTree (Node 8 (Node 6 EmptyTree EmptyTree) EmptyTree)
  > delete 3 (Node 3 EmptyTree (Node 8 (Node 6 EmptyTree EmptyTree) EmptyTree))
  Node 8 (Node 6 EmptyTree EmptyTree) EmptyTree
• Příklady dotazů a správných odpovědí pro c:
  > tridy (\x y -> x `mod` 3 == y `mod` 3) [1..10]
  [[1,4,7,10], [2,5,8], [3,6,9]]
  > tridy (\x y -> x `mod` 2 == y `mod` 2) [1..10]
  [[2,4,6,8,10],[1,3,5,7,9]]
  > tridy (\x y -> x `div` 3 == y `div` 3) [1..10]
  [[1,2],[3,4,5],[6,7,8],[9,10]]
  > tridy (\x y -> x `div` 3 == y `div` 3) []
  []
  > tridy (\x y -> x `div` 100 == y `div` 100) [1..10]
  [[1,2,3,4,5,6,7,8,9,10]]

10. domácí úkol 4.5.2011

• Nezapomeňte na (správnou) typovou signaturu u všech funkcí. Důležitá je i časová složitost algoritmů.
• HASKELL a) (za 0,5 bodu) FOR-cyklus
• Napište funkci qsum a b c analogickou následujícímu for-cyklu v jazyku C:
  

     s=0;
     for (i = A; C(i) < B(i); i++)
          s += C(i);
     

  
  Kde A, B, C jsou parametry - A je číslo, B a C jsou funkce jedné proměnné, to budou také parametry požadované funkce qsum. Cílem je tedy spočítat součet hodnot C(A), C(A+1), C(A+2), C(A+3), ..., C(A+j), kde j je maximální takové, že C(A+j) < B(A+j).
• Příklady dotazů a správných odpovědí :
  > qsum 2 (\x -> 21) (\x -> x*x)
  29
  > qsum 4 (\x -> 6666) (\x -> x*x-x)
  183754
  > qsum 1 (\x -> 10) (\x -> x)
  45
  > qsum 1 (\x -> x*x) (\x -> x*x*x)
  0
  > qsum 1 (\x -> x*x*x*3333) (\x -> x*x*x*x+113)
  82201691350171302
• HASKELL b) (za 2 body) Nekonečné posloupnosti
• (za 0,5 bodu) Definujte funkci posl1, která vytvoří nekonečný seznam. Posloupnost je dána následujícím rekurentním předpisem:
  a_0 = 1
  a_1 = 2
  a_2 = 3
  a_[n+1] = 3*a_n + 2*a_[n-1] + a_[n-2]
  
• (za 0,5 bodu) Definujte funkci posl2, která vytvoří nekonečný seznam. Posloupnost je dána následujícím rekurentním předpisem:
  a_0 = 3
  a_1 = 2
  a_2 = 1
  a_n = a_0 + a_1 + ... + a_[n-1]
  
• (za 0,5 bodu) Uvažujme Pascalův trojúhelník jako nekonečnou datovou strukturu (např. seznam seznamů). Definujte funkci pascal, která Pascalův trojúhelník vytvoří.
• (za 0,5 bodu) Definujte funkci prvocisla, která vytvoří nekonečný seznam prvočísel.
• Příklady dotazů a (snad :)) správných odpovědí :
  - odpověď na následující dotazy by měla být okamžitá
  > posl1!!12
  1496513
  > posl2!!12
  3072
  > posl1!!100
  26248960555212191101531354990599576648993957964622882351
  > posl2!!100
  950737950171172051122527404032
  > take 10 pascal
  [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1],[1,6,15,20,15,6,1], [1,7,21,35,35,21,7,1],[1,8,28,56,70,56,28,8,1],[1,9,36,84,126,126,84,36,9,1]]
  > pascal!!100
  [1, 100, 4950, 161700, 3921225, 75287520, 1192052400, 16007560800, 186087894300, 1902231808400, 17310309456440, 141629804643600, 1050421051106700, 7110542499799200, 44186942677323600, 253338471349988640, 1345860629046814650, 6650134872937201800, 30664510802988208300, 132341572939212267400, 535983370403809682970, 2041841411062132125600, 7332066885177656269200, 24865270306254660391200, 79776075565900368755100, 242519269720337121015504, 699574816500972464467800, 1917353200780443050763600, 4998813702034726525205100, 12410847811948286545336800, 29372339821610944823963760, 66324638306863423796047200, 143012501349174257560226775, 294692427022540894366527900, 580717429720889409486981450, 1095067153187962886461165020, 1977204582144932989443770175, 3420029547493938143902737600, 5670048986634686922786117600, 9013924030034630492634340800, 13746234145802811501267369720, 20116440213369968050635175200, 28258808871162574166368460400, 38116532895986727945334202400, 49378235797073715747364762200, 61448471214136179596720592960, 73470998190814997343905056800, 84413487283064039501507937600, 93206558875049876949581681100, 98913082887808032681188722800, 100891344545564193334812497256, 98913082887808032681188722800, 93206558875049876949581681100, 84413487283064039501507937600, 73470998190814997343905056800, 61448471214136179596720592960, 49378235797073715747364762200, 38116532895986727945334202400, 28258808871162574166368460400, 20116440213369968050635175200, 13746234145802811501267369720, 9013924030034630492634340800, 5670048986634686922786117600, 3420029547493938143902737600, 1977204582144932989443770175, 1095067153187962886461165020, 580717429720889409486981450, 294692427022540894366527900, 143012501349174257560226775, 66324638306863423796047200, 29372339821610944823963760, 12410847811948286545336800, 4998813702034726525205100, 1917353200780443050763600, 699574816500972464467800, 242519269720337121015504, 79776075565900368755100, 24865270306254660391200, 7332066885177656269200, 2041841411062132125600, 535983370403809682970, 132341572939212267400, 30664510802988208300, 6650134872937201800, 1345860629046814650, 253338471349988640, 44186942677323600, 7110542499799200, 1050421051106700, 141629804643600, 17310309456440, 1902231808400, 186087894300, 16007560800, 1192052400, 75287520, 3921225, 161700, 4950, 100, 1]
  > prvocisla!!300
  1993
  > prvocisla!!500
  3581
  

9. domácí úkol 27.4.2011

• Dovysvětlení zmatku ze cvičení:
  > (1>) 3
  False
  > (>1) 3
  True
  > ((>) 1) 3
  False
  
• HASKELL a) (za 1 bod) Na rozjezd
• (za 0,25 bodu) Definujte funkci soucin s, která spočte součin všech prvků seznamu celých čísel.
• (za 0,25 bodu) Definujte funkci aritm a_0 d n, která vytvoří seznam obsahující prvních n členů aritmetické posloupnosti (a_i = a_0 + d * i).
• (za 0,25 bodu) Definujte funkci splitAt_ n s, která rozdělí seznam s na prefix a suffix, kde prefix má délku n. Vrátí dvojici seznamů. Můžete použít standardně definované funkce take a drop.
• (za 0,25 bodu) Definujte funkci pocetKorenu a b c, která spočte počet kořenů kvadratické rovnice (uvažovaná rovnice je ve tvaru a x^2 + b x + c = 0).
• Nezapomeňte na (správnou) typovou signaturu!
• HASKELL b) (za 0,75 bodu) Mergesort
• Definujte funkci mergesort s, která setřídí seznam . K tomu využijte (a definujte) následující pomocné funkce.
• split, která rozdělí seznam na dva.
• merge, která spojí dva setříděné seznamy.
• Nezapomeňte na (správnou) typovou signaturu! Dodržte optimální časovou složitost algoritmu.
• HASKELL c) (za 0,5 bodu) Quicksort
• Definujte funkci quicksort s, která setřídí seznam. Můžete využít standardní funkci filter, ++ aj.
• Nezapomeňte na (správnou) typovou signaturu! Dodržte optimální časovou složitost algoritmu.

8. domácí úkol 20.4.2010

• PROLOG a) (za 1 bod) Přelévání vody - prohledávání stavového prostoru
  Jsou dány dvě nádoby o oběmy X litrů a Y litrů. Naším cílem je dosáhnout toho, aby v první nádobě bylo právě Z litrů. K dispozici je nevyčerpatelný zdroj a nevyčerpatelný odtok. Na začátku jsou nádoby prázdné. Definujte predikát nadoby (+Vstup, - Reseni), kde Vstup je tvaru [X,Y,Z], a Reseni je seznam stavů z počátečního do koncového. Predikát by měl nalézt nejkratší cestu. Vhodná reprezentace stavu je součástí řešení a měla by být popsaná.
• PROLOG b) (za 1 bod) Misionáři a lidojedi - prohledávání stavového prostoru
  Je dáno X misionářů, Y lidojedů a Z rovnoběžných řek. Lze přepravit všechny misionáře a lidojedy z nejlevějšího břehu na nejpravější tak, aby na žádném (mezi)břehu nebylo v žádném okamžiku více lidojedů nežli misionářů? Pokud by se tak stalo, lidojedi misionáře sežerou. Na každé řece je k dispozici jedna loďka pro dvě osoby. Definujte predikát lidojedi (+Vstup, - Reseni), kde Vstup je tvaru [X,Y,Z], a Reseni je seznam stavů z počátečního do koncového. Predikát by měl nalézt nejkratší cestu. Vhodná reprezentace stavu je součástí řešení a měla by být popsaná.
• SCHEME BONUS c) (za 1 bod) Třídění
• Tuto úlohu nemusíte řešit, pokud ale máte za prvních sedm domácích úloh méně než 14 bodů a pošlete správné řešení, můžete si nahradit část ztracených bodů (do výše maximálně 14). Pozor, od příště už bonusové úlohy zřejmě nebudou.
• Napište funkci minimumS , která má na vstupu seznam čísel a vrátí minimální číslo ze seznamu.
• Napište funkci deleteS , která má dva parametry - seznam čísel a prvek seznamu. Funkce vrátí seznam bez prvního výskytu prvku.
• Napište funkci minSort , která má jeden parametr - seznam čísel (čísla se v něm mohou opakovat). Funkce vrátí vzestupně setříděný seznam. Implementuje třídění přímým výběrem minima.
• Napište funkci insertS , která má dva parametry - vzestupně setříděný seznam čísel (čísla se mohou opakovat) a číslo. Funkce vrátí seznam, který vznikne zařazaním čísla na správné místo do seznamu.
• Napište funkci insertSort , která má jeden parametr - seznam čísel (čísla se v něm mohou opakovat). Funkce vrátí vzestupně setříděný seznam. Implementuje třídění vkládáním (postupným zatřizováním prvků).

7. domácí úkol 13.4.2011

• Protože si budu moct zaslaná řešení prohlédnout nejdříve až v pondělí, prodlužuji pro tentokrát termín pro zaslání případné opravy do začátku následujícího cvičení. :)
• PROLOG nebo SCHEME - Prostorový (závěsný) mobil
• Prostorový mobil je tvořen lanky, tyčkami a závažími. Na jednom lanku vždy visí buď závaží nebo tyčka. Na obou koncích každé tyčky je zavěšeno další lanko s (pod)mobilem. Lanka mají fixní délku. Každá tyčka je lankem rozdělena na dvě ramena obecně různých délek. Každé závaží má svou hmotnost.
  
  mobil ::= levé_rameno pravé_rameno
  rameno ::= délka_ramena pod_mobil
  délka_ramena ::= číslo
  pod_mobil ::= mobil nebo číslo ( = hmotnost závaží)
  
  
• Navrhněte vhodnou datovou strukturu pro reprezentaci prostorového mobilu a definujte následující predikáty:
• (za 0,5 bodu) vyvazeny(+Mobil) resp. (vyvazeny mobil) - Mobil je vyvážený, pokud jsou všechna ramena vodorovná (hmotnost lanek a tyček přitom zanedbáváme).
• (za 1 bod) bezpecny(+Mobil) resp. (bezpecny mobil) - Mobil je bezpečný, pokud při libovolné rotaci ramen nemůže dojít ke srážce. Můžeme předpokládat, že Mobil je vyvážený.
• (za 0,5 bodu) ekvivalentní(+MobilA,+MobilB) resp. (ekvivalentni mobilA mobilB) - MobilA mohu získat z MobiluB vhodným otáčením ramen.
• Protože navržení vhodné datové struktury je součástí řešení, posílejte spolu s řešením i slovní popis použité datové struktury.
• I pokud se rozhodnete pro SCHEME, pošlete otestované řešení.
• SCHEME BONUS b) (za 1 bod)
• Tuto úlohu nemusíte řešit, pokud ale máte za prvních šest domácích úloh méně než 12 bodů a pošlete správné řešení, můžete si nahradit část ztracených bodů (do výše maximálně 12).
• Pošlete otestované, přeložitelné řešení.
• Základní formy ve SCHEME.
• Interpretery pro SCHEME
• b1) (za 0,3 bodu) Na cvičení jsme definovali funkci map pro seznamy. Napište funkci (mapTree f t) , která je analogií funkce map, ale na vstupu má na místo seznamu binární strom t a funkci f. Funkce mapTree aplikuje funkci f na každý vnitřní uzel stromu (tj. na jeho hodnotu) a vrátí výsledný strom.
• b2) (za 0,3 bodu) Na cvičení jsme definovali funkce foldl, foldr pro seznamy. Napište funkci (foldTree f p t) , která je analogií funkce foldr, ale na vstupu má na místo seznamu binární strom. Funkce foldTree vrátí hodnotu p pro listy stromu t (listy stromu jsou prázdné stromy) a hodnotu funkce f (se třemi parametry) rekurzivně na vnitřní uzly stromu (parametry f jsou hodnota uzlu, "to, co přišlo zleva" a "to, co přišlo zprava").
• b3) (za 0,4 bodu) Napište čtyři z následujících funkcí za využití foldTree nebo mapTree: sumTree (součet prvků ve stromě), countTree (počet prvků ve stromě), minTree (minimální prvek ve stromě), dvakrat (vrací strom, kde budou všechny prvky vynásobené dvěma), nadruhou (vrací strom, kde budou všechny prvky umocněné nadruhou), preved (vrací strom, kde bude hodnota každého uzlu tvořena dvojicí (původní_hodnota počet_uzlů_v_podstromu).
• Stromy:
  ( define (tree V L R) (list V L R))
  ( define emptyT '())
  ( define (value s) (car s))
  ( define (left s) (cadr s))
  ( define (right s) (caddr s))

6. domácí úkol 6.4.2011

• Zápočtové programy - termíny:
• do 14.4.2011 výběr zadání - náčrt vhodných témat naleznete zde.
• do 20.4.2011 stručná specifikace (typicky jeden odstavec)
• do 8.7.2011 program a dokumentace
• Vyberte si libovolné dvě z úloh a), b), c), maximum bodů, které lze získat, je 2 body. Třetí úloha je opět bonusová - nahradí část v minulosti ztracených bodů (do výše maximálně 10).
• a) (za 1 bod) Binární halda
  Binární haldu lze reprezentovat různě (jako strom, v poli,...). V binární haldě jsou uloženy prvky (porovnatelné pomocí @<) tak, že hodnota každého vrcholu je menší nebo rovna než hodnoty jeho synů. Zvolte vhodnou datovou strukturu pro reprezentaci binární haldy a implementujte nad ní základní operace:
• extractMin(+Halda,-Minimum,-Halda1) - Halda1 vznikne odebráním Minima z Haldy. Ideálně O(log n)
• insert(+Halda,+Prvek,-Halda1) - Halda1 vznikne přidáním Prvku do Haldy. Ideálně O(log n)
• postav(+Pole,-Halda) - Z Pole přirozených čísel postaví haldu. Lze řešit postupným vkládáním prvků. Ideálně O(n log n)
• heapsort(+Pole,-SetridenePole) - Z pole postaví haldu a vytvoří setříděné pole postupným odebíráním minima z haldy. Ideálně O(n log n)
• Pozor, seznam v Prologu není pole s konstantním přístupem, tedy reprezentace seznamem zřejmě nepovede k ideální složitosti. Stromovou reprezentaci pak zřejmě bude třeba pro zajištění požadované složitosti rozšířit o nějaké potřebné údaje.
• V komemtáři programu nebo v těle zprávy stručně popište zvolenou reprezentaci.
• Příklady dotazů a odpovědí tentokrát závisí na zvolené reprezentaci. Třídění lze zkontrolovat snadno porovnáním např. se standardním sortem.
  ?- heapsort([3,1,2,4],H)
  H = [1,2,3,4].
  ?- heapsort([petr,pepa,adam],H)
  H = [adam, pepa, petr].
  
• b1) (za 0.5 bodu) Vyhodnocování booleovských výrazů
  Definujte predikát vyhodnot(+Vyraz,+TabulkaProměnných, -Hodnota). Vyraz je booleovský výraz sestavený z booleovských konstant true a false, proměnných (libovolné atomy s výjimkou true a false), z logických spojek (not, and, or, implikace, ekvivalence) a závorek. Logickým spojkám přitom odpovídají následující operátory: - (NOT), * (AND), + (OR), -> (implikace), <-> (ekvivalence). Tedy term true*(false+ -true) odpovídá formuli TRUE AND (FALSE OR NOT TRUE).
  Hodnota je pravdivostní hodnota booleovského Vyrazu pro pravdivostní hodnoty proměnných, které jsou uloženy v seznamu TabulkaProměnných. TabulkaProměnných je seznam termů ve tvaru proměnná:true nebo proměnná:false.
  
  Spojky definujte jako operátory např takto:
  :- op(200, fy, -). % NOT
  :- op(210, yfx, *). % AND
  :- op(220, yfx, +). % OR
  :- op(230, xfy, ->). % IMPLIKACE
  :- op(240, xfx, <->). % EKVIVALENCE
  :- op(260, xfy, :).
  
  Pokud Váš interpret nedovolí dané operátory předefinovat, použijte klidně jiné, ale upozorněte mě na to. :)
  Příklady:
  ?- vyhodnot((-false)*(true+false),[],H).
  H = true.
  ?- vyhodnot((-x)*(x+(y+false)),[x:false,y:true,z:true],H)
  H = true.
  
• b2) (za 0,5 bodu) Definuje predikát splnitelna(+Vyraz), kde výraz Vyraz je splnitelná formule (nabývá hodnoty true pro nějaké pravdivostní hodnoty svých proměnných).
• c) (za 1 bod) Množiny
  Definujte predikát mnozina(+Vyraz,+TabulkaProměnných, -Množina). Vyraz je aritmetický výraz sestavený z proměnných (libovolné atomy), z množinových operátorů (+ je sjednocení, . je průnik, * je kartézský součin,- je odčítání, ^ je xor) a závorek. Tedy term x+(y*z) odpovídá sjednocení množiny x a kartézského součinu množin y a z.
  TabulkaProměnných je seznam termů ve tvaru proměnná:[] nebo proměnná:[H|T] (seznam termů uspořádaných od nejmenšího po největší - bez duplicit). Množina je výsledná množina (uspořádaný seznam prvků množiny od nejmenšího po největší - bez duplicit). Prvky množiny nemusí být pouze čísla (ale jsou porovnatelné pomocí @<).
  Důležitá je efektivita implementace jednotlivých množinových operací. Ta by měla být (až na kartézský součin) lineární.
  
  Spojky definujte jako operátory např. takto:
  :- op(210, yfx, *).
  :- op(220, yfx, +).
  :- op(230, yfx, -).
  :- op(230, yfx, .).
  :- op(240, yfx, ^).
  :- op(260, xfy, :).
  
  Například:
  ?- mnozina((x+y)-z,[x:[1,2,5],y:[3,5],z:[1,5,7]],M).
  M = [2,3]
  ?- mnozina(x*(y.z),[x:[1,2],y:[3,5],z:[1,5,7]],M).
  M = [[1,5],[2,5]]
  ?- mnozina(x*(y*z),[x:[1,2],y:[3,5],z:[1]],M).
  M = [[1,[3,1]],[1,[5,1]],[2,[3,1]],[2,[5,1]]]
  
  
• Příklady dalších dotazů a (snad) správných odpovědí pro b, c:
  ?- vyhodnot(true,[],V).
  V=true.
  
  ?- vyhodnot(false,[],V).
  V=false.
  
  ?- vyhodnot(-true,[],V).
  V=false.
  
  ?- vyhodnot(true*(-false),[],V).
  V=true.
  
  ?- vyhodnot((-true)+(-false),[],V).
  V=true.
  
  ?- vyhodnot(false->true,[],V).
  V=true.
  
  ?- vyhodnot(-(false*true),[],V).
  V=true.
  
  ?- vyhodnot((false*(-true))<->(true -> false),[],V).
  V=true.
  
  ?- vyhodnot((true*(false -> true))<->(true -> false),[],V).
  V=false.
  
  ?- vyhodnot(false,[x:true],V).
  V=false.
  
  ?- vyhodnot(x,[x:true],V).
  V=true.
  
  ?- vyhodnot(x,[x:false],V).
  V=false.
  
  ?- vyhodnot(x + y,[x:false, y:true],V).
  V=true.
  
  ?- vyhodnot(x -> (y -> -x),[x:false, y:true],V).
  V=true.
  
  ?- vyhodnot(( -x + y) <-> -(-y * -x),[x:true, y:true],V).
  V=true.
  
  ?- vyhodnot(x* -y*z* -a* -b,[a:false,x:true,y:false,z:true,b:false],V).
  V=true.
  
  ?- splnitelna(true).
  yes
  
  ?- splnitelna(false).
  no
  
  ?- splnitelna(true -> x).
  yes
  
  ?- splnitelna(x + -x).
  yes
  
  ?- splnitelna(x * -x).
  no
  
  ?- splnitelna(x <-> (y -> x) ).
  yes
  
  ?- splnitelna((-x -> -y) <-> (y -> x) ).
  yes
  
  ?- mnozina((x.y.z)^u,[x:[1,3,4,5,6],y:[2,3,6,8],z:[4,6,7],u:[1,2,3]],K).
  K = [1, 2, 3, 6].
  
  ?- mnozina((x.y.z)-x,[x:[1,3,4,5,6],y:[2,3,6,8],z:[4,6,7],u:[1,2,3]],K).
  K = [].
  
  ?- mnozina((x+y).(z+u),[x:[1,3,4,5,6],y:[2,3,6,8],z:[4,6,7],u:[1,2,3]],K).
  K = [1, 2, 3, 4, 6].
  
  ?- mnozina(((x+y)-u).(z^u),[x:[1,3,4,5,6],y:[2,3,6,8],z:[4,6,7],u:[1,2,3]],K).
  K = [4, 6].
  
  ?- mnozina((x-u)*(x.u),[x:[1,3,4,5,6],y:[2,3,6,8],z:[4,6,7],u:[1,2,3]],K).
  K = [[4, 1], [4, 3], [5, 1], [5, 3], [6, 1], [6, 3]].
  
  

5. domácí úkol 30.3.2011

• Permutace
• Tato úloha má několik podúloh. Stačí, pokud pošlete řešení libovolné podmnožiny z nich se součtem 2 body. Zbylé úlohy nemusíte řešit, pokud ale máte za první čtyři domácí úlohy méně než 8 bodů a pošlete správné řešení, můžete si nahradit část ztracených bodů (do výše maximálně 8).
• a) (za 0,5 bodu) Na vstupu máme seznam S, který reprezentuje permutaci množiny přirozených čísel {1,2,...,n}. Definujte predikát nextPerm(+S,-NS), který k S vrátí lexikograficky následující permutaci. Věnujte pozornost časové složitosti - měla by být lineární (O(n)).
• b) Permutaci množiny n přirozených čísel {1,2,...,n} lze zadat různými způsoby:
• jako seznam obrazů [p(1),p(2),...,p(n)], např. P = [3,2,1,5,4]
• jako seznam cyklů, zde C = [[1,3],[2],[4,5]]
• jako vektor inverzí, zde I = [0,1,2,0,1]. I je posloupnost délky n pro kterou platí:
  I(i) = počet prvku {j < i | P(j) > P(i)}
• Definujte následující predikáty:
• b1) (0,5 bodu) perminv (+P,-I), který k dané permutaci (zadané jako seznam obrazů) určí příslušný vektor inverzí,
• b2) (0,5 bodu) invperm (+I,-P), který k danému vektoru inverzí určí příslušnou permutaci,
• b3) (0,5 bodu) permcyk (+P,-C), který k dané permutaci (zadané jako seznam obrazů) určí příslušný seznam cyklů,
• b4) (0,5 bodu) cykperm (+C,-P), který k danému seznamu cyklů určí příslušnou permutaci.
• Věnujte pozornost časové složitosti řešení (měla by být nejvýše kvadratická).
• Návody k úlohám (samozřejmě je ale lze řešit i jinak):
• b1) perminv - lze řešit přímočaře (rekurzí nebo s aku)- spočteme vždy počet větších prvků v seznamu před p(i), případně si pomůžeme otočením seznamu.
• b2) invperm - opět si můžeme pomoct otočením seznamu inverzí, pak stačí vzít pomocný seznam S=[N,..,1] a odebírat z něj vždy (I(i)+1)-ní prvek - (víme, že I(i) prvků v S je větších než p(I)).
• b3) permcyk - permutaci můžeme snadno rozdělit na seznam dvojic [i,p(i)]. Tyto dvojice pak můžeme pospojovat do cyklů [i,p(i),p(p(i)),...,x], kde p(x)=i.
• b4) cykperm - Stačí cykly roztrhat na dvojice [i,p(i)]. Ty pak buď setřídíme, nebo permutaci vyrobíme přímo.
• c) (1 bod) Definujte predikát nthPerm(+N,?K,?P), kde seznam P je K-tá permutace čísel {1,2,...,N} podle lexikografického uspořádání. Predikát by měl fungovat oběma směry: pro K najít K-tou permutaci, pro permutaci P zjistit, kolikátá je.
• Úlohu c) stačí poslat do 14 dnů. Můžete případně poslat i proceduru jen pro jeden směr.
• Pro každý směr bude třeba napsat zvláštní proceduru, dají se pak spojit do jedné pomocí testů var a nonvar
• Časová složitost pro oba směry by měla být O(n^2). Pozor, volání nextPerm k-krát má časovou složitost O(kn) = O(n.n!). Předpokládáme, že aritmetické operace (např. násobení) jsou konstantní.
• Příklady dotazů a správných odpovědí (další snad doplním):
  ?- nextperm([2,3,1,4], P).
  P = [2,3,4,1]
  
  ?- nextperm([4,5,3,2,1], P).
  P = [5,1,2,3,4]
  
  ?- nextperm([12,4,6,8,10,2,14,13,11,9,7,5,3,1], P).
  P = [12,4,6,8,10,3,1,2,5,7,9,11,13,14]
  
  ?- nextperm([5,4,3,2,1], P).
  no. % nebo P = [1,2,3,4,5]
  
  ?- perminv([1,3,2],I).
  I = [0,0,1].
  
  ?- invperm([0,0,1],P).
  P = [1,3,2].
  
  ?- perminv([10,11,12,13,8,3,9,5,7,1,4,6,2,17,18,19,16,14,20,15],I).
  I = [0,0,0,0,4,5,4,6,6,9,8,7,11,0,0,0,3,4,0,5].
  
  ?- invperm([0,0,0,0,4,5,4,6,6,9,8,7,11,0,0,0,3,4,0,5],P).
  P = [10,11,12,13,8,3,9,5,7,1,4,6,2,17,18,19,16,14,20,15].
  
  ?-permcyk([10,11,5,6,7,8,9,4,3,2,12,1,13,14,15],C).
  C=[[1,10,2,11,12],[3,5,7,9],[4,6,8],[13],[14],[15]]
  
  ?-cykperm([[1,10,2,11,12],[3,5,7,9],[4,6,8],[13],[14],[15]],P).
  P=[10,11,5,6,7,8,9,4,3,2,12,1,13,14,15]
  
  ?-permcyk([1,2,3,4,5],C).
  C=[[1],[2],[3],[4],[5]]
  
  ?-cykperm([[1],[2],[3],[4],[5]],P).
  P=[1,2,3,4,5]
  
  ?- permcyk([2,3,4,5,6,1],C).
  C = [[1,2,3,4,5,6]] ;
  
  ?- cykperm([[1,2,3,4,5,6]],P).
  P = [2,3,4,5,6,1] ;
  
  ?- nthPerm(5,1,P).
  P = [1,2,3,4,5]
  
  ?- nthPerm(5,K,[1,5,2,4,3]).
  K = 20
  
  ?- nthPerm(4,K,[4,1,3,2]).
  K = 20
  
  

4. domácí úkol 23.3.2011

• a) (za 0,7 bodu) Na vstupu máme dvě matice A a B. Definujte proceduru vynasob(+A,+B,-M), která implementuje násobení matic. Matice jsou reprezentovany jako seznamy řádků.
• Predikát by měl odpovědět fail. pro matice, které nelze navzájem vynásobit (matice jdou navzájem vynásobit, pokud se počet sloupců první matice rovná počtu řádků druhé matice). Je možné, že tuto podmínku bude vaše procedura splňovat automaticky - pokud ne, bude třeba ji otestovat zvlášť.
• b) (za 0,6 bodu) Na vstupu máme seznam S. Definujte proceduru multijoin(+S,?T), kde seznam T je "multisjednocením" seznamu S. Multisjednocením se rozumí odstranění všech hranatých závorek, tedy obsahuje-li seznam prvek, který je také seznam, tak je nahrazen prvky tohoto seznamu, například z [1,[2,[],3,[4]],[[[]],5,muz(jan),m]] se nahrazením získá seznam [1,2,3,4,5,muz(jan),m].
  • Můžete použít nerovnost (\=), případně řez. Budou potřeba.
• c) (za 0,7 bodu) Na vstupu máme zestručněný seznam S celých čísel. Prvky S jsou buď čísla nebo "intervaly" tvaru x..y, kde x a y jsou čísla. Definujte proceduru rozvin(+S,?T), která převede S na uplný seznam celých čísel T - všechny prvky tvaru x..y se nahradí posloupností x,x+1,...,y, je-li x<=y, či x,x-1,...,y, je-li x>y.
  • Operátor .. definujte pomocí op/3 (přidejte do programu pravidlo :- op(200,xfx,..).). Případně ho můžete nahradit libovolným jiným binárním operátorem (např. +).
  • K vyřešení této úlohy není potřeba řez.
• Příklady dotazů a správných odpovědí:
  ?- vynasob([[2, 3], [1, 4]],[[-1, 2], [1, -2]], M).
  M = [[1, -2], [3, -6]]
  
  ?- vynasob([[2,3,1], [1,4,1]],[[-1, 2, 1], [1, -2, 0]], M).
  fail.
  
  ?- vynasob([[1, 1, 1, 2], [5, -1, 0, 0], [1, 0, -1, 0]],[[1, 1], [5, 1], [-1, 0], [1, 1]],M).
  M = [[7, 4], [0, 4], [2, 1]]
  
  ?- multijoin([[[a]],1,2,[a,[b,[]]]],S).
  S = [a,1,2,a,b]
  
  ?- multijoin([f([a]),[a,[a],a],[a],a],S).
  S = [f([a]),a,a,a,a,a]
  
  ?- multijoin([[[],[[],[[]]],[[]],[]],[[]],[[[]],[]]],S).
  S = []
  
  ?-rozvin([2,3..5,7,3..1,5,3..3],S).
  S = [2, 3, 4, 5, 7, 3, 2, 1, 5, 3]
  
  

3. domácí úkol 16.3.2011

• Pokračování příkladu ze cvičení - viz. predikát prostredni/2 řešený trikem. Bez použití aritmetiky (operátor is atd.) definujte následující predikáty:
• a) (za 0.5 bodu) polovinymuzu(+S,-T1,-T2), seznam S je zřetězením seznamů T1 a T2, přičemž počet mužů v T1 a v T2 se liší nejvýše o 1 (na počtu žen v T1, T2 nezáleží).
• b) (za 0.5 bodu) tretinymuzu(+S,-T1,-T2,-T3), seznam S je zřetězením seznamů T1, T2 a T3, přičemž počet mužů v libovolných dvou ze seznamů T1,T2 a T3 se liší nejvýše o 1 (na počtu žen v T1, T2, a T3 nezáleží).
• Uvažujeme seznamy pouze osob (mužů a žen), muži jsou definovaní pomocí predikátu muz/1, ženy pomocí predikátu zena/1. Prvky se mohou v seznamu opakovat.
• Řešení často není jednoznačné. Existuje více variant/řezů (záleží na ženách uprostřed seznamu (a případně na prostředním muži), do které části padnou). V tom případě stačí, když procedura vrátí jednu variantu (nejlépe buď jen jednu nebo všechny!).
• Pozor na krajní případy - prázdný či jednoprvkový seznam, seznam jen žen apod.
• e) BONUS (za 1 bod) predikát polovinymuzu/3, napsaný tak, aby mohl být použit i v dotazech typu polovinymuzu(+,+,+) a rozpoznal právě všechna správná řešení. Při volání polovinymuzu(+,-,-) by predikát měl postupně generovat všechny správné varianty. Pozor, nehledáme všechny možné permutace, jen všechny "řezy" při zachování pořadí.
• c) (za 1 bod) Na vstupu máme matici M. Definujte predikát rozbal(+M,?S), který do seznamu S poskládá prvky matice M tak, jak leží na spirále. Matice nemusí být čtvercová. Viz vzorový příklad. Pozor hlavně na krajní případy, jako jsou "malé" matice.
• Příklad databáze faktů:
  % muz(X)
  muz(karel).
  muz(tomas).
  muz(lukas).
  muz(david).
  muz(pavel).
  muz(milan).
  muz(simon).
  muz(jirka).
  muz(quido).
  muz(vojta).
  muz(m).
  
  % zena(X)
  zena(pavla).
  zena(verka).
  zena(petra).
  zena(marta).
  zena(klara).
  zena(zdena).
  zena(hanka).
  zena(z).
  
  
• Příklady dotazů a správných odpovědí (nicméně často je správně více variant)
  ?- polovinymuzu([karel,tomas,lukas,david,pavel,jirka,quido,vojta,simon,milan],A,B).
  A = [karel,tomas,lukas,david,pavel] , B = [jirka,quido,vojta,simon,milan] ;
  fail.
  
  ?- polovinymuzu([pavla,karel,verka,petra,tomas,zdena],A,B).
  A = [pavla,karel] ,
  B = [verka,petra,tomas,zdena] ;
  fail.
  % zde existují dvě alternativní správná řešení: A = [pavla,karel, verka,petra], B = [tomas,zdena] nebo A = [pavla,karel, verka], B = [petra,tomas,zdena]
  
  ?- polovinymuzu([z,z,z,z,m,m,z],A,B).
  A = [z,z,z,z,m] , B = [m,z] ;
  fail.
  % jediné správné řešení
  
  ?- tretinymuzu([karel,tomas,lukas,david,pavel,jirka,quido,vojta,simon,milan],A,B,C).
  A = [karel,tomas,lukas,david] ,
  B = [pavel,jirka,quido] ,
  C = [vojta,simon,milan] ;
  fail.
  % i zde je více správných řešení
  
  ?- tretinymuzu([pavla,karel,verka,petra,tomas,lukas,david,marta,pavel,jirka,klara,quido,vojta,simon,milan,zdena],A,B,C).
  A = [pavla,karel,verka,petra,tomas,lukas,david] ,
  B = [marta,pavel,jirka,klara,quido] ,
  C = [vojta,simon,milan,zdena] ;
  fail.
  % i zde je více správných řešení
  
  ?- tretinymuzu([z,z,m,m,m,z,z,z,z],A,B,C).
  A = [z,z,m] , B = [m] , C = [m,z,z,z,z] ;
  fail.
  % jediné správné řešení
  
  ?- rozbal([[1,2,3],[4,5,6],[7,8,9]],X).
  X=[1,4,7,8,9,6,3,2,5]
  
  ?-rozbal([[1,2,3,4,5],[6,7,8,9,0],[1,2,3,4,5]],X).
  X=[1,6,1,2,3,4,5,0,5,4,3,2,7,8,9]
  
  ?- rozbal([[1,2],[3,4],[5,6]],X).
  X=[1,3,5,6,4,2]
  
  ?- rozbal([[a],[b],[c]],X).
  X=[a,b,c]
  
  
• Ilustrační příklad pro bonusovou úlohu:
  ?-polovinymuzu([m,z,m,z,m],X,Y).
  X = [m], Y = [z, m, z, m] ;
  X = [m, z], Y = [m, z, m] ;
  X = [m, z, m], Y = [z, m] ;
  X = [m, z, m, z], Y = [m];
  false.
  

2. domácí úkol 9.3.2011

• Příklad na rodinné vztahy.
• Uvažujeme databázi faktů muz(X), zena(X), rodina(Otec, Matka, Seznam dětí od nejstaršího k nejmladšímu). Implementujte libovolné čtyři z těchto procedur (maximum bodů, které lze získat, je 2):
• a) (za 0.25 nebo 0.5 bodu) Definujte predikát bratri(?Ci,?SeznamBratru). Jednodušší varianta za 0.25 bodu je, pokud SeznamBratru je včetně Ci (je-li Ci muž).
• b) (za 0.5 bodu) Definujte predikát mladsisestra(?Ci,?MladsiSestra).
• c) (za 0.5 bodu) Definujte predikát starsibratr(?Ci,?StarsiBratr).
• d) (za 0.5 bodu) Definujte predikát nejmladsisestra(?Ci,?NejmladsiSestra).
• e) (za 0.5 bodu) Definujte predikát nejstarsibratr(?Ci,?NejstarsiBratr).
• Pozor! - nejmladší sestra Ci nemusí být mladší než Ci, stejně tak nejstarší bratr Ci nemusí být starší než Ci.
• Pozor! - nepoužívejte operátor řezu ('!') a negaci ('\=', not,...).
• Příklad databáze faktů:
  
  % rodina(Otec,Matka, Seznam deti od nejstarsiho k nejmladsimu)
  rodina(borivoj, anna, [jana, petr, pavel,pavla,vera,marcela,jan]).
  rodina(simon,marcela,[]).
  rodina(pavel,klara,[zdena]).
  rodina(petr,bozena,[tomas]).
  rodina(pavel,bozena,[lukas,david]).
  rodina(tomas,pavla,[marta,dan]).
  rodina(david,marta,[karel,petra]).
  rodina(tomas,marta,[lucie,barbora]).
  
  % muz(X)
  muz(borivoj).
  muz(dan).
  muz(karel).
  muz(tomas).
  muz(lukas).
  muz(david).
  muz(petr).
  muz(pavel).
  muz(jan).
  muz(simon).
  
  % zena(X)
  zena(pavla).
  zena(vera).
  zena(marcela).
  zena(jana).
  zena(anna).
  zena(klara).
  zena(lucie).
  zena(barbora).
  zena(bozena).
  zena(marta).
  zena(petra).
  
  
• Příklady dotazů a správných odpovědí pro naše fakta: (pořadí odpovědí se samozřejmě může lišit)
  ?- bratri(vera,SB).
  SB = [petr, pavel, jan].
  
  ?- bratri(lucie,SB).
  SB = [].
  % nebo
  fail.
  
  ?- bratri(david,SB).
  SB = [lukas].
  % případně SB = [lukas, david].
  
  ?- bratri(Ci,[petr, pavel, jan]).
  Ci = jana ;
  Ci = pavla ;
  Ci = vera ;
  Ci = marcela ;
  % případně i petr, pavel a jan.
  fail.
  
  ?- starsibratr(marcela,B).
  B = petr ;
  B = pavel ;
  fail.
  
  ?- starsibratr(lukas,B).
  fail.
  
  ?- starsibratr(Ci,pavel).
  Ci = pavla ;
  Ci = vera ;
  Ci = marcela ;
  Ci = jan ;
  fail.
  
  ?- mladsisestra(karel,S).
  S = petra ;
  fail.
  
  ?- mladsisestra(Ci,vera).
  Ci = jana ;
  Ci = petr ;
  Ci = pavel ;
  Ci = pavla ;
  fail.
  
  ?- nejmladsisestra(Ci,marta).
  Ci = dan ;
  no
  
  ?- nejmladsisestra(petra,S).
  fail.
  
  ?- nejmladsisestra(Ci,marcela).
  Ci = jana ;
  Ci = petr ;
  Ci = pavel ;
  Ci = pavla ;
  Ci = vera ;
  Ci = jan ;
  fail.
  
  ?- nejstarsibratr(jana,B).
  B = petr ;
  fail.
  
  ?- nejstarsibratr(petr,B).
  B = pavel ;
  fail.
  
  

1. domácí úkol 2.3.2011

• 0) Vyzkoušejte si práci se zvoleným interpretem Prologu, například SWI-Prolog
• 1) Modelování přirozených čísel pomocí termů 0, s(0), s(s(0)),...
• 1a) (za 0.5 bodu) součin Definujte predikát mul(+X,+Y,?Z), tak že Z = X * Y (X,Y,Z jsou přirozená čísla modelovaná pomocí termů). Návod: X * (Y + 1) = (X * Y) + X.
• 2b) (za 0.5 bodu) mocnina Definujte predikát pow(+X,+Y,?Z), tak že Z = X ^ Y (X,Y,Z jsou přirozená čísla modelovaná pomocí termů). Návod: X ^ (Y + 1) = (X ^ Y) * X.
• 1c) (za 0.5 bodu) faktoriál Definujte predikát fact(+X,?F), tak že F = X! (X, F jsou přirozená čísla modelovaná pomocí termů).
• 1d) (za 0.5 bodu) modulo Definujte predikát mod(+X,+Y,?Z), tak že Z = X mod Y (X,Y,Z jsou přirozená čísla modelovaná pomocí termů).
• Při definici predikátů můžete použít predikáty definovné na cvičení: nat(X), add(X,Y,Z), lt(X,Y) aj. (pokud je použijete, pošlete je společně s řešením).
• Pokud narazíte při řešení na problém, se kterým si nebudete vědět rady, napište - poradím vám. Pokud v řešení, které pošlete, budou chyby, nevadí, můžete mi poslat opravu (pokud to stihnete v termínu).
• Na co pozor: aby se výpočet nezacyklil, aby program nevypisoval více stejných odpovědí
• Pro pokročilé: nepoužívejte aritmetické operátory, operátor řezu ('!') a negaci ('\=', not,...).
• Příklady dotazů a správných odpovědí (postupně doplním další :))
  ?- mul(s(s(0)), s(s(0)),X).
  X = s(s(s(s(0)))) ;
  false.
  
  ?- mul(s(s(0)), 0,X) .
  X = 0 ;
  false.
  
  ?- mul(0,s(s(0)),X) .
  X = 0 ;
  false.
  
  ?- pow(s(s(0)),s(s(0)),Z) .
  Z = s(s(s(s(0)))) ;
  false.
  
  ?- pow(0,s(s(0)),Z) .
  Z = 0 ;
  false.
  
  ?- pow(s(s(0)),0,Z) .
  Z = s(0) ;
  false.
  
  ?- fact(s(s(s(0))),F).
  F = s(s(s(s(s(s(0)))))) ;
  false.
  
  ?- fact(s(s(s(s(0)))),F).
  F = s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(0)))))))))))))))))))))))) ;
  false.
  
  ?- mod(s(s(s(s(s(s(s(0))))))),s(s(s(s(0)))),X).
  X = s(s(s(0))) .
  
  ?- mod(s(s(s(s(s(s(s(0))))))), s(s(0)),X).
  X = s(0) .
  
  ?- mod(s(s(s(s(s(s(s(0))))))),0,X).
  false.