Zkouška 12. 6. 2020 (Dvořák, Hric)

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ů.
Sejsel
Matfyz(ák|ačka) level I
Příspěvky: 6
Registrován: 28. 1. 2017 14:24
Typ studia: Informatika Bc.

Zkouška 12. 6. 2020 (Dvořák, Hric)

Příspěvek od Sejsel »

Zkouška probíhala nestandardně vzdáleně. Programovalo se na vlastních počítačích, odevzdávalo se do Moodlu. Všichni se připojili na Zoom, prošlo se společně zadání a byly odpovězeny otázky k zadání. Kvůli nejasnostem byla dokonce jedna část první otázky (1e) změněna na volitelnou. Bylo povoleno používat slidy, popřípadě jiný obsah z Moodlu, naopak různé hledání po internetu ne. Po víkendu následovala ústní část, v průběhu víkendu se v Moodlu objevily nějaké komentáře a body, které ještě pak byly upraveny. Prišlo mi to mírně hodnocené, úlohy jsem neměl nijak dokonale (v případě úlohy 2 jsem ji neměl skoro vůbec), ale i tak jsem dostal hodně bodů. Podmínky a zadání úloh následují. V příloze je seznam povolených predikátů a funkcí.
Moodle, podmínky zkoušky píše: (a) část písemná
zadání i odevzdání prostřednictvím Moodle UK
můžete používat překladače obou jazyků
budou zadány 4 problémy, dva z logického (Prolog) a dva z funkcionálního (Haskell) programování
součástí zadání bude seznam standardních predikátů / funkcí (probraných na přednášce), které můžete použít, aniž byste je explicitně definovali
samozřejmě můžete využít i jiné knihovní predikáty / funkce, ovšem součástí vašeho řešení by pak měla být jejich definice
během zkoušky můžete nahlížet i do slajdů z přednášek (k dispozici na Moodle)
naopak není povoleno snažit se řešení "vygooglovat", hledat pomoc na diskuzních fórech či využívat asistence další osoby
délka 2h 15min

(b) část ústní sestává z části povinné a volitelné
povinná část: cca 15-20min diskuze na vaší (opravenou a obodovanou) písemkou, měli byste být schopni vaše řešení vysvětlit / obhájit, v závěru navrhneme hodnocení
hodnocení 4 : neúspěch, je třeba, abyste se znovu podívali na obsah předmětu a přihlásili se na další termín
hodnocení 1: zkouška končí, lepší známku nabídnout nemůžeme
hodnocení 2 nebo 3: dle vaší volby zde buď zkouška končí, nebo se můžete přhlásit na volitelnou část ústní zkoušky, kde si můžete známku zlepšit
volitelná část: cca 30-45min, řešení dalších problémů, zodpovězení otázek z obsahu předmětu
poznámka: zde si můžete hodnocení samozřejmě i zhoršit: bylo by velmi nespravedlivé, kdybychom tuto možnost vyloučili, jakkoliv ji nepovažujeme ża přiliš pravděpodobnou
Moodle, podmínky písemné části píše: U všech úloh můžete předpokládat, že vstup je zadán korektně.
Můžete používat standardní predikáty jazyka Prolog a standardní funkce jazyka Haskell z přiloženého seznamu.
Další pomocné predikáty / funkce je třeba explicitně definovat.

V Prologu prosím nepoužívejte predikáty typu assert a retract či bagof, setof a findall.

Můžete využívat překladače Prologu i Haskellu.
Můžete nahlížet do slajdů z přednášek (či nahrávek) na těchto stránkách.
Žádná další asistence (google, diskuzní fóra, pomoc další osoby) není povolena.

Hodnocení:
každá úloha je ohodnocena 10 body
aspoň 35b : výborně
aspoň 27b : velmi dobře
aspoň 19b & aspoň 5 b z Prologu & aspoň 5b z Haskellu: velmi dobře
jinak : neúspěch

Čas: 2h 15 min
1 (10b)

Profesor Hammerstein definoval predikat setrid/2 takto:

Kód: Vybrat vše

