Zkouška 24. 6. 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ů.
blablabla777
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 27. 5. 2019 20:55
Typ studia: Informatika Bc.

Zkouška 24. 6. 2020

Příspěvek od blablabla777 »

Písemná část 2:15 (nejprve bylo ústní vysvětlení úloh)

Prolog 1 - Problém truhláře

Truhlář má dostatek trámů délky D a seznam Xs délek trámů, které potřebuje nařezat. V seznamu Xs se délky mohou opakovat.

Cílem problému je sestavit predikát rezy(+D,+Xs, -N, -Vss), který
  • rozdělí požadované délky do skupin, které se mají nařezat z jednoho trámu
  • truhlář přitom používá hladový algoritmus, tj. pro každou délku použije první trám, z něhož lze ještě požadovanou délku odřezat
  • vrátí celkový počet řezaných trámů N
  • a seznam seznamů Vss (délky N), jehož každý prvek reprezentuje dělení jednoho trámu (případný zbytek se neuvádí).
Příklad:

Kód: Vybrat vše

rezy(5,[3,2,2,2,2,1,4], N, V).
N=4, V=[[3,2],[2,2,1],[2],[4]]
  1. Definujte predikát rezy/4. Definice případných pomocných predikátů prosím opatřete vysvětlujícím komentářem.
  2. Je některý z vašich predikátů koncově rekurzivní? Pokud ano, vysvětlete, který to je a jaký to má význam.
  3. Pokud ne, dal by se některý takto upravit? Odpověď prosím zdůvodněte.[/*]
Prolog 2 - Systém různých reprezentantů

Je zadán seznam množin Mss. Chceme všemi možnými způsoby vybrat a vrátit v seznamu reprezentanty daných množin v odpovídajícím pořadí s podmínkou, že konkrétní reprezentanti v jednom výběru jsou různí.

Příklad:

Kód: Vybrat vše

reprezentanti([[1],[1,2,3],[1,3,4]], R).
R = [[1,2,3],[1,2,4],[1,3,4]]
  1. Sestavte predikát reprezentanti(+Mss, -Rss).
  2. Stručně vysvětlete, proč je vaše definice korektní.
  3. Je ve vašem programu použit řez (!) ? Jde o řez červený (mění deklarativní význam programu) či zelený (nemění d.v.)? Pokud ne, je řez nezbytný pro definici některého vestavěného predikátu / operátoru, který jste ve vašem řešení použili? Jde o řez červený (mění deklarativní význam programu) či zelený (nemění d.v.)?
Haskell 1 - Klouzavé průměry

Cílem je definovat binární funkci klouzave, která
  • obdrží na vstupu posloupnost čísel a přirozené číslo n
  • a vrátí posloupnost klouzavých průměrů řádu n, tj. aritmetických průměrů n sousedních prvků.
Příklad:

Kód: Vybrat vše

klouzave [1.5, 2.5, 3.5, 4.5, 5.5] 3
[2.5,3.5,4.5]
  1. Definujte typovou signaturu funkce klouzave
  2. Definujte vlastní funkci s explicitním využitím rekurze
  3. Sestavte alternativní definici, tentokráte bez explicitního použití rekurze, přitom můžete využívat libovolné knihovní funkce z přiloženého seznamu.
  4. Vyhýbá se alespoň jedna z vašich definic opakovaným výpočtům? Pokud ne, dala by se takto upravit? Zdůvodněte.
  5. Bude některá z vašich definic fungovat i na nekonečných seznamech? Pokud ano, vysvětlete proč. Pokud ne, dala by se některá z vašich definic takto upravit? Zdůvodněte.

Kód: Vybrat vše

take 5 $ klouzave [1..] 10
[5.5,6.5,7.5,8.5,9.5]
Haskell 2

Cílem toho problému je zobecnit funkce foldr / foldl na obecné kořenové stromy.
  1. Definujte datový typ pro reprezentaci obecných kořenových stromů s ohodnocenými vrcholy:
    • snažte se o co nejobecnější definici
    • nezapomeňte na reprezentaci prázdného stromu
  2. Funkce foldl a foldr zobecněte na funkci fold, která bude - namísto seznamu - procházet stromem ve vaší reprezentaci popsané v (a).
  3. Pomocí funkce fold definujte funkci arita, která vrátí aritu (tj. maximální počet dětí přes všechny vrcholy) zadaného kořenového stromu.
  4. Pomocí funkce fold definujte funkci pdc, která vrátí průměrnou délku cesty z kořene do listu (tj. součet délek všech cest z kořene do listu / počet listů).
Odpovědět

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