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

Náhradní domácí úkoly

• POZOR: Termín pro získání zápočtu byl 9. červenec. Zápočtové úlohy ani náhradní úlohy mi tedy už neposílejte, nebudou uznány.
• Studenti, kteří během semestru nezískali za testíky včetně náhradního alespoň 4 body a chtějí ode mě zápočet, mají (poslední) možnost napsat si ještě jednu opravu (testík bude ve tvaru jeden příklad za 1 bod).
• Studenti, kterým chybí za testíky a domácí úlohy více než 12 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ž 12, 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.
• Haskell - matice (úplné řešení je 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 - dynamické programování (úplné řešení je za 1 bod)
• Dokončete řešení úloh s kostičkami a mřížkou, které jsme rozpracovali na cvičení.
• Řešení by mělo být odladěné a doplněné o testovací příklady.
• SCHEME - AVL strom (úplné řešení je 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 (úplné řešení je za 1 bod)
• Definujte predikát nthPerm(+N,?K,?P), kde P je K-tá permutace čísel {1,2,...,N} podle lexikografického uspořádání (P je seznam). Predikát by měl fungovat oběma směry: pro K najít K-tou permutaci, pro permutaci P zjistit, kolikátá je. Časová i prostorová složitost použitého algoritmu by měla být maximálně kvadratická (k-krát nextPerm tedy není akceptovatelné řešení).
• 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ů
• Řešení by mělo být odladěné a doplněné o testovací příklady.

11. domácí úkol 11.5.2010

• Na posledním cvičení nebude standardní testík, ale větší náhradní testík "povinný" pro ty studenty, kteří nebudou mít do posledního cvičení dostatek bodů a chtějí ode mě zápočet. Testík bude mít tři části, každá bude odpovídat jednomu probranému programovacímu jazyku a jednomu běžnému testíku (a bude se tak i bodovat). Za náhradní testík lze tedy získat až 3 body.
• Body za domácí úkoly nad limit 16 se automaticky převádějí na body za testíky (v poměru 2:1). Pro jednoduchost jsou body navíc na těchto stránkách ponechány v původním sloupečku (rozhodující je součet). Každý student smí mezi domácími úlohami a testíky převést maximálně 8 (4) bodů. Zbytek bodů je třeba získat standardně.
• Za domácí úkol je i tentokrát více úloh. Doufám, že příjdou vhod především těm studentům, kteří mají prozatím málo bodů.
• HASKELL a) (za 1,5 bodu) Stromy
• (za 0,25 bodu) 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). 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) 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). 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,75 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ů)
• Příklady dotazů a správných odpovědí :
  > 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
• HASKELL b) (za 2 body) Nekonečné posloupnosti
• Z minula.
• (za 0,25 bodu) Definujte funkci aritm_, která vytvoří nekonečný seznam obsahující aritmetickou posloupnost (ta je definovaná předpisem a_i = a_0 + d * i).
• (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,75 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ří.
• Příklady dotazů a (snad :)) správných odpovědí :
  - odpověď na následující dotazy by měla být okamžitá
  > take 10 (aritm_ 3 (-1) )
  [3,2,1,0,-1,-2,-3,-4,-5,-6]
  > (aritm_ 4 17)!!1000
  17004
  > 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]
• 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í :
  > 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.2010

• Body za domácí úkoly nad limit 16 se automaticky převádějí na body za testíky (v poměru 2:1). Pro jednoduchost jsou body navíc na těchto stránkách ponechány v původním sloupečku (rozhodující je součet). Každý student smí mezi domácími úlohami a testíky převést maximálně 8 (4) bodů. Zbytek bodů je třeba získat standardně.
• Za domácí úkol je tentokrát více úloh. Doufám, že příjdou vhod především těm studentům, kteří mají prozatím málo bodů. Úlohy a),c) jsou do příště, b) stačí za 14 dnů.
• 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
• Stačí za 14 dnů.
• (za 0,25 bodu) Definujte funkci aritm_, která vytvoří nekonečný seznam obsahující aritmetickou posloupnost (ta je definovaná předpisem a_i = a_0 + d * i).
• (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,75 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ří.
• Příklady dotazů a (snad :)) správných odpovědí :
  - odpověď na následující dotazy by měla být okamžitá
  > take 10 (aritm_ 3 (-1) )
  [3,2,1,0,-1,-2,-3,-4,-5,-6]
  > (aritm_ 4 17)!!1000
  17004
  > 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]
• HASKELL c) (za 1,5 bodu) Z minula -- Dělitelé
• (za 0,5 bodu) Definujte funkci del x, která vrátí seznam dělitelů (celého nezáporného) čísla x (např. (del 24)== [1,2,3,4,6,8,12,24]).
• (za 0,5 bodu) Definujte funkci prv n, která testuje, zda n je prvočíslo.
• (za 0,5 bodu) Definujte funkci delmoc x d, která vrátí maximální mocninu čísla d, která dělí x (např. (delmoc 100000 100) == 2).
• Nezapomeňte na (správnou) typovou signaturu!
• Příklady dotazů a správných odpovědí :
  > map (del) [1..5]
  [[1],[1,2],[1,3],[1,2,4],[1,5]]
  > filter prv [1..20]
  [2,3,5,7,11,13,17,19]
  > delmoc 1620 6
  2

9. domácí úkol 27.4.2010

• HASKELL a) (za 1,25 bodu) Na rozjezd
• 0. Nainstalujte si interpret Haskellu a vyzkoušejte si práci v něm.
• (za 0,25 bodu) Definujte funkci soucet s, která spočte součet všech prvků seznamu celých čísel.
• (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 1,5 bodu) Dělitelé
• Stačí za 14 dnů:
• (za 0,5 bodu) Definujte funkci del x, která vrátí seznam dělitelů (celého nezáporného) čísla x (např. (del 24) == [1,2,3,4,6,8,12,24]).
• (za 0,5 bodu) Definujte funkci prv n, která testuje, zda n je prvočíslo.
• (za 0,5 bodu) Definujte funkci delmoc x d, která vrátí maximální mocninu čísla d, která dělí x (např. (delmoc 100000 100) == 2).
• Nezapomeňte na (správnou) typovou signaturu!

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 voda (+Vstup, - Reseni), kde Vstup je tvaru vstup(c(X,Y),Z), a Reseni je seznam stavů z počátečního do koncového (například [s(0,0),...,s(Z,neco)]).
• PROLOG BONUS(za 0,5 bodu) Pokud predikát nalezne nejkratší cestu.
• SCHEME b) (za 1 bod) Třídění
• Základní formy ve SCHEME.
• Interpery pro SCHEME
• 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 zatridS , 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ů).
• SCHEME BONUS c) (za 1,5 bodu)
• (za 0,5 bodu) Na cvičení jsme definovali funkci map pro seznamy. Napište funkci (mapTree t f) , 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.
• (za 0,5 bodu) Na cvičení jsme definovali funkci app pro seznamy. Napište funkci (appTree t f g) , která je analogií funkce app, ale na vstupu má na místo seznamu binární strom. Funkce appTree aplikuje funkci g (s jedním parametrem) na listy stromu (listy stromu jsou prázdné stromy) a funkci 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").
• (za 0,5 bodu) Napište dvě z následujících funkcí za využití appTree 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).
• 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))
• Bonusové body se dají opět převést na aktivitu.

7. domácí úkol 6.4.2010

• Do 14 dnů (ale nejlépe do týdne) byste si měli vybrat téma zápočtového programu - náčrt možných témat. Poté, co se na tématu dohodneme, mi pošlete stručnou specifikaci programu (podrobnější zadání - obvykle bude stačit jeden odstavec). Termín na odeslání specifikace je 26.duben.
• Tento (7.) domácí úkol stačí odevzdat za 14 dnů, tj. před cvičením 20.4.2010.
• 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.
• a) (za 1,5 bodu) Binární halda
  Binární haldu lze reprezentovat různě (jako strom, v poli,...). V binární haldě jsou uložena přirozená čísla 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. O(log n)
• insert(+Halda,+Prvek,-Halda1) - Halda1 vznikne přidáním Prvku do Haldy. O(log n)
• postav(+Pole,-Halda) - Z Pole přirozených čísel postaví haldu. Lze řešit postupným vkládáním prvků. 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. O (n log n)
• b) BONUS (za 2 body) Prostorový (závěsný) mobil
• 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). Bonusové domácí úlohy lze také převést na body za aktivitu (v poměru 1:1).
• 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) - 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) - Mobil je bezpečný, pokud při libovolné rotaci ramen nemůže dojít ke srážce.
• (za 0,5 bodu) ekvivalentní(+MobilA,+MobilB) - MobilA mohu získat z MobiluB vhodným otáčením ramen.

6. domácí úkol 30.3.2010

• Pokud naleznete nějaké nejasnosti v zadání nebo vzorových příkladech, dejte mi co nejdříve vědět, informace sem doplním.
• a) (za 0,75 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, :).
  
  Například:
  ?- vyhodnot((-false)*(true+false),[],H).
  H = true.
  ?- vyhodnot((-x)*(x+(y+false)),[x:false,y:true,z:true],H)
  H = true.
  
  Inspirovat se můžete z přednáškových slajdů (např. Dvořák, 24.3.2010). Je tam i povídání o operátorech (pokud někdo nechodíte na přednášky a chcete se dozvědět více).
  
  Trocha nápovědy:
  %pro negaci (pro ostatní operace lze obdobně)
  ...
  vyhodnot(true,_,true).
  vyhodnot(false,_,false).
  ...
  vyhodnot(-B,S,V):- vyhodnot(B,S,V1), negace(V1,V).
  ...
  % negace - definice výčtem: (pro ostatní spojky lze provést obdobně)
  negace(true, false).
  negace(false, true).
  
  % pro tento fragment řešení by již mělo fungovat:
  ?- vyhodnot(-false,[],H).
  H = true;
  
  ?- vyhodnot(-(-false),[],H).
  H = false;
  
  Pokud uvažujeme i proměnné, je třeba kromě jednotlivých operací ošetřit i substituci true a false za příslušnou proměnnou.
  
• b) (za 0,75 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 čísel 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 (v případě kartézského součinu). Uspořádání prvků v případě kartézského součinu je myšleno "lexikograficky": [1,1]<[1,2]<[2,1].
  Rada Původní množiny jsou uspořádané a bez duplicit. Operace pro sjednocení, průnik, atd. lze tedy jednoduše a efektivně implementovat tak, aby tuto vlastnost zachovávaly, a není pak třeba výslednou množinu třídit.
  
  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 dotazů a (snad :) ) správných odpovědí :
  ?- 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 23.3.2010

• a) (za 0,5 bodu) Na vstupu máme dvě matice A a B. Definujte predikát vynasob(+A,+B,-M), který implementuje násobení matic. Matice jsou reprezentovany jako seznamy řádků. Predikát by měl odpovědět no (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).
• b) (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)).
• c) (za 1 bod) + BONUS (za 1 bod)
• Tato úloha má čtyři podúlohy, stačí, pokud pošlete řešení pro libovolné dvě z nich. Zbylé dvě ú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). Bonusové domácí úlohy lze také převést na body za aktivitu (v poměru 1:1).
• Permutaci množiny n přirozených čísel {1,2,...,n} lze zadat různými způsoby:
• jako seznam obrazů, např. P = [3,2,1,4]
• jako seznam cyklů, zde C = [[1,3],[2],[4]]
• jako vektor inverzí, zde I = [0,1,2,0]. 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:
• c1) (0,5 bodu) perminv (+P,-I), který k dané permutaci (zadané jako seznam obrazů) určí příslušný vektor inverzí,
• c2) (0,5 bodu) invperm (+I,-P), který k danému vektoru inverzí určí příslušnou permutaci,
• c3) (0,5 bodu) permcyk (+P,-C), který k dané permutaci (zadané jako seznam obrazů) určí příslušný seznam cyklů,
• c4) (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á).
• Konvence (pro c3): pro jednodušší kontrolu by měl každý cyklus začínat nejmenším prvkem a cykly by měly být seřazeny podle prvního prvku. U standardního řešení vzniká tato varianta "sama od sebe", není třeba nic třídit ani cyklicky otáčet. Nicméně pokud použijete řešení, co bude řadit cykly nebo prvky v cyklech jinak, pokuste se řešení převést na standardní variantu.
• 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).
  no
  
  ?- 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]]
  
  ?- 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] ;
  
  

