Zkouška 26.6.2018

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ů.
host

Zkouška 26.6.2018

Příspěvek od host »

PROLOG
1. Definujte predikát frekv/2, který

obdrží seznam konstant
a vrátí frekvence dvojic za sebou jdoucích konstant
Výstupní reprezentaci si zvolte a popište pro vzorový vstup.

Příklad:

?- frekv([a,b,a,b,c], P).
P = [f(a-b,2),f(b-a,1)f(b-c,1)]

2. Je dán orientovaný acyklický graf (DAG) o n vrcholech pomocí seznamu sousedů. Procedura dfs/2 projde graf do hloubky a přidá k vrcholům časy otevření a uzavření v rozsahu od 1 do 2n. Na pořadí vrcholů na výstupu nezáleží:

definujte predikát dfs/2
napište konkrétní výstup vašeho programu na vzorovém grafu z příkladu níže.
Příklad:

?- dfs([c-[d], a-[b,c], b-[d,e], d-[], e-[]], V).
V = [v(a,1,10,[b,c]), v(c,2,5,[d]), v(d,3,4,[]), v(b,6,9,[e]), v(e,7,8,[])]

HASKELL
3. Je daný seznam prvků, který vzniknul průchodem binárního vyhledávacího stromu (BVS) v pořadí preorder. První prvek je kořen, ten určuje díky uspořádání jednoznačně rozdělení prvků do levého a pravého podstromu a následně je celý strom jednoznačně určen.

a) Napište definici typu BVS a pro stromy s vnitřními prvky typu a.

b) Napište definici funkce reBVS :: Ord a => [a] -> BVS a.

4. Definujte funkci change3, která

obdrží seznam, který reprezentuje abecedu povolených prvků, které lze využít k modifikaci
obdrží seznam xs pro modifikaci
vrátí seznam všech modifikací vstupního seznamu xs, které se od něho liší v právě 3 prvcích.
Příklad: (podtržené prvky jsou změněny)

> change3 ”ab” ”aabe”

[”bbae”, ”bbba”, ”bbbb”, ”baaa”, ”baab”, ”abaa”, ”abab”]

a) Definujte typ funkce change co nejobecněji (včetně případných typových tříd):

b) Definujte funkci change:
Odpovědět

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