Hric + Dvořák 18. 9. 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ů.
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:

Hric + Dvořák 18. 9. 2012

Příspěvek od mathemage »

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}.
Naposledy upravil(a) mathemage dne 18. 9. 2012 22:37, celkem upraveno 2 x.
Carpe Diem!
maky
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 24. 1. 2010 15:25
Typ studia: Informatika Mgr.

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

Příspěvek od maky »

á, 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.
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: Hric + Dvořák 18. 9. 2012

Příspěvek od mathemage »

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:
Carpe Diem!
Odpovědět

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