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
Popište zvolenou reprezentaci binárních stromů.
Definujte predikát allTrees/2.
Stručně vysvětlete, proč je vaše definice korektní.
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.{: style="list-style-type:lower-alpha"}
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
Definujte predikát bip/3.
Napište o jednotlivých predikátech ve vašem řešení, zda jsou koncově rekurzivní.{: style="list-style-type:lower-alpha"}
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
Definujte typovou signaturu funkce ascending.
Definujte vlastní funkci.
Jak byste zobecnili tuto funkci tak, aby ji bylo možné použít s libovolným porovnávacím operátorem?
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č.{: style="list-style-type:lower-alpha"}
4. Haskell: Stromové operace
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.
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.
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.
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.{: style="list-style-type:lower-alpha"}