# Zkouška 16. 7. 2020

<{ForumPost(poster="blablabla777", timestamp=2020-07-16 22:15:11)}>
Písemná část 2:15 (nejprve bylo ústní vysvětlení úloh). Ústní část v průběhu následujícího týdne.  
  
**1. Prolog: Generování binárních stromů**  
  
Cílem úlohy je definovat predikát allTrees, který pro daný seznam hladin vygeneruje všechny možné binární stromy.  

* Hladinou rozumíme seznam prvků, které se nacházejí ve stejné hloubce
* Můžete předpokládat, že každá hladina má nanejvýš dvojnásobek prvků předchozí hladiny (ale může jich mít méně).
* Hladiny vygenerovaného stromu musejí odpovídat hladinám specifikovaných ve vstupním seznamu.

Např. pro seznam \[\[1],\[2,3],\[4]] dostaneme následující 4 stromy:  

       1
     2   3
    4
    
       1
     2   3
      4
    
       1
     2   3
        4
    
       1
     2   3
          4
    

1. Popište zvolenou reprezentaci binárních stromů.
1. Definujte predikát allTrees/2.
1. Stručně vysvětlete, proč je vaše definice korektní.
1. Lze vaší definici použít opačným směrem? Tj. nalezne váš predikát seznam hladin pokud specifikujete pouze výsledný strom? Vysvětlete.

**2. Prolog: Bipartitní rozklad grafu**  
  
Je zadán neorientovaný graf G a množina vrcholů M. Zjistěte, zda M a doplněk M tvoří bipartitní rozklad grafu G (tj. každá hrana grafu má právě jeden koncový vrchol v množině M). Pokud ano, vydejte druhou množinu rozkladu.  

    ?- bip([a-[c,d], b-[d], c-[a], d-[a,b]], [a,b], D).
        D = [c,d]
    
    ?- bip([a-[c,d], b-[d], c-[a], d-[a,b]], [b,c], D).
        false
    

1. Definujte predikát bip/3.
1. Napište o jednotlivých predikátech ve vašem řešení, zda jsou koncově rekurzivní.

**3. Haskell: Rostoucí posloupnosti**  
  
Cílem je definovat funkci ascending, která na vstupu obdrží seznam hodnot (libovolného typu) a vrátí zpět seznam posloupností, který splňuje:  

* každá posloupnost je striktně rostoucí a nelze ji zleva ani zprava prodloužit
* sloučením všech posloupností dostaneme vstupní seznam

Příklad:  

    ghci> ascending [1,2,3,4,3,2,1,2]
    [[1,2,3,4],[3],[2],[1,2]]
    
    ghci> let x = [1,2,3,1,2,3] in concat (ascending x) == x
    True
    

1. Definujte typovou signaturu funkce ascending.
1. Definujte vlastní funkci.
1. Jak byste zobecnili tuto funkci tak, aby ji bylo možné použít s libovolným porovnávacím operátorem?
1. Bude vaše definice fungovat i na nekonečných seznamech? Pokud ano, vysvětlete proč. Pokud ne, dala by se vaše definice takto upravit? Zdůvodněte proč.

**4. Haskell: Stromové operace**  

1. Definujte datový typ pro binární stromy.  

    * Hodnoty jsou uloženy ve vnitřních uzlech.
    * Pokuste se o co nejobecnější definici.
    * Nezapomeňte na reprezentaci prázdného stromu.
1. Definujte funkci replicateT. Výsledkem replicateT n a je binární strom, který obsahuje n kopií hodnoty a.  

    * Výsledný strom by měl mít minimální možnou hloubku. Např. strom replicateT 7 a by měl mít hloubku 3.
1. Definujte funkci zipWithT jako zobecnění funkce zipWith. zipWithT f t1 t2 sloučí prvky stromů t1 a t2 na stejných pozicích pomocí funkce f.  

    * Pokud nemá nějaký prvek z jednoho stromu odpovídající prvek na stejné pozici v druhém stromě, tak jej do výsledného stromu nepřidávejte. Např. pro prázdný strom empty by mělo platit zipWithT f t empty == empty a zipWithT f empty t == empty.
1. Pomocí replicateT a zipWithT definujte funkci cut. cut n t odstraní ze stromu t všechny vrcholy, jejichž hloubka je ostře větší než n.

<{/ForumPost}>