# Hric + Dvořák 18. 9. 2012

<{ForumPost(poster="mathemage", timestamp=2012-09-18 21:22:42)}>
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:

    ?- 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:

    ?- 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

    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:

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

    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}.*
<{/ForumPost}>

<{ForumPost(poster="maky", timestamp=2012-09-18 22:22:53)}>
á, 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.
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-09-18 22:39:37)}>
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:
<{/ForumPost}>