4. domácí úkol 16.3.2010

• a) (za 1 bod) Na vstupu máme seznam S. Definujte predikát 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)]] se nahrazením získá seznam [1,2,3,4,5,muz(jan)].
• b) (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.
• c) BONUS (za 0,75 bodu)
• Tuto úlohu nemusíte řešit, pokud ale máte za první tři domácí úlohy méně než 6 bodů a pošlete správné řešení, můžete si nahradit část ztracených bodů (do výše maximálně 6).
• Na vstupu máme matici M. Definujte predikát pecka(+M,?Pecka,?Slupka), ketrý matici M rozdělí na "vnitřek" (Pecka) a "obal" (Slupka). "Vnitřek" matice je matice zbavená prvního a posledního řádku a sloupce. Slupka je matice M, kde je "vnitřek" vyplněn nulami. Lze nalézt elegantní řešení.
• Pozor hlavně na krajní případy, jako jsou prázdný seznam a "malé" matice.
• Příklady dotazů a správných odpovědí:
  ?- 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 = []
  
  ?- 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]
  
  ?- pecka([[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1],[1, 1, 1, 1, 1, 1],[1, 1, 1, 1, 1, 1],[1, 1, 1, 1, 1, 1]],[[1, 1, 1, 1],[1, 1, 1, 1],[1, 1, 1, 1]], [[1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1]]).
  true.
  
  ?- pecka([[3, 0, 4, 2, 1, 0], [1, 3, 2, 0, 1, 1], [4, 4, 5, 5, 3, 3]], Pecka, Slupka).
  Pecka = [3, 2, 0, 1], Slupka = [[3, 0, 4, 2, 1, 0], [1, 0, 0, 0, 0, 1], [4, 4, 5, 5, 3, 3]]
  
  ?- pecka([[3, 3, 4, 2, 1, 0], [1, 3, 2, 5, 1, 1]], Pecka, Slupka).
  Pecka = [], Slupka = [[3, 3, 4, 2, 1, 0], [1, 3, 2, 5, 1, 1]]
  
  

3. domácí úkol 9.3.2010

