# Zkouška 26.6.2018

<{ForumPost(poster="host", timestamp=2018-06-26 15:24:03)}>
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:
<{/ForumPost}>