Zkoužka 4.9.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 4.9.2020

Příspěvekod rewert » 4. 9. 2020 19: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?
rewert
Matfyz(ák|ačka) level I
 
Příspěvky: 1
Registrován: 13. 1. 2019 12:50
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