Zkouška 24.6.2019 (Dvořák, Hric)

1. Prolog: Generování výrokových formulí (5 bodů)
   Formule výrokového počtu jsou sestavené z (výrokových) proměnných ve funktoru var/1 a logických spojek negace, konjunkce a disjunkce (bez konstant). Dále máte dány v argumentech predikátu gen/3 číslo k pro velikost formule a seznam jmen proměnných. Generujte backtrackingem všechny logické formule (každou jednou), které obsahují proměnné ze seznamu a ve kterých je počet spojek a výskytů proměnných dohromady právě k.

Definujte predikát gen(+K, +Jmena, -Fle). Na pořadí generovaných formulí nezáleží, ale měli byste vygenerovat každou právě jednou. K řešení není potřeba predikát =../2 (univ).

Příklad:

?- gen(4,[p],F).

F = not(not(not(var(p))));
F = not(and(var(p),var(p)));
F = not(or(var(p),var(p)));
F = and(not(var(p)),var(p));
F = and(var(p),not(var(p)));
F = or(not(var(p)),var(p));
F = or(var(p),not(var(p)));
false.

1. Prolog: Koncepty (5 bodů)
   Jeden objekt je zadán uspořádaným seznamem dvojic klíč-hodnota. Na vstupu máte seznam objektů. Napište proceduru koncept/2, která vyrobí nejmenší koncept zahrnující všechny vstupní objekty. Koncept je seznam dvojic klíč-seznam_hodnot. Koncept zahrnuje objekt, pokud koncept má všechny klíče objektu a v seznamu hodnot příslušného klíče u konceptu je obsažena hodnota klíče u objektu. Pokud objekt nějaký klíč konceptu nemá, bude v seznamu hodnot konceptu hodnota nedef.

Příklad:

?- koncept([ [barva-modra, motor-diesel, pocet_kol-6], [barva-bila, motor-plyn, pocet_mist-40], [motor-elektro, pocet_mist-5] ], Koncept).

Koncept = [barva-[modra,bila,nedef], motor-[diesel,plyn,elektro], pocet_kol-[6,nedef], pocet_mist-[40,5,nedef]]

1. Haskell: Kumulativní součty (5 bodů)
   Je dána číselná matice A. Definujte funkci

kumulace :: Num a => [[a]] -> [[a]]

která z matice A vyrobí matici B stejných rozměrů (viz příklad níže)

každý prvek na souřadnicích (i,j) bude roven součtu všech hodnot  
v submatici s levým horním rohem (0,0)  
a pravým dolním rohem (i,j)   

Poznámka: Snažte se vyhnout opakování stejných výpočtů.

Příklad:

kumulace[[1,1,1],[1,2,1],[0,1,0],[1,1,-4]]
[[1,2,3],[2,5,7],[2,6,8],[3,8,6]]

1. Haskell: Doplnění hypergrafu (5 bodů)
   Hypergraf je zadán množinou vrcholů a množinou hyperhran, což jsou alespoň dvouprvkové podmnožiny množiny vrcholů. Naší cílem je definovat funkci doplnění, která doplní do hypergrafu H všechny dvouprvkové (hyper)hrany pro ty dvojice vrcholů, které nejsou společně obsaženy v žádné hyperhraně vstupního hypergrafu H. Funkce tedy např. z hypergrafu

   • s vrcholy {1,2,3,4,5} a hyperhranani {1,3,5} a {2,3,4}

   • vytvoří hypergraf se stejnými vrcholy a hyperhranami {1,3,5},{2,3,4},{1,2},{1,4},{5,2} a {5,4}

(a) Definujte datový typ pro reprezentaci hypergrafu. Pokuste se o co nejobecnější definici (vrcholy mohou být reprezentovány nejen čísly, ale i znaky, řetězci apod.)

(b) Specifikujte typovou signaturu funkce

doplneni ::

(c) Funkci definujte.{: style="list-style-type:decimal"}

