Zkouška 16. 7. 2020

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ů.
blablabla777
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 27. 5. 2019 20:55
Typ studia: Informatika Bc.

Zkouška 16. 7. 2020

Příspěvek od blablabla777 »

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:

Kód: Vybrat vše

   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ů.
  2. Definujte predikát allTrees/2.
  3. Stručně vysvětlete, proč je vaše definice korektní.
  4. 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.

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
  1. Definujte predikát bip/3.
  2. 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:

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
  1. Definujte typovou signaturu funkce ascending.
  2. Definujte vlastní funkci.
  3. Jak byste zobecnili tuto funkci tak, aby ji bylo možné použít s libovolným porovnávacím operátorem?
  4. 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.
  2. 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.
  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.
  4. 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.
Odpovědět

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