Zkouška 19. 9. 2022

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ů.
MájaH
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 30. 1. 2020 20:14
Typ studia: Informatika Bc.

Zkouška 19. 9. 2022

Příspěvek od MájaH »

1. Prolog (POVINNÁ): Transformace obecného kořenového stromu.

Na vstupu jen zadán obecný (ne nutně binární) kořenový strom, jehož vrcholy jsou ohodnoceny (ne nutně různými) přirozenými čísly. Cílem této úlohy je sestavit predikát trans/2, který k zadanému vstupnímu stromu T sestrojí strom téhož tvaru jako T, v němž bylo ohodnocení každého vrcholu nahrazeno aritmetickým průměrem všech ohodnocení, které se v T vyskytují.

Důležité: Plné bodové ohodnocení bude uděleno jen řešení, které

použije pouze jediný (rekurzivní) průchod stromem T.

(a) Navrhněte reprezentaci obecného kořenového stromu. Svůj návrh ilustrujte na jednoduchém příkladě.

(b) Sestavte definici predikátu trans/2.

(c) Je vaše definice predikátu trans/2 koncově rekurzivní?

Pokud ano, vysvětlete proč, a k čemu je koncové rekurze užitečná.
Pokud ne, dala by se definice přeformulovat tak, aby podmínky koncové rekurze splňovala? Odpověď zdůvodněně.




2. Prolog (VOLITELNÁ): Třídění seznamu.

Profesor Hammerstein definoval predikat setrid/2 takto:

% setrid(+Xs,-Ys) :- Ys je seznam přirozených čísel ze seznamu Xs setříděný vzestupně.
setrid(Xs,Ys) :- append(A,[H1,H2|B],Xs), H1 > H2, !, append(A,[H2,H1|B],Xs1), setrid(Xs1,Ys).

zapomněl však na klauzuli, která definuje bázi rekurze.

(a) Doplňte jednu (opravdu jen jednu) chybějící klauzuli tak, aby výsledná procedura korektně setřídila vstupní seznam přirozených čísel.
Na výstupu bychom měli obdržet jen jediné řešení.

(b) Pokud jste doplnili klauzuli na konec, lze místo toho (nějakou jinou) klauzuli doplnit na začátek tak aby program fungoval? Naopak, pokud jste doplnili klauzuli na začátek, lze místo toho (nějakou jinou) klauzuli doplnit na konec tak aby program fungoval? Vysvětlete.

(c) V definici pravidla je použit řez (!). Jde o zelený (nemění deklarativní význam) či červený řez (mění d.v.) ? Vysvětlete!
Obsahuje některá z vašich klauzulí, (doplněná v (a) nebo (b)) zelený či červený řez?

(d) Jaký známý třídící algoritmus výše uvedený kód implementuje? Pokud neznáte název, můžete alespoň slovně popsat, jak setrid/2 funguje.

(e) Lze u procedury setrid/2 obrátit směr výpočtu?

% setrid(-Xs,+Ys) :- Xs je seznam přirozených čísel ze seznamu Ys setříděný vzestupně

Pokud ne, šel by kód jednoduše upravit tak, aby se výsledný predikát (pojmenovaný třeba setrid2/2) dal korektně volat oběma způsoby?






3. Haskell (POVINNÁ) : Násobení polynomů.

Cílem tohoto problému je definovat funkci pro násobení řídkých polynomů.

(a) Definujte datový typ pro reprezentaci řídkých polynomů, tj. polynomů, u nichž je většina koeficientů nulových.
Snažte se o

efektivní reprezentaci
co největší obecnost (např. možnost jak celočíselných, tak reálných koeficientů, komplexní čísla uvažovat nemusíte)
stupně budou samozřejmě vyjádřeny přirozenými čísly

Důležité:

nezapomeňte na reprezentaci nulového polynomu
budete-li ve vaší reprezentaci předpokládat nějaké uspořádání, uveďte to prosím do poznámky

(b) Definujte typovou signaturu funkce pro násobení takto popsaných řídkých polynomů.

(c) Sestavte definici funkce pro násobení. Budete-li definovat pomocné funkce, opatřete prosím každou definici komentářem, v němž vysvětlíte, co příslušná funkce počítá.

(d) Lze ve vaší reprezentaci definovat nekonečný polynom? Pokud ano, jeden takový (zcela libovolný) definujte.

(e) Bude vaše funkce z (c) fungovat i v případě, kdy aspoň jeden z činitelů je nekonečný polynom? Odpověď prosím zdůvodněte.





4. Haskell (VOLITELNÁ) : Shoda v okně

Cílem tohoto problému je najít podobné úseky (okna) ve dvou zadaných řetězcích.

Na vstupu jsou dva konečné Stringy a dvě čísla: k pro délku okna a l jako parametr podobnosti. Úlohou je zjistit, zda existují v daných řetězcích podobné souvislé úseky (přesně) délky k (tzv. okna) a pokud ano, vydat některou jejich polohu. Okna jsou podobná, pokud aspoň na l místech mají shodné znaky.

(a) Definujte funkci najdiOkna typu String -> String -> Int -> Int -> Maybe (Int,Int) , která bude řešit popsanou úlohu. Výstup je Nothing, pokud podobná okna neexistují.

(b) Pokud existuje víc podobných oken, kterou dvojici vydá váš program?

(c) Chceme abstrahovat od konkrétní podobnosti dvou oken. Napište typ funkce vyššího řádu najdiOknaAbs, která bude parametrizována funkcí pro podobnost dvou oken, bude mít stejné vstupy a výstup kromě parametru l. Napište definici najdiOkna s využitím nové funkce.

Příklad: (0-indexované výstupy)

Mějme řetězce "abcdefgh" "asadcfcht".

Pro (k,l)=(4,2) jsou možné výstupy (0,0),(0,2),(2,2),(3,3),(4,4).
Pro l=3 úloha nemá řešení.
Pro (k,l)=(5,3) je jediné řešení (3,3).
Odpovědět

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