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
1 (10b)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
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).
(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ě
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é.
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)]
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']
(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?