zkouška 12.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ů.

zkouška 12.9.2012

Příspěvekod guthro » 12. 9. 2012 22:50

Dnešní zadání:
1 Prolog :máme neorientovaný graf zadaný seznamem hran,hrana je zadaná pouze jednou(a-b).Napište funkci,která dostane seznam hran a vrátí vrcholy s jejich stupni.(nebo nejak tak).
%stupne(+Hrany,-Stupne)

2 Prolog obdelníky a okna,taky už to tu někde je.Máme zadáno okno o(X,Y,X2,Y2),kde X,Y označuje souřadnice levého dolního rohu,a X2 Y2 pravého horního.Napište funkci,která dostane seznam obdelníků definovaných stejně jako okno,pak okno,a vrátí seznam obdelníků nebo částí obdelníků co jsou vidět,tzn průnik každého obdelníku s oknem,a je li nulový,nevracet ho vůbec.

3 Haskell Máte seznam xs a a seznam dvojic a,napište funkci perm,která vrátí všechny permutace seznamu xs takové,že je v nich první prvek každé dvojice dříve než ten druhý(resp někde to tu je srozumetelněji).Zároveň napište typ funkce perm: (Eq a)=>[a]->[(a,a)]->[[a]]

4 Haskell Napi3te funkci fold pro stromy BTree a = Void | Node (Btree a) a (BTree a) takovou,aby byl její předpis a->(a->b->a->a)->BTree a->a,a zároveň pomocí ní definujte funkci hloubka a listy,které vrátí počet listů stromu a hloubku stromu.

fold :: a->(a->b->a->a)->BTree a->a
fold x f Void = x
fold x f (Node l v p)=f (fold x f l) v (fold x f p)
hloubka tree = fold 0 (\a b c -> (max a b)+1) tree
listy tree=fold 0 (\a b c->max a+b 1)

Velky: máme hypergraf-graf,kde jeho hrany mohou protínat více vrcholů,lépe se to predstavuje kruznici kolem grafu na obrazku,kde uvnitr jsou vrcholy co na hrane lezi,který má být lineární-každé dvě jeho hrany se protínají v nejvýše jednom vrcholu,a každá má alespoň 2 vrcholy.Na vstupu dostaneme libovolně zadaný hypergraf,ověřte jestli je lineární,a pokud ano,pokuste se ho obarvin n barvami,kde n je počet vrcholů.Údajně je nějaká hypotéza že to jde vždy.Můj postup byl reprezentovat si hrany seznamem vrcholů již se hrana dotýká,a nejdříve ověřit linearitu,pak si seřadit hrany podle jejich velikosti od největší(Hric říkal že by vhodnější bylo je řadit podle dotyků s ostatními hranami,ale to je o dost pracnější),a pak dávat postupně hrany do seznamů,reprezentující barvy.Nakonec spočítat počet vrcholů,a počet barev,a pokud mám barev víc,zkusit to obarvit jinak.Používal jsem prolog,a přišlo mi že spoustu věcí mám zadarmo.

Pokud by se něco co jsem napsal nedalo pochopit,ozvěte se,pokusím se dovysvětlit.
guthro
 

Re: zkouška 12.9.2012

Příspěvekod Davpe » 12. 9. 2012 23:20

Kurva, ted jsem to dopsal. No nic, tak to tady bude dvakrat :D

Prvni cast:
Cas: 1h 20 min (tedy o 5 minut dele nez normalne)
Min bodu na projiti: 11 bodu (tedy o 1 bod mene nez normalne), min. 5 za kazdy jazyk.
Dostanete k Haskellu papir http://ksvi.mff.cuni.cz/~dvorak/vyuka/N ... Funkce.pdf
Zakazan byl assert a retract

Prolog
1) Dan neorientovany graf asociativnim seznamem, ukol byl spocitat stupne vrcholu. Nekdo se tam ptal, jestli ma graf smycky, nevim jaka byla odpoved, ale asi slo uvazovat to bez nich.

stupne ([a-b, c-b. d-a, c-a], V).
V = [a-3, b-2, c-2, d-1]

