# Zkouška 19. 9. 2016 (Dvořák, Hric)

<{ForumPost(poster="jankasvk", timestamp=2016-09-19 19:00:20)}>
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 $e^1 = e$.  
Rád prvku a je 3, pretože $a^1 = a, a^2 = a a = b, a^3 = a (a a) = a b = e$.  
Rád prvku b je 3, pretože $b^1 = b, b^2 = a, a^3 = b a = e$.  

    rady([[e, a, b], [a, b, e], [b, e, a]], V).
    V = [e-1, a-3, b-3].
    

**2.Trojuholníky v grafe**  
Nájdite všetky trojuholníky v neorientovanom grafe. Každý trojuholník práve raz.  
(Bolo zakázané použiť findall a pod.)

    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

    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))
    

**4. Hrany v hypergrafe**  
Viz: [http://forum.matfyz.info/viewtopic.php?f=169&t=8851](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
<{/ForumPost}>