Zkouska 20.9.2017

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ů.
didllicek
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 20. 9. 2017 21:15
Typ studia: Informatika Bc.

Zkouska 20.9.2017

Příspěvek od didllicek »

1.Definujte predikát dif/2, který obdrží seznam S, a vrátí seznam všech seznamů, které obdržíte z S vypuštěním nejvýše 2 prvků. Pořadí prvků ve výstupních seznamech se nemění.
Příklad:
?- dif([a,b,c],D).
D=[[a,b,c], [b,c], [a,c], [a,b], [a], , [c]]

2.Je zadán neorientovaný graf G a jeden jeho vrchol v. Definujte predikát pokryti/3, který postupně vrátí všechna vrcholová pokrytí grafu G, která obsahují vrchol v a jsou minimální vzhledem k inkluzi.
Množina vrcholů V grafu je vrcholovým pokrytím, pokud každá hrana má alespoň jeden vrchol v množině V.
(a) Na příkladě popište, jakou reprezentaci grafu budete používat.
(b) Definujte predikát
pokryti(+Graf, +Vrchol, -VPokrytí)
kde Graf je zadán v reprezentaci popsané v (a).

3.Funkce podminky/2 dostává seznam podmínek jedné proměnné a seznam hodnot. Vydává seznam seznamů hodnot, kde i-tý seznam na výstupu obsahuje hodnoty, pro které byla splněna i-tá podmínka a nebyly splněny předchozí podmínky. Hodnoty, pro které nebyla splněna žádná podmínka, se zahodí.
Příklad:
> podminky [even,(>5),(==3)] [0..9]
[[0,2,4,6,8],[7,9],[3]]
a) Napište typovou signaturu funkce podmínky (co nejobecnější, včetně případných typových tříd).
b) Napište funkci podminky.

4.Cílem tohoto problému je zobecnit standardní funkci take na funkci takeTree, která
-obdrží obecný kořenový strom a dvě přirozená čísla n a m
-odstraní ve stromě všechny vrcholy ve hloubce větší než m (hloubka vrcholu v je počet hran na cestě z kořene do v)
-pro každý vrchol, který má více než n dětí, odstraní všechny děti (s příslušnými podstromy) kromě n nejlevějších
-a výsledný (nejvýše n-ární) strom (hloubky nejvýše m) vrátí.
(a) Definujte datový typ pro obecný kořenový strom, v jehož vrcholech jsou uloženy prvky typu a.
(b) Využijte váš datový typ k definici nekonečného stromu, tj. takového stromu, že pro každé přirozené číslo i buďto existuje vrchol s alespoň i dětmi, nebo existuje vrchol ve hloubce alespoň i.
(c) Definujte typovou signaturu funkce takeTree.
(d) Funkci takeTree definujte.

Velky priklad

Je dán úplný (neorientovaný) graf s hranami ohodnocenými délkou. V některých vrcholech jsou dány balíčky, i víc v jednom vrcholu, a každý z nich má určené místo doručení.
Máte 1 auto, které uveze pouze daný počet balíčků. Úkolem je naplánovat cestu, která začne a končí v daném vrcholu (depo) a doručí postupně všechny balíčky. V průběhu doručování nesmí být překročena kapacita auta. Přitom máte (heuristicky) minimalizovat celkovou dobu doručování.
Popište používané datové struktury a napište funkci plán, která na vstupu obdrží
graf
specifikace balíčků
kapacitu auta
depo (počáteční vrchol)
a vrátí plán cesty.
Odpovědět

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