Delal jsem to tak, ze jsem si prvni vytahl vsechny promenne a pak jsem pro kazdou promennou prosel seznam a pocital prispevky.
2) Mame okno (zadano levym dolnim a pravym hornim rohem, tedy o(Xd,Yd, Xh, Yh) a mame spoustu malych obdelniku (seznam o(_,_,_,_)). Mohou nastat tri pripady:
Obdelnik je mimo okno -> zahazuje me ho
Obdelnik je uvnitr okna -> nechame ho byt
Obdelnik je zcasti uvnitr, zcasti venku -> orezeme ho tak, aby byl uvnitr okna.
Ukolem je vratit seznam obdelniku po aplikaci techto kriterii

Moje Reseni:
obdelniky (_, [], []).
obdelniky(Okno, [O|OS], Out) :- mimo(Okno, O), obdelniky(Okno, Out).
obdelniky(Okno, [O|OS], [O|Out]) :- uvnitr(Okno, O), obdelniky(Okno, Out).
obdelniky(Okno, [O|OS], [NovyObdelnik|Out]) :- tranformuj(Okno, O, NovyObdelnik), obdelniky(Okno, Out).

a odpovidajici tri predikaty mimo, uvnitr a tranformuj ktere uz jsou jen hratky se zobackama

Haskell:
3)
Máme seznam prvků a dále seznam dvojic (x,y).
a) Máme definovat typ funkce perm (viz. níže)
b) Máme napsat funkci perm, která vygenerovat všechny permutace seznamu, že každá permutace splňuje, že prvek x je před prvkem y pro všechny dvojice (x,y).

perm [1,2,3,4] [(4,2), (3,1), (2,1)] = [[4,3,2,1], [4,2,3,1], [3,4,2,1], [4,2,3,1]]

Řešení:
a) perm :: Eq a => [a] -> [(a,a)] -> [[a]]
b) náčrt mého řešení
Kód: Vybrat vše

perm :: Eq a => [a] -> [(a,a)] -> [[a]]
perm seznam omezeni = perm2 (generujPermutace seznam) omezeni

perm2 :: Eq a => [[a]] -> [(a,a)] -> [[a]]
perm2 p [] = p
perm2 p (x:xs) = perm2 (filter (jeOmezeniSplneno x) p) xs

generujPermutace :: Eq a => [a] [[a]]
generujPermutace [] = [[]]
generujPermutace xs = [x:ys | x <- xs, ys = generujPermutace (delete x xs)]

jeOmezeniSplneno :: Eq => (a,a) -> [a]
jeOmezeniSplneno (a,b) xs = fromJust $ elemIndex a xs < fromJust $ elemIndex b xs

(Pozor, funkce delete a elemIndex nejsou v papiru, kde jsou vypsane funkce z haskellu, takze jsem si je programoval sam).

4)
Máme datový typ
data BTree a = Nil | Vrchol (BTree a) a (BTree a)
a) definujte funkci fold :: b -> (b -> a -> b -> b) -> BTree a -> b
b) Pouzijte funkci vyska :: BTree -> Int pomoci fold ke spocitani vysky stromu
c) POuzijte funkci listy :: BTree -> Int fold ke spocitani poctu listu

Nacrt reseni:
a)

fold b f Nil = b
fold b f (Vrchol x a y) = f (fold b f x) a (fold b f y)

b)
Kód: Vybrat vše

vyska t = fold 0 (\l a r -> (max l r)+1) t


c)
Kód: Vybrat vše

listy t = fold 0 (\l a r -> if l == 0 && r == 0 then 1 else l+r) t


(jinak pozor, hodne lidi vcetne me napsalo
Kód: Vybrat vše

listySPATNE t = fold 1 (\l a r -> l+r) t


coz nespocita listy ale Nily)

Druha cast:
Obarvovani hypergrafu
Mame hypergraf (hrany spojovat vice vrcholu nez jen dva), ktery je linearni (tj. prunik dvou hran je <= 1 vrchol)
Priklad: (v1, v2, [x), w1, w2]
Tento hypergraf je linearni, ma dve hrany (jedna spojuje vrcholy v1, v2,x druha vrcholy x, w1, w2) a pet vrcholu
(v1, [v2, x), w1, w2] -> Neni linearni (jedna hrana spojuje tri vrcholy, druha 4 ale jejich prunik jsou dva vrcholy: v2, x)

Barvime hrany linearnich hypergrafu. Existuje hypoteza, ze na to je potreba nejvyse tolik barev, kolik je vrcholu.
a) navrhnout reprezentaci hypergrafu
b) overit, zda je hypergraf linearni (tedy pro kazdou dvojici hran overit, zda prunik ma velikost 1 nebo je prazdny)
c) Overit hypotezu a najit obarveni hypergrafu + vymyslet heuristiku, jak se k reseni dopracovat rychleji (tedy neresit brute-forcem)

