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ů.

Zkouška 16. 7. 2020

Příspěvekod blablabla777 » 16. 7. 2020 21:15

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

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

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron