Zkouška 25.06.2012

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ů.
John Beak
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 29. 10. 2009 20:59
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Zkouška 25.06.2012

Příspěvek od John Beak »

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:

Kód: Vybrat vše

? 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

Kód: Vybrat vše

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)

Kód: Vybrat vše

> 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

Kód: Vybrat vše

data NTree a = Ntree a [Ntree a]
a ve vrcholech obsahuje dvojice (klíč, hodnota). Napište funkci

Kód: Vybrat vše

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

Kód: Vybrat vše

> 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.
Trolling is a art.
Design Your Universe
IcyTower.cz
John Beak's Website
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Zkouška 25.06.2012

Příspěvek od mathemage »

John Beak píše:
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?
Carpe Diem!
Odpovědět

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