od jankasvk » 19. 9. 2016 19:00
Zadania boli dlhé a tak len zhrniem podstatu...
Bolo explicitne zakázané používať bagof, setof, findall.
Prolog
1. Multiplikatívna grupa
Na vstupe dostanete tabuľku násobenia v grupe, Úlohou je vrátiť rád všetkých prvkov. V prvom riadku na prvom mieste sa nachádza jednotkový prvok
e. Prvý riadok tvorí teda hlavičku celej tabuľky.
Príklad:
[
[e, a, b],
[a, b, e],
[b, e, a]
]
Rád prvku e je 1, pretože
.
Rád prvku a je 3, pretože
 = a b = e)
.
Rád prvku b je 3, pretože
.
Kód: Vybrat vše
rady([[e, a, b], [a, b, e], [b, e, a]], V).
V = [e-1, a-3, b-3].
Nájdite všetky trojuholníky v neorientovanom grafe. Každý trojuholník práve raz.
(Bolo zakázané použiť findall a pod.)
Kód: Vybrat vše
troj([a-[b,c,d], b-[a,c], c-[a, b, d], d-[a,c]], T).
T = [t(a,b,c), t(a,c,d)].
Haskell
3.Rekonštrukcia BVS
Máme zadaný zoznam vrcholov zoradený v
preorder poradí pr prechádzaní z koreňa. Spätne z neho zostavte BVS.
Vopred zadané:
data BTree a = Void | Node (BTree a) a (BTree a)
rekonstrukce :: Ord a => [a] -> BTree a
Kód: Vybrat vše
rekonstrukce [5,4,3,9,7,10] = Node (Node (Node Void 3 Void) 4 Void) 5 (Node (Node Void 7 Void) 9 (Node Void 10 Void))
Viz:
http://forum.matfyz.info/viewtopic.php?f=169&t=8851, no nebola zadaná signatúra
dopleni.
Veľký príklad
Rozložte graf na čo najmenší počet ciest a cyklov (hranovo disjunktných). Úloha má polynomiálne riešenie.
Situácia:
Dvaja odišli ešte pred veľkým príkladom, že prvou časťou neprejdú.
Osobne som mala z prvej časti všetko dobre, no v druhej som zvolila zlý algoritmus (nesprávne riešene), ktoré som z časti implementovala. Pán Hric ho so mnou prešiel a dal mi dvojku za zároveň správne zapísanie toho, čo som chcela a súčasne nesprávny algoritmus
Zadania boli dlhé a tak len zhrniem podstatu...
Bolo explicitne zakázané používať bagof, setof, findall.
Prolog
[b]1. Multiplikatívna grupa[/b]
Na vstupe dostanete tabuľku násobenia v grupe, Úlohou je vrátiť rád všetkých prvkov. V prvom riadku na prvom mieste sa nachádza jednotkový prvok [i]e[/i]. Prvý riadok tvorí teda hlavičku celej tabuľky.
Príklad:
[
[b][e, a, b][/b],
[a, b, e],
[b, e, a]
]
Rád prvku e je 1, pretože [latex]e^1 = e[/latex].
Rád prvku a je 3, pretože [latex]a^1 = a, a^2 = a a = b, a^3 = a (a a) = a b = e[/latex].
Rád prvku b je 3, pretože [latex]b^1 = b, b^2 = a, a^3 = b a = e[/latex].
[code]
rady([[e, a, b], [a, b, e], [b, e, a]], V).
V = [e-1, a-3, b-3].
[/code]
[b]2.Trojuholníky v grafe[/b]
Nájdite všetky trojuholníky v neorientovanom grafe. Každý trojuholník práve raz.
(Bolo zakázané použiť findall a pod.)
[code]
troj([a-[b,c,d], b-[a,c], c-[a, b, d], d-[a,c]], T).
T = [t(a,b,c), t(a,c,d)].
[/code]
Haskell
[b]3.Rekonštrukcia BVS[/b]
Máme zadaný zoznam vrcholov zoradený v [i]preorder[/i] poradí pr prechádzaní z koreňa. Spätne z neho zostavte BVS.
Vopred zadané:
data BTree a = Void | Node (BTree a) a (BTree a)
rekonstrukce :: Ord a => [a] -> BTree a
[code]
rekonstrukce [5,4,3,9,7,10] = Node (Node (Node Void 3 Void) 4 Void) 5 (Node (Node Void 7 Void) 9 (Node Void 10 Void))
[/code]
[b]4. Hrany v hypergrafe[/b]
Viz: [url]http://forum.matfyz.info/viewtopic.php?f=169&t=8851[/url], no nebola zadaná signatúra [i]dopleni[/i].
Veľký príklad
Rozložte graf na čo najmenší počet ciest a cyklov (hranovo disjunktných). Úloha má polynomiálne riešenie.
Situácia:
Dvaja odišli ešte pred veľkým príkladom, že prvou časťou neprejdú.
Osobne som mala z prvej časti všetko dobre, no v druhej som zvolila zlý algoritmus (nesprávne riešene), ktoré som z časti implementovala. Pán Hric ho so mnou prešiel a dal mi dvojku za zároveň správne zapísanie toho, čo som chcela a súčasne nesprávny algoritmus