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

Přednáška je věnována neprocedurálnímu programování. Většina semestru je věnována programování v jazyku Prolog, ve kterém studenti i ladí zápočtové programy. Informativně se studenti seznámí i s jazykem LISP a neprocedurálními částmi programovacích systémů.
jankasvk
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 31. 5. 2015 13:05
Typ studia: Informatika Bc.

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

Příspěvek od jankasvk »

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.

Kód: Vybrat vš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.)

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))
4. Hrany v hypergrafe
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
Odpovědět

Zpět na „PRG005 Neprocedurální programování“