Zkoužka 4.9.2020

rewert · Příspěvek od **rewert** » 4. 9. 2020 20:27

Podmínky stejné jako u předchozích zkoušek tento rok:

Čas: 2:15 + při vysvětlování zadání ~ 20 min
povinná ustní část: prochází se řešení
nepovinná ustní část: podle domluvy (na vylepšení 2 a 3)

Hodnocení písemky:
každá úloha je ohodnocena 10 body

aspoň 35b : výborně
aspoň 27b : velmi dobře
aspoň 19b & aspoň 5b z Prologu & aspoň 5b z Haskellu: dobře
jinak : neúspěch

Zadání písemky
1. Prolog: Topologické uspořádání grafu (3 podotázky)
Je dán orientovaný graf G pomocí seznamů sousedů. Zjistěte, jestli lze graf G topologicky uspořádat a pokud ano, vydejte seznam vrcholů v topologickém pořadí.

Příklad:

Kód: Vybrat vše

?- topo([a-[],b-[a,c],c-[a],d-[a,c]],Usp).
Usp=[b,d,c,a]

(a) Definujte příslušný predikát topo/2 v jazyce Prolog.
(b) Odhadněte časovou složitost vašeho řešení. Odhad zdůvodněte.
(c) Jsou některé z vašich predikátů koncově rekurzivní ? Pokud ano, vysvětlete, které to jsou, a jaký to má význam. Pokud ne, vysvětlete, zdali by se dal některý takto upravit.

2. Prolog: Diskrepanční vrstvy (3 podotázky)
Napište predikát diskr/2, který dostane binární strom (s konstruktory t/3 a nil/0) a vrátí seznam seznamů vrcholů stromu, kde v jednom vnitřním seznamu jsou všechny vrcholy, ke kterým se při průchodu od kořene dostaneme se stejným počtem kroků doprava. Vnější seznam je od nejlevější vrstvy, na pořadí ve vnitřních seznamech nezáleží.

Příklad:

Kód: Vybrat vše

?- diskr(t( t(t(nil,a,nil),b,t(nil,c,nil)),
            d,
            t(t(nil,e,t(nil,f,nil)),
              g,
              t(nil,h,t(nil,i,nil)) )), V).
V = [[a,b,d],[c,g,e],[f,h],[i]]

(a) Definujte příslušný predikát diskr/2.
(b) Je ve vašem řešení použit řez (!) nebo negace? Pokud ano, změní se něco, když řez / negaci vypustíme? Pokud ne, dal by se řez / negace někde smysluplně využít?
(c) Lze u predikátu diskr/2 obrátit směr výpočtu? Podrobněji: dle příkladu předpokládáme volání diskr(+,-). Bude fungovat i volání diskr(-, +), tj. zadáme seznam diskrepančních vrstev, a na výstupu obdržíme strom? Vysvětlete.

3. Haskell: Největší součet souvislé podposloupnosti (4 podotázky)

a) Pro zadanou posloupnost čísel najděte spojitý úsek, jehož součet je největší. Vydejte souřadnice začátku a konce úseku a dosažený součet.

Kód: Vybrat vše

soucty :: Num a => [a] → (Int, Int, a)

Pokuste se o nějakou optimalizaci, tj. nepočítejte součty hrubou silou (zcela samostatně).

Příklad: (indexováno od 0)

Kód: Vybrat vše

> soucty [-1,1,2,3,-4]
 (1,3,6)

b) Jaký význam má část 'Num a =>' v definici funkce soucty ? Proč tam musí být?
c) Uveďte dvě možné konkrétní hodnoty proměnné a z typu funkce soucty.
d) Lze definovat 'Num a' taky pro uživatelské typy nebo musíme použít pouze předdefinované/vestavěné? Lze naši funkci soucty použít pro nějaký uživatelský typ na místě a ? (Proč ano/ne?)

4. Haskell: Rekonstrukce binárního stromu (3 podotázky)

Binární vyhledávací strom je zadán jako seznam hodnot vrcholů v pořadí preorder. Definujte funkci

Kód: Vybrat vše

readBt :: Ord a => [a] -> Bt a

která ze zadaného seznamu zrekonstruuje původní strom typu

Kód: Vybrat vše

data Bt a = Void
          | Node (Bt a) a (Bt a)

Připomeňme, že v binárním vyhledávacím stromu platí pro každý vrchol v, že všechny hodnoty v levém, resp. pravém podstromu v jsou menší, resp. větší nežli hodnota v. Odtud plyne, že původní strom je zadaným seznamem určen jednoznačně.

Příklad:

Kód: Vybrat vše

> readBt [5, 2, 4, 9]
Node (Node Void 2 (Node Void 4 Void)) 5 (Node Void 9 Void)

(a) Definujte funkci readBt.
(b) Je ve vašem řešení použita nějaká funkce vyššího řádu (funkce s funkcionálními argumenty)? Pokud ne, dala by se zde nějaká smysluplně použít?
(c) Je ve vašem řešení použita notace stručných seznamů (list comprehension), tj. [... | ...] ? Pokud ne, dala by se zde smysluplně použít?