• Pokračování příkladu ze cvičení - viz. predikát prostredni/2 řešený trikem. Bez použití aritmetiky (predikát is) definujte následující predikáty:
• a) (za 0.25 bodu) napoloviny(+S,-T1,-T2), seznam S je zřetězením seznamů T1 a T2, přičemž počet prvků v T1 a v T2 se liší nejvýše o 1
• b) (za 0.5 bodu) natretiny(+S,-T1,-T2,-T3), seznam S je zřetězením seznamů T1, T2 a T3, přičemž počet prvků v libovolných dvou ze seznamů T1, T2 a T3 se liší nejvýše o 1
• c) (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ží)
• d) (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ží)
• Pro zadání c) a d) uvažujeme seznamy pouze osob (mužů a žen), muži jsou definovaní pomocí predikátu muz/1, ženy pomocí predikátu zena/1.
• Řešení často není jednoznačné (pokud počet prvků seznamu není dělitelný dvěma/třemi). V tom případě stačí, když procedura vrátí jednu variantu.
• Pozor na krajní případy - prázdný či jednoprvkový seznam, seznam jen žen (u c),d)) apod. Také pozor na to, že prvky se MOHOU v seznamu opakovat.
• e) BONUS (až za 1 bod navíc) predikáty napoloviny1/3, polovinymuzu1/3, napsané tak, aby mohly být použity i v dotazech typu napoloviny1(+,+,+),polovinymuzu1(+,+,+) a rozpoznaly právě všechna správná řešení. Při volání napoloviny1(+,-,-), polovinymuzu1(+,-,-) by predikáty měly 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í. U napoloviny1/3 budou maximálně dvě správné varianty. U polovinymuzu1/3 může být variant více (záleží na ženách uprostřed seznamu (a případně na prostředním muži), do které poloviny padnou).
• Ilustracni příklad pro bonusovou úlohu:
  muz(m).
  zena(z).
  
  ?-polovinymuzu1([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.
  
• 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).
  
  % zena(X)
  zena(pavla).
  zena(verka).
  zena(petra).
  zena(marta).
  zena(klara).
  zena(zdena).
  zena(hanka).
  
  
• Příklady dotazů a správných odpovědí (nicméně často je správně více variant)
  ?- napoloviny([a,b,c,d,e,f],A,B).
  A = [a,b,c] ,
  B = [d,e,f] ;
  no
  
  ?- napoloviny([a,b,c,d,e,f,g,h,i],A,B).
  A = [a,b,c,d,e] ,
  B = [f,g,h,i] ;
  no
  % alternativní správné řešení: A = [a,b,c,d] , B = [e,f,g,h,i] ;
  
  ?- napoloviny([a],A,B).
  A = [a] ,
  B = [] ;
  no
  % alternativní správné řešení: A = [] , B = [a] ;
  
  ?- napoloviny([a,a],A,B).
  A = [a] ,
  B = [a] ;
  no
  
  ?- natretiny([a,b,c,d,e,f],A,B,C).
  A = [a,b] ,
  B = [c,d] ,
  C = [e,f] ;
  no
  
  ?- natretiny([a,b,c,d,e,f,g],A,B,C).
  A = [a,b,c] ,
  B = [d,e] ,
  C = [f,g] ;
  no
  % alternativní správné řešení: A = [a,b] , B = [c,d,e], C = [f,g] nebo A = [a,b] , B = [c,d], C = [e,f,g]
  
  ?- 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] ;
  no
  
  ?- polovinymuzu([pavla,karel,verka,petra,tomas,zdena],A,B).
  A = [pavla,karel] ,
  B = [verka,petra,tomas,zdena] ;
  no
  % 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]
  
  ?- 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] ;
  no
  % 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] ;
  no
  % i zde je více správných řešení
  

2. domácí úkol 2.3.2010

• a) Modelování přirozených čísel pomocí termů 0, s(0), s(s(0)),...
• a1) (za 0.5 bodu) Definujte predikát mod(+X,+Y,?Z), tak že Z = X mod Y (X,Y,Z jsou přirozená čísla modelovaná pomocí termů)
• a2) (za 0.25 bodu) Definujte predikát fact(+X,?F), tak že F = X! (X, F jsou přirozená čísla modelovaná pomocí termů)
• Rada - při definici predikátů můžete použít predikáty definovné na cvičení: natural(X), add(X,Y,Z), mul(X,Y,Z) aj.
• Důrazné doporučení - nepoužívejte operátor řezu ('!') a negaci ('\=', not,...).
• Příklady dotazů a správných odpovědí
  ?- 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.
  
  ?- fact(s(s(s(0))),F).
  F = s(s(s(s(s(s(0)))))) ;
  no
  
  ?- 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)))))))))))))))))))))))) ;
  no
  
  


• b) 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).
• b1) (za 0.25 bodu) Definujte predikát mladsisestra(?Ci,?MladsiSestra).
• b2) (za 0.25 bodu) Definujte predikát starsibratr(?Ci,?StarsiBratr).
• b3) (za 0.5 bodu) Definujte predikát nejmladsisestra(?Ci,?NejmladsiSestra).
• b4) (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.
• Důrazné doporučení - 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,[verka,dan]).
  rodina(david,verka,[karel,petra]).
  
  % 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(zdena).
  zena(bozena).
  zena(verka).
  zena(petra).
  
  
• Příklady dotazů a správných odpovědí pro naše fakta: (pořadí odpovědí se může lišit)
  ?- starsibratr(marcela,B).
  B = petr ;
  B = pavel ;
  no
  
  ?- starsibratr(lukas,B).
  no
  
  ?- starsibratr(Ci,pavel).
  Ci = pavla ;
  Ci = vera ;
  Ci = marcela ;
  Ci = jan ;
  no
  
  ?- mladsisestra(karel,S).
  S = petra ;
  no
  
  ?- mladsisestra(Ci,vera).
  Ci = jana ;
  Ci = petr ;
  Ci = pavel ;
  Ci = pavla ;
  no
  
  ?- nejmladsisestra(Ci,verka).
  Ci = dan ;
  no
  
  ?- nejmladsisestra(petra,S).
  no
  
  ?- nejmladsisestra(Ci,marcela).
  Ci = jana ;
  Ci = petr ;
  Ci = pavel ;
  Ci = pavla ;
  Ci = vera ;
  Ci = jan ;
  no
  
  ?- nejstarsibratr(jana,B).
  B = petr ;
  no
  
  ?- nejstarsibratr(petr,B).
  B = pavel ;
  no
  
  

1. domácí úkol 23.2.2010

• 0) Vyzkoušejte si práci se zvoleným interpretem Prologu, například SWI-Prolog
• 1) Pokračování příkladu ze cvičení - modelování přirozených čísel pomocí termů 0, s(0), s(s(0)),...
  natural(0). % nula je přirozené číslo
  natural(s(X)) :- natural(X). % n+1 je přirozené číslo, je-li n přirozené číslo
  
• a) (za 0.5 bodu) Definujte predikát even(?X), který rozhodne, zda X je sudé přirozené číslo (modelované pomocí termů)
• b) (za 0.5 bodu) Definujte predikát odd(?X), který rozhodne, zda X je liché přirozené číslo (modelované pomocí termů)
• c) (za 0.5 bodu) Definujte predikát leq(+X,+Y), který rozhodne, zda X je menší nebo rovné Y (X a Y jsou přirozená čísla modelovaná pomocí termů)
• d) (za 0.5 bodu) Definujte predikát lt(+X,+Y), který rozhodne, zda X je menší než Y (X a Y jsou přirozená čísla modelovaná pomocí termů)
• Konvence: Znak '+' u argumentu značí, že je "vstupní" (v dotazech bude jako tento argument vždy specifikovaný term), '-' značí "výstupní" (v dotazech bude jako tento argument vždy proměnná),'?' značí, že v dotazu může být na daném místě proměnná i specifikovaný term.
• Rada - při definici procedur můžete použít predikát natural(X) definovný na cvičení, nebo využít podobný princip. Všechny procedury by měly odpovědět "false" (resp. "no"), pokud některý z argumentů není číslo (např. leq(pepik,anicka).).
• Příklady dotazů a správných odpovědí
  ?- even(0).
  true.
  
  ?- even(s(0)).
  false.
  
  ?- even(s(s(s(s(0))))).
  true.
  
  ?- even(pepik).% neni cislo
  false.
  
  ?- even(s(s(s(s(pepik))))). % neni cislo
  false.
  
  ?- even(X).
  X=0;
  X=s(s(0));
  X=s(s(s(s(0)))).
  
  ?- odd(0).
  false.
  
  ?- odd(s(0)).
  true.
  
  ?- odd(s(s(s(s(s(0)))))).
  true.
  
  ?- odd(pepik).% neni cislo
  false.
  
  ?- odd(X).
  X=s(0);
  X=s(s(s(0)));
  X=s(s(s(s(s(0))))).
  
  ?- leq(0,0).
  true.
  
  ?- leq(0,pepik). % neni cislo
  false.
  
  ?- leq(s(0),s(s(pepik))). % neni cislo
  false.
  
  ?- leq(pepik,s(s(0))). % neni cislo
  false.
  
  ?- leq(s(0),0).
  false.
  
  ?- leq(s(0),s(0)).
  true.
  
  ?- lt(0,0).
  false.
  
  ?- lt(s(0),0).
  false.
  
  ?- lt(0,s(s(0))).
  true.