Velký příklad:

Klastrování pro detektor (Prolog/Haskell)

Data z detektoru jsou dlouhý seznam událostí z jednotlivých senzorů, které jsou uspořádány ve čtvercové mřížce. Jedna částice zasáhne i víc senzorů. Každý zasažený senzor pošle svojí polohu (v mřížce), energii částice a čas příletu. Máte spojit do klastrů informace o jedné částici. Klastr je co největší, ale spojitý (4-souvislost, po hranách mřížky) a všechny časy příletů se liší nejvýš o Delta. Problém je, že data přicházejí zpožděny až o Z, Z > Delta, ale víte, že senzor nepošle dvě události během doby Z. Několik částic může přiletět současně a následně data z klastrů jsou na vstupu promíchána.

Napište funkci/proceduru klastry, která dostane na vstup Delta, Z a seznam událostí jako čtveřic (i,j, energie, čas). Na výstup posíláte seznam klastrů, kde každý klastr je seznam událostí.

Skvělý, díky za big one.

Dnes jsem byl na ústní zkoušce u Dvořáka, byl moc hodný :D.

Letmo jsme projeli velký příklad — zajímala ho nějaká myšlenka odevzdaného kódu. Pak jsme se hlavně věnovali malým příkladům. Probíhalo to formou příjemné diskuse ohledně odevzdaného řešení. Diskutovali se možná zlepšení, chyby, ale i dobře vyřešené příklady, kde poukazoval na kusy kódu, které se mu líbili.

Celkově mi připadá důležité se na odevzdaná řešení před ústní zkouškou podívat a zjistit, co opravdu funguje a co ne. Pokud to nefunguje, tak si najít chybu, případně zjistit, kolik úprav je třeba udělat, aby se dané řešení zfunkčnilo. Může vám to hodně pomoci.

Počítejte s tím, že se vás může zeptat i na nějakou doplňující otázku, mě se zeptal na rozdíl mezi type, newtype a data v Haskellu. Vyplatí se umět i různé seznamoviny (hlavně věci kolem rozdílových seznamů). Pokud byste chtěli lepší známku, než na jakou dle vašeho výkonu v písemné části máte, tak můžete počítat s tím, že dostanete něco opravit/naprogramovat na papír.

Přidávám ještě moje řešení malých příkladů.

1. Prolog: Generování výrokových formulí (5 bodů)

   gen(1, Jmena, var(J)) :- !, member(J, Jmena). gen(2, Jmena, not(P)) :- !, gen(1, Jmena, P). gen(N, Jmena, V) :- N > 2, B is N-2, C is N-1, between(1,B,X), D is C - X, gen(X, Jmena, P), gen(D, Jmena, F), ( V = and(F,P) ; V = or(F,P) ).

   gen(N, Jmena, not(E)) :- N > 2, A is N-1, gen(A, Jmena, E).

