od Davpe » 13. 9. 2012 00: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.
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/NPRG005/HaskellFunkce.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í
[code]
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
[/code]
(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)
[code]
vyska t = fold 0 (\l a r -> (max l r)+1) t
[/code]
c)
[code]
listy t = fold 0 (\l a r -> if l == 0 && r == 0 then 1 else l+r) t
[/code]
(jinak pozor, hodne lidi vcetne me napsalo
[code]
listySPATNE t = fold 1 (\l a r -> l+r) t
[/code]
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.