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:
rezy(5,[3,2,2,2,2,1,4], N, V). N=4, V=[[3,2],[2,2,1],[2],[4]]
Definujte predikát rezy/4. Definice případných pomocných predikátů prosím opatřete vysvětlujícím komentářem.
Je některý z vašich predikátů koncově rekurzivní? Pokud ano, vysvětlete, který to je a jaký to má význam.{: style="list-style-type:lower-alpha"}
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:
reprezentanti([[1],[1,2,3],[1,3,4]], R). R = [[1,2,3],[1,2,4],[1,3,4]]
Sestavte predikát reprezentanti(+Mss, -Rss).
Stručně vysvětlete, proč je vaše definice korektní.
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.)?{: style="list-style-type:lower-alpha"}
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:
klouzave [1.5, 2.5, 3.5, 4.5, 5.5] 3 [2.5,3.5,4.5]
Definujte typovou signaturu funkce klouzave
Definujte vlastní funkci s explicitním využitím rekurze
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.
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.
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.{: style="list-style-type:lower-alpha"}
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.
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
Funkce foldl a foldr zobecněte na funkci fold, která bude - namísto seznamu - procházet stromem ve vaší reprezentaci popsané v (a).
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.
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ů).{: style="list-style-type:lower-alpha"}