# Zkouška 25.06.2012

<{ForumPost(poster="John Beak", timestamp=2012-07-07 20:27:36)}>
**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.
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-09-03 21:01:17)}>

 > John Beak wrote:
 > **  
 > 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.**
 > 
 > ----
**  
  
Ahoj!  
  
Prosim te, jak se to jen resilo? Rikal nejake reseni (prip. jaks to treba delal ty)? K cemu tam napr. byla ta trojuhelnikova nerovnost?  
  
BTW co se mysli tim**

 > **minimalizována maximální délka některé z cest**
**  
Jakoze delka nejdelsi z tech N cest je co nejmensi?**
<{/ForumPost}>