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.
Kód: Vybrat vše
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.
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.
Kód: Vybrat vše
?- 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í.
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
Kód: Vybrat vše
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č.
- 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.