% 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 za uvedené pravidlo 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) Doplňte jednu (opravdu jen jednu) chybějící klauzuli před uvedené pravidlo 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í.
(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) VOLITELNE: Lze u procedury setrid/2 obrátit směr výpočtu?

Kód: Vybrat vše

% 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?

2 (10b)

Do země Mobilia, v níž je každý občan vybaven chytrým telefonem, přicestoval Cestovatel, nakažený virovým onemocněním. Všichni ostatní byli přitom ještě zdraví.
Můžeme předpokládat, že virus se přenese z jedné osoby na druhou, pokud spolu strávili ve vzdálenosti menší než 2m alespoň čas K, kde K ja známá kritická hodnota.
Díky chytrým telefonům máme pro každého občana Mobilie seznam záznamů jeho kontaktů, kde každý takový záznam pro osobu A obsahuje

identifikaci osoby B, která se k němu přiblížila do vzdálenosti < 2m
čas setkání
a délku setkání

Cílem je sestavit program, který na základě takových záznamů vrátí seznam infikovaných osob.

(a) V jazyce Prolog popište datovou strukturu pro reprezentaci jednoho záznamu kontaktu občana Mobilie popsaného výše.
(b) V jazyce Prolog navrhněte reprezentaci položek VstupníhoSeznamu, přičemž každá položka bude obsahovat indentifikaci občana Mobilie a seznam záznamů jeho kontaktů.
(c) Sestavte predikát inf/4, který obdrží
VstupníSeznam
identifikaci Cestovatele
kritickou hodnotu K
a vrátí seznam infikovaných

U každého pomocného predikátu prosím v poznámce popište jeho význam.

Volitelné: výstupní seznam můžete uspořádat dle délky kontaktu s infikovanými do nerostoucí posloupnosti.

(d) Odhadněte časovou složitost vašeho řešení.
(e) Je některý z vašich predikátů koncově rekurzivní ? Pokud ano, vysvětlete, jaký to má význam. Pokud ne , dal by se některý takto upravit?

3 (10b)

Rozdělte zadaný binární vyhledávací strom T na n+1 binárních vyhledávacích stromů T0, ... , Tn

podle zadaných vstupních hodnot ki , 1 ≤ i ≤ n
tak, že ve stromě Ti jsou hodnoty x, ki ≤ x < ki+1, pokud jsou nerovnosti aplikovatelné.

Obrázek

Snažte se o efektivitu, celé podstromy patřící do jednoho pruhu zpracujte najednou.

(a) Definujte datový typ pro reprezentaci binárních vyhledávacích stromů. Snažte se o co nejobecnější definici.
(b) Definujte typovou signaturu funkce pruhy, včetně typových tříd.
(c) Funkci pruhy definujte. Budete-li používat pomocné funkce, u každé popište její význam.
(d) Pokuste se stručně zdůvodnit korektnost vaší defnice.

4 (10b)

Definujte funkce rle a rld, které realizují run-length encoding a decoding. Funkce

Kód: Vybrat vše

rle :: Eq a => [a] -> [Either a (a,Int)]
zakóduje co nejdelší úseky stejných prvků ve vstupním seznamu do dvojice (prvek, počet) typu Either s datovým konstruktorem Right.
Pokud je prvek v úseku sám, kóduje se pouze prvek vnořený do typu Either s datovým konstruktorem Left.

Příklad:

Kód: Vybrat vše

> rle ”abbcccda” 
[Left 'a', Right ('b',2), Right ('c',3), Left 'd', Left 'a']
(a) Definujte funkci rle s využitím rekurze, ale bez použití stručných seznamů či funkcí vyšších řádů (funkce s funkcionálními parametry).
(b) Definujte funkci rle bez explicitního využití rekurze, ale za použití stručných seznamů či funkcí vyšších řádů.
(c) Definujte typovou signaturu funkce rld, která realizuje dekompresi, tj. převod ze seznamu úseků na původní seznam prvků.
(d) Definujte funkci rld. Použijte přitom funkci map či concat.
(e) Bude některá z funkcí fungovat i na nekonečných seznamech? Proč ano nebo proč ne?
Přílohy
PredikatyaFunkce.pdf
Seznam povolených predikátů a funkcí
(97.98 KiB) Staženo 289 x
Odpovědět

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