26.7.2021 - Zkouška

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ů.
spidoosho
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 27. 5. 2019 19:36
Typ studia: Informatika Bc.

26.7.2021 - Zkouška

Příspěvek od spidoosho »

Zkouška přes Zoom na 2:30 hodiny. Zkoušející krásně vysvětlí zadání a ptá se, jestli všichni všemu rozumí a potom začíná odpočet.
==================================================================================================================
1. Prolog: Generátor seznamů (10 bodů)

Cílem úlohy je definovat predikát gen(-Xs,+N), který

obdrží přirozené číslo N
a postupně vrátí všechny korektně utvořené termy, které jsou tvořeny právě N do sebe různě vnořenými seznamy.
Každý seznam uvedeného typu bychom měli na výstupu obdržet právě jednou, na pořadí odpovědí nezáleží.

Příklad:

?- gen(Xs,4).
Xs = [[[[]]]] ;
Xs = [[[], []]] ;
Xs = [[], [[]]] ;
Xs = [[], [], []] ;
Xs = [[[]], []] ;
false.

(a) Definujte predikát gen/2. Vaše definice by měla sestávat z nejvýše tří klauzulí.

(b) Pomocí predikátu gen/2 definujte nový predikát gen(-Xs), který postupně vrátí všechny seznamy, které obsahují jen jiné seznamy (každý takový seznam by měl být na výstupu právě jednou).

Příklad:

?- gen(Xs).
Xs = [] ;
Xs = [[]] ;
Xs = [[[]]] ;
Xs = [[], []] ;
Xs = [[[[]]]] ;
Xs = [[[], []]] ;
atd ...

(c) Lze vaši definici predikátu gen/1 použít opačným směrem? Jinak řečeno, bude fungovat volání typu gen(+Xs), kdy na vstupu zadáme term Xs a očekáváme odpověď true / false podle toho, zdali jde / nejde o seznam obsahujícící pouze seznamy? Proč ano nebo proč ne?

(d) Je některý z predikátů ve vašem řešení nedeterministický? A je v tomto případě nedeterminismus užitečný? Vyskytuje se v něm i predikát, který je deterministický? Vysvětlete.
==================================================================================================================
2. Prolog: Pohled z okna (10 bodů)

V této úloze budeme pracovat s okny na pracovní ploše počítače. Každé takové okno lze pro naše účely reprezentovat obdélníkem v rovině, jehož strany jsou rovnoběžné se souřadnými osami. Na vstupu je zadán seznam takových obdélníků a další obdélník, nazývaný pohledové okno, stejného druhu. Definujte predikát

okno(+SeznamObdelnikuNaPloše, +PohledovéOkno, -SeznamOřezanýchObdelniku),

který obdrží popsaný vstup a vrátí seznam obdélníků "ořezaných" do pohledového okna, tj.

pokud je obdélník celý v pohledovém okně, bude zachován,
pokud je celý mimo, bude vynechán,
pokud je zčásti mimo, bude zmenšen na tu část, která je v pohledovém okně.
(a) Popište, jak budete v jazyce Prolog reprezentovat jeden obdélník výše uvedeného typu. Snažte se o úspornou reprezentaci: např. popsat takový obdélník souřadnicemi všech čtyř jeho vrcholů je zbytečně redundantní.

(b) Sestavte definici predikátu okno/3.

(c) Je ve vašem řešení nějaký koncově rekurzivní predikát? A naopak, vyskytuje se v něm nějaký predikát, který není koncově rekurzivní? Vysvětlete.
==================================================================================================================
3. Haskell: Čísla s různými číslicemi (10 bodů)

V této úloze budeme pracovat s přirozenými čísly (včetně nuly), v jejichž dekadickém zápisu jsou cifry po dvou různé; pracovně je můžeme nazývat čísla různociferná.

Představme si uspořádání všech různociferných čísel podle velikosti a uvažme dvě funkce:

funkce poradi obdrží různociferné číslo a vrátí jeho pořadí v tomto uspořádání
> poradi 102
92
funkce gen obdrží pořadí a vrátí příslušné různociferné číslo
> gen 92
102
Cílem této úlohy je implementovat JEDNU z uvedených funkcí (můžete si zvolit, kterou), ovšem bez toho, že bychom různociferná čísla systematicky generovali (takový algoritmus by pracoval v exponenciálním čase).

(a) Definujte typovou signaturu funkce, kterou budete implementovat. Pro identifikaci nekorektního vstupu (číslo se stejnými ciframi v prvním či číslo, které není pořadím žádného různociferného čísla ve druhé případě) využijte datový typ Maybe nebo Either.

(b) Zvolenou funkci implementujte. Mělo by jít o efektivní postup, tj. vyhněte se systematickému generování všech různociferných čísel (takové řešení by bylo penalizováno velmi výraznou bodovou redukcí).

(c) Zdůvodněte korektnost vašeho řešení: buďto formou podrobných komentářů v kódu v části (b) (což doporučujeme), nebo explicitním vysvětlením uvedeným v části (c).
==================================================================================================================
4. Haskell: Řídké polynomy (10 bodů)

V této úloze budeme pracovat s řídkými polynomy, tj. polynomy, u nichž je většina koeficientů nulových.

(a) Definujte datový typ pro reprezentaci řídkých polynomů. Snažte se o

efektivní reprezentaci
co největší obecnost (možnost různých typů koeficientů, typový polymorfismus).
Nezapomeňte na reprezentaci nulového polynomu. Budete-li potřebovat nějaké uspořádání prvků, specifikujte to v komentáři k vaší definici.

(b) Definujte typovou signaturu funkce pro násobení takto popsaných řídkých polynomů. Je v tomto případě možné, uvést v definici typový parametr, který by mohl nabývat hodnot alespoň dvou různých datových typů? Pokud ano, udělejte to, pokud to naopak není možné či vhodné, vysvětlete proč.

(c) Sestavte funkci pro násobení řídkých polynomů. Budete-li potřebovat 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) Využijte váš datový typ z části (a) pro definici nekonečného polynomu

p(x)=1+x3+x6+x9+…
Odpovědět

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