2. Prolog: Koncepty (5 bodů)

   vstup(V) :- V = [ [barva-modra,motor-diesel, pocet_kol-6], [motor-plyn,pocet_mist-40, barva-modra], [motor-elektro,pocet_mist-5] ].

   foldr(_, [], Acc, Acc) :- !. foldr(Binary, [X | Xs], Acc, Y) :- foldr(Binary, Xs, Acc, Z), call(Binary, X, Z, Y).

   foldl(_, [], Y, Y) :- !. foldl(Binary, [X | Xs], Acc, Y) :- call(Binary, X, Acc, NewAcc), foldl(Binary, Xs, NewAcc, Y).

   filter(_, [], []) :- !. filter(Pred, [X | Xs], [X | Ys]) :- call(Pred, X), !, filter(Pred, Xs, Ys).

   filter(Pred, [_ | Xs], Ys) :- filter(Pred, Xs, Ys).

   unique([],[]). unique([X | Xs], [X | Ys]) :- filter(notUnifiable(X), Xs, Z), unique(Z, Ys).

   notUnifiable(X, Y) :- X = Y.

   fst(H, Y) :- H=..[_, Y, _].

   map(_, [], []) :- !. map(Unary, [X | Xs], [Y | Ys]) :- call(Unary, X, Y), map(Unary, Xs, Ys).

   koncept2nazvy(O, N) :- map(fst, O, N).

   pridejNazvy(O, Acc, NewAcc) :- koncept2nazvy(O, N), append(Acc, N, NewAcc).

   koncepty2nazvy(Os, Ns) :- foldl(pridejNazvy, Os, [], Nd), unique(Nd, Ns).

   vyndej(Name, A-_, Acc, Acc) :- Name = A, !. vyndej(Name, Name-B, Acc, [B | Acc]).

   getAttributeValue(O, Name, Value) :- foldl(vyndej(Name),O,[], Values), length(Values, L), (L == 1 -> Values = [Value] ; (L == 0 -> Value = nedef ;

    %else
        fail
    )
    ).
   

   p(Name, O, Acc, [Value|Acc]) :- getAttributeValue(O, Name, Value), !. p(_, _, Acc, Acc).

   getAttributeValues(Os, Name, Values) :- foldr(p(Name),Os, [], Values).

   dvojce(Objekty, Nazev, Nazev-Hodnoty) :- getAttributeValues(Objekty, Nazev, Vals), unique(Vals, Hodnoty).

   koncept(V, Y) :- koncepty2nazvy(V, Ns), map(dvojce(V),Ns,Y).

3. Haskell: Kumulativní součty (5 bodů)

   safehead :: [[a]] -> [a] safehead xs | null xs = [] | otherwise = head xs

   kumulace :: Num a => [[a]] -> [[a]] kumulace m = reverse $ foldl (\km r -> kumulaceRadku (safehead km) r : km) [] m

   kumulaceRadku :: Num a => [a] -> [a] -> [a] kumulaceRadku [] r = scanl1 (+) r kumulaceRadku kr r = foldr ((a,b,c,d) acc -> a+b+c-d : acc) [] xs where xs = zip4 kr r

   zip4 :: Num a => [a] -> [a] -> [(a,a,a,a)] zip4 kr r = zip4' kr r (0:kr) 0 where zip4' :: Num a => [a] -> [a] -> [a] -> a -> [(a,a,a,a)] zip4' _ [] _ _ = [] zip4' (a : kr) (b : r) (c : kr1) d = (b,d,a,c) : zip4' kr r kr1 (b+d+a-c)

4. Haskell: Doplnění hypergrafu (5 bodů)

   data Hypergraf a = Hypergraf [a] [[a]] deriving Show

   testHypergraf = Hypergraf [1,2,3,4,5] [[1,3,5], [2,3,4]]

   prvek :: Eq a => [a] -> [[a]] -> Bool prvek _ [] = False prvek x (y : ys) = jePrvek || jeObracenePrvek || prvek x ys where jePrvek = x == y jeObracenePrvek = reverse x == y

   difference :: Eq a => [[a]] -> [[a]] -> [[a]] difference xs ys = foldr (\x a -> if prvek x a then a else if not $ prvek x ys then (x : a) else a ) [] xs

   doplneni :: Eq a => Hypergraf a -> Hypergraf a doplneni (Hypergraf xs ys) = Hypergraf xs (ys ++ hranyPridat) where vsechnyMozneHrany = kombinace 2 xs hranyUvnitr = foldr (\hhrana ak -> ak ++ kombinace 2 hhrana) [] ys hranyPridat = difference vsechnyMozneHrany hranyUvnitr

   kombinace :: (Eq a, Integral b) => b -> [a] -> [[a]] kombinace 0 _ = [[]] kombinace _ [] = [] kombinace n (x : xs) | n > 0 = kombinace n xs ++ map (x:) (kombinace (n-1) xs)

{: style="list-style-type:decimal"}