Fórum studentů MFF UK

[quote="John Beak"]
[b]
Na vstupu je zadán úplný graf [i]G[/i] s ohodnocenými hranami, počáteční vrchol [i]V[/i] grafu a číslo [i]N[/i]. Ú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.
[line][/line]
[/quote]

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
[quote]minimalizována maximální délka některé z cest[/quote]
Jakoze delka nejdelsi z tech N cest je co nejmensi?

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

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

> 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)]

data NTree a = Ntree a [Ntree a]

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

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

[b]1. Prolog: Klastr dosažitelnosti[/b]
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 [i]V[/i] grafu a hodnota [i]Prah[/i]. Definujte predikát [i]klastr/4: klastr(+Graf, +V, +Prah, -Klastr)[/i], který vrátí v proměnné [i]Klastr[/i] seznam všech těch vrcholů Grafu, které jsou dosašitelné z vrcholu V cestou z hran s ohodnocením nejvýše [i]Prah[/i].

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

[b]3. Haskell: Izomorfní stromy[/b]
Binární strom je reprezentován pomocí typu
[code]data Bt a = Void
| Node (Bt a) a (Bt a)[/code]
Napište funkci [i]izo i :: Int -> Bt a -> [Bta a][/i], která dostane číslo [i]N[/i] a strom [i]S[/i] a vyrobí seznam všech stromů, které mají v právě [i]N[/i] vrcholech prohozenou pravou a levou větev.
[u]Příklad:[/u] (indentace ve výstupu pro přehlednost)
[code]> 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)][/code]

[b]4. Haskell: Uspořádání stromu[/b]
N-ární strom je reprezentován datovým typem
[code]data NTree a = Ntree a [Ntree a][/code]
a ve vrcholech obsahuje dvojice [i](klíč, hodnota)[/i]. Napište funkci
[code]sort NT :: (h->k->Bool) -> Ntree (k, h) -> Ntree (k, h)[/code]
která uspořádá v každém vrcholu stromu jeho podstromy podle klíče podle dané porovnávací funkce [i]cmp[/i].
Máte k dispozici funkci [i]sort :: (a->a->Bool) -> [a] -> [a][/i]
[u]Příklad[/u]
[code]> sortNT (<) (Ntree (1, 'a') [Ntree (3, 'x') [], Ntree (0, 'z') []])
(Ntree (1, 'a') [Ntree (0, 'z') [], NTree (3, 'x') []])[/code]
[line][/line]
[b]Velký příklad: Problém n obchodních cestujících[/b] (přibližné znění)
Můžete si vybrat jeden z těchto jazyků: Prolog, Haskell
Na vstupu je zadán úplný graf [i]G[/i] s ohodnocenými hranami, počáteční vrchol [i]V[/i] grafu a číslo [i]N[/i]. Ú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.
[line][/line]
V prvním příkladu byla nejasnost zadání, zda-li se vztahuje formulace "cestou z hran s ohodnocením nejvýše [i]Prah[/i]" 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.