Hric + Dvořák 18. 9. 2012

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Hric + Dvořák 18. 9. 2012

Re: Hric + Dvořák 18. 9. 2012

od mathemage » 18. 9. 2012 22:39

Supr, sqělý :D

Díky i za big one, myslím, že řešení asi už nemusíme, ať si taky něco vyřeší sami :lol:

Re: Hric + Dvořák 18. 9. 2012

od maky » 18. 9. 2012 22:22

á, právě jsem šla zapsat. tak jen upřesním zadání:

1) definovat predikát orez(+Strom,+Dolni,+Horni,-OrezanyStrom), kde Dolni a Horni jsou meze intervalu, nechat ve stromě jen prvky X tž D <= X <= H. (už někdy bylo)

2) kontrola(+SeznamObdelniku,Vysl), obdelnik definovany o(X,Y,VX,VY), kde X,Z jsou souřadnice levého dolního rohu a VX,VY délka stran. Měly se postupně vrátit dvojice, které mají neprázdný průnik - např. V = o(0,0,1,1)-o(1,1,2,2) ; ....

3) Nejlépe vidět na příkladě:
prihradky [2,4,6,8] [5,1,6,10,7,3] --> [(1,[1]), (2,[]), (4,[3,5]), (6,[6,7]), (8,[10])]
první seznam je setříděný, jsou to meze intervalů, druhý je seznam prvků, které do těch intervalů chci rozstrkat. pokud je v seznamu prvků nějaký menší než nejmenší hranice intervalu, pak jej tam napsat a jako jeho "klíč" dát hodnotu nejmenšího prvku, jinak výstup bude začínat prvním číslem ze seznamu intervalů (tady by to byla 2).

4) a) určit datový typ hypergrafu (hypergraf = hrany tvořeny alespoň dvěma vrcholy).
b) funkci :: HGraf a -> HGraf a, tž nový hypergraf má navíc hrany mezi dvěma vrcholy, které nejsou spolu v jiné hyperhraně.
př: pův hrany: [[1,2,3],[1,2],[3,4]] --> přidané: [[1,4], [2,4]]

velký příklad:
uzávorkování výrazu - na vstupu zadány jen konstanty true/false a operátory and, not, or - jak, to si zvolíme sami. našim prvním úkolem bylo zjistit, jestli je možné toto nějak uzávorkovat, aby to byl korektní výraz (tedy např "not true and" nepůjde nikdy, ale "true and not false" už ano). priorita ani asociativita operátorů nebyla zadaná. jestliže to lze uzávorkovat, určit, jestli to lze uzávorkovat tak, že celková hodnota toho výrazu je true, pokud ano, pak nějaké (jedno) uzávorkování vydat. samozřejmě byla žádoucí i aplikace nějaké heuristiky.

Hric + Dvořák 18. 9. 2012

od mathemage » 18. 9. 2012 21:22

Hola!

Dnešní kombo Hric + Dvořák nám zadali následující příklady (některý recyklovaný, některý poupravený, některý zcela fresh):

Prolog
1)Prořezávání BVStromu
Binární vyhledávací strom (=BVS) reprezentovaný pomocí predikátů void/0 a t/3 (rekursivní struktura, navíc přirozená čísla ve vrcholech), dále přirozená čísla D a H zadány na vstupu. Prořezat tak, aby zůstal BVS právě jen s vrcholy s hodnotami ležícími mezi, tedy vrchol s hodnotou X zůstane iff D =< X =< H.

Příklad:

Kód: Vybrat vše

?- orez(t(
         t(
          void, 5, void
         ),
         10,
         t(
          t(
           void, 15, void
          ),
          20,
          t(
           void, 30, void
          ),
         ),
        ), 10, 20, T).
T = t(void, 10, t(t(void, 15, void), 20, void)).
2)Protínající se obdélníky
Obdélník (jakožto množina bodů včetně vnitřku a hranice) v rovině se stranami rovnoběžnými s osami je zadán pomocí predikátu o(X, Y, VX, VY), kde X, Y jsou souřadnice dolního levého rohu a VX, VY jeho rozměry. Dva obdélníky se protínají iff nejsou disjunktní jakožto množiny bodů (tj. jakékoli dotýkání se na hraně či v bodě se nepovažuje za nevhodné).
Na vstupu dostaneme seznam takovýchto a takto zadaných obdélníků, úkolem je backtrackingem postupně vydat všechny protínající se dvojice. Při dotazu se ukázalo, že je lepší vypsat bez opakování a v pořadí, v jakém jsou ve vstupním seznamu, tedy když se v seznamu [..., X, ... , Y] protínali, vypsat jen X-Y a ne ještě Y-X. Ale v zadání to explicitně nebylo, tak to v nejhorším šlo vynechat...

Příklad:

Kód: Vybrat vše

?- protinajiSe([o(0, 0, 1, 1), o(1, 1, 2, 3), o(2, 2, 3, 4)], V).
V = o(0, 0, 1, 1)-o(1, 1, 2, 3) ;
V = o(1, 1, 2, 3)-o(2, 2, 3, 4) ;
false.
Haskell
3)Dělení na přihrádky
umisťování holubů do holubníků, zde prvků do intervalů
Zadány seřazené prvky b_1 < \dots < b_n (pravé okraje přihrádek) a prvky c_1, \dots c_m (samotní holubi). Rozdělte prvky (holubi) do přihrádek pomocí funkce

Kód: Vybrat vše

prihradky :: Ord a => [a] -> [a] -> [(a, [a])]
takto:
a) c_k patří do přihrádky označené b_i iff b_i \leq c_k < b_{i+1}
b) c_k patří do přihrádky označené b_n iff b_n \leq c_k
To vše ve tvaru (oznaceni_prihradky, [seznam_prvku_v_teto_prihradce]).

Pokud jsou nějaké prvky (nějací holubi) menší než b_1, přidejte přihrádku (c_{min}, C), kde C je seznam těchto menších prvků.

Příklad:

Kód: Vybrat vše

> prihradky [2, 5, 11, 25] [10, 2, 1, 0, 3, 6, 30]
[(0, [1, 0], (2, [2, 3]), (5, [10, 6]), (11, []), (25, [30])]
4)Doplnění hran hypergrafu
Zadán hypergraf (viz http://cs.wikipedia.org/wiki/Hypergraf )
a) Navrhněte datovou reprezentaci hypergrafu v Haskellu, stylem HGraf a, kde a jsou datové typy vrcholů.
b) Navrhněte funkci

Kód: Vybrat vše

doplneni :: Eq a => HGraf a -> HGraf a
která k zadanému hypergrafu přidá hrany (jako v normálním grafu, tedy dvojice vrcholů), jež spolu nejsou v 1 hyperhraně.

Příklad:
Do hypergrafu s vrcholy {1, 2, 3, 4, 5} a hyperhranami {{1, 4}, {4, 5, 2}, {3, 1, 2}} se doplní hrany {1, 5}, {4, 3} a {3, 5}.

Nahoru