# Zkouska 20.9.2017

<{ForumPost(poster="didllicek", timestamp=2017-09-20 21:31:15)}>
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.**
<{/ForumPost}>