Delal jsem ji v Prologu (kvuli backtrackingu), nestihl jsem to dotahnout) a jeste jsem ji nemel dobre (casu bylo fakt strasne malo).

Ustni cast (Hric):
Nekteri sli druhy den, ja jsem sel jako posledni jeste ten den, mel jsem jit 17:50, dostal jsem se na radu az o hodku a pul pozdeji, takze jsem odchazel v osm (zkouska samotna zacinala v 9). Docela zabijak dne.
Prvni cast opravil do detailu (skrtal mi i chybne zavorky v haskellu), nekde napsal otaznik, jinde nejakou poznamku, dal mi to at si to projdu, otaznik jsem mu vysvetlil (mel jsem to dobre, akorat to v te zmeti pismen nepochopil, takze se urcite hne nevzdavat a je dobre se zeptat, co se mu tam nelibi), opravil jsem si i nektere veci a napsal mu je vedle na papir.
Dve ulohy jsem mel uplne spravne na plny pocet (2 + 3), zbytek 2 a 2 tedy 14 bodu.
Pak vzal velkou ulohu, kterou opravenou nemel a spolecne jsme to prosli (bral postupne jeden predikat po druhem, dukladne to cetl, kazdou promennou, zamyslel se jak to funguje, podtrhaval, co bylo spatne. Ptal se me i jakou jsem vymyslel heuristiku a nejake jeji obhajeni ze neni uplne k nicemu...

Znamka za 2.

Na obe casti bylo malo casu, prvni jsem stihl tak tak, ale nezkontroloval, druhou cast jsem nestihl. Ale to byl problem skoro u vsech. Kdyz to porovnam s Unixem, kde byl k dispozici jeste pocitac + libovolna literatura, proletel to behem par minut a vubec se nezaobiral detaily...zatimco tady se v tom strasne rejpou, daji vam seznam funkci jen pro haskell a to jeste jen par vybranych a to strhavani bodu mi prislo taky docela prisne. Ale zkousejici jsou nastesti hodni a nejakou znamku z toho vykouzli.
Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
 
Příspěvky: 98
Registrován: 22. 9. 2010 15:07
Typ studia: Informatika Bc.
Login do SIS: pegrimed

Re: zkouška 12.9.2012

Příspěvekod mathemage » 16. 9. 2012 21:20

Davpe píše:
Moje Reseni:
obdelniky (_, [], []).
obdelniky(Okno, [O|OS], Out) :- mimo(Okno, O), obdelniky(Okno, Out).
obdelniky(Okno, [O|OS], [O|Out]) :- uvnitr(Okno, O), obdelniky(Okno, Out).
obdelniky(Okno, [O|OS], [NovyObdelnik|Out]) :- tranformuj(Okno, O, NovyObdelnik), obdelniky(Okno, Out).

a odpovidajici tri predikaty mimo, uvnitr a tranformuj ktere uz jsou jen hratky se zobackama


Hola! Nejak mi to nedalo, tak jsem se chtel podelit o reseni, ktere napadlo mne. Davpeho reseni je samozrejme naproste spravne, ale jen pokud nema nekdo rad moc zobacku, muze zkusit toto:

Kód: Vybrat vše
prunik2D(o(Xd, Yd, Xh, Yh), o(Xd2, Yd2, Xh2, Yh2), o(Sd, Vd, Sh, Vh) ) :-
  prunik(Xd-Xh, Xd2-Xh2, Sd-Sh),
  prunik(Yd-Yh, Yd2-Yh2, Vd-Vh).

prunik(A1-A2, B1-B2, L-R) :-
  (A1 < B1 -> L = B1 ; L = A1),
  (A2 < B2 -> R = A2 ; R = B2),
  L < R.

cut(Okno, [], []).
cut(Okno, [O|Os], [Cut|Os2]) :-
  prunik2D(Okno, O, Cut), !,
  cut(Okno, Os, Os2).
cut(_, [_|Os], Os2) :-
  cut(Okno, Os, Os2).


Prunik 2 obdelniku se pocita jako (kartezsky) soucin 2 intervalu v jednotlivych dimenzich (na vysku & na sirku). Kdyz jsou disjunktni, selze, coz automaticky pomuze pri vyhazovani disjunktnich obdelniku.
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
 
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Login do SIS: had


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

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník