NPRG005/Zkouška Dvořák, Hric 25.06. 2012

1. Prolog: Klastr dosažitelnosti
je dán neorientovaný ohodnocený graf jako seznam hran s ohodnocením, každá hrana pouze v jednom směru. Dále je dán vrchol V grafu a hodnota Prah. Definujte predikát klastr/4: klastr(+Graf, +V, +Prah, -Klastr), který vrátí v proměnné Klastr seznam všech těch vrcholů Grafu, které jsou dosašitelné z vrcholu V cestou z hran s ohodnocením nejvýše Prah.

2. Prolog: Pseudosplay binárního stromu
Binární vyhledávací strom (BVS) obsahuje číselné hodnoty a reprezentujeme ho pomocí funktorů t/3 a void/0. Na stupu je dán binární vyhledávací strom a jeden jeho vrchol V. Napište prodecuru
transf/3: transf(+BVS,+V,-BVS0),
která pomocí rotací transformuje vstupní strom BVS tak, že vrchol V se dostane do kořene výstupního stromu BVS0, který je platný binární vyhledávací strom.
Příklad:

? transf(t(void,1,t(t(void,5,void),10,void)),5,V).
V = t(t(void,1,void),5,t(void,10,void))

3. Haskell: Izomorfní stromy
Binární strom je reprezentován pomocí typu

data Bt a = Void
          | Node (Bt a) a (Bt a)

Napište funkci izo i :: Int -> Bt a -> [Bta a], která dostane číslo N a strom S a vyrobí seznam všech stromů, které mají v právě N vrcholech prohozenou pravou a levou větev.
Příklad: (indentace ve výstupu pro přehlednost)

> izo 1 Node (Node Void 1 (Node Void 2 (Node Void 0 Void)))
[Node (Node Void
            2
           (Node Void 0 Void))
       1
       Void,
Node Void
     1
    (Node (Node (Void 0 Void)
           2
           Void)]

4. Haskell: Uspořádání stromu
N-ární strom je reprezentován datovým typem

data NTree a = Ntree a [Ntree a]

a ve vrcholech obsahuje dvojice (klíč, hodnota). Napište funkci

sort NT :: (h->k->Bool) -> Ntree (k, h) -> Ntree (k, h)

která uspořádá v každém vrcholu stromu jeho podstromy podle klíče podle dané porovnávací funkce cmp.
Máte k dispozici funkci sort :: (a->a->Bool) -> [a] -> [a]
Příklad

> sortNT (<) (Ntree (1, 'a') [Ntree (3, 'x') [], Ntree (0, 'z') []])
(Ntree (1, 'a') [Ntree (0, 'z') [], NTree (3, 'x') []])

Velký příklad: Problém n obchodních cestujících (přibližné znění)
Můžete si vybrat jeden z těchto jazyků: Prolog, Haskell
Na vstupu je zadán úplný graf G s ohodnocenými hranami, počáteční vrchol V grafu a číslo N. Úkolem je navrhnout heuristiku, která najde N různých cest (kružnic přes všechny vrcholy) tak, aby bylo pokud možno minimalizována maximální délka některé z cest. Cílem není napsat perfektní algoritmus, který najde řešení v nekonečném čase, ale nějaký rozumně rychlý algoritmus. V grafu platí trojúhelníková nerovnost.

V prvním příkladu byla nejasnost zadání, zda-li se vztahuje formulace "cestou z hran s ohodnocením nejvýše Prah" k jednotlivým hranám, nebo k celé cestě. Nakreslili nám na tabuli, že myslí k jednotlivým hranám. Než se tak stalo, ztratil jsem zhruba 10 minut času vymýšlením řešení alternativní verze.

Na vypracování bylo standardně 75 minut, poté následovala krátká pauza a druhá část, na kterou bylo 90 minut.

Zkouška 25.06.2012