# Zkouska 14.6 2010 <{ForumPost(poster="DarkAngeL", timestamp=2010-06-14 22:29:42)}> Zacneme sadou "lehkych prikladu": (predpoklada se, ze vstupy jsou korektni) PROLOG 1) Definujte predikat orez(+Seznam obdelniku, +Okno, -Seznam orezanych obdelniku), ktery vyreze z kazdeho daneho obdelniku tu cast, ktera se nachazi v okne a hodi ji na vystup. Nachazi-li se obdelnik uplne mimo okno, na vystup neprijde misto nej nic. Obdelniky jsou zadany nasledovne: **o(XD,YD,XH,YH)** - \[XD,YD] jsou souradnice leveho dolniho rohu a \[XH,YH] jsou souradnice praveho horniho rohu obdelniku. Okno je zadano jako obdelnik. Priklad: ?- orez(\[o(1,1,3,3),o(2,3,5,4)],o(2,2,4,4),V). V = \[o(2,2,3,3),o(2,3,4,4)]. Reseni: orez([],_,[]). orez([o(XD,YD,XH,YH)|Zb], o(XL,YL,XP,YP), [o(XD1,YD1,XH1,YH1)|V]) :- orez_obd(XD,XH,XL,XP,XD1,XH1), XD1 \== nil,orez_obd(YD,YH,YL,YP,YD1,YH1), YD1 \== nil, !,orez(Zb, o(XL,YL,XP,YP), V). orez([_|Zb], Okno, V) :- orez(Zb, Okno, V). orez_obd(D,H,L,P,D,H) :- D >= L, H =< P, !. orez_obd(D,H,L,P,L,H) :- D =< L, H >= L, H =< P, !. orez_obd(D,H,L,P,D,P) :- D >= L, D =< P, H >= P, !. orez_obd(D,H,L,P,L,P) :- D =< L, H >= P, !. orez_obd(_,H,L,_,nil,nil) :- H =< L, !. orez_obd(D,_,_,P,nil,nil) :- D >= P. 2) Mame zadan graf ve smyslu vrcholu a jeho sousedu (seznam prvku tvaru: {oznaceni_vrcholu}-{seznam oznaceni jeho sousedu}). Definujte predikat troj(+Graf,-Trojuhelniky), kde "Trojuhelniky" je seznam vsech trojic vrcholu, ktere tvori v G trojuhelnik. Priklad: ?- troj( \[a-\[b,c], b-\[a,c,d], c-\[a,b,d], d-\[b,c]], T ). T = \[\[a, b, c], \[b, c, d]]. Reseni: troj(G,T) :- setof(S, trojuh(G,S), T). trojuh(G,T) :- select(V1,G,G1), select(V2,G1,G2), select(V3,G2,_),je_trojuh(V1,V2,V3), oznaceni(V1,V11), oznaceni(V2,V22), oznaceni(V3,V33), sort([V11,V22,V33], T). je_trojuh(V1-S1,V2-S2,V3-S3) :- member(V2,S1), member(V3,S2), member(V1,S3). oznaceni(V-S,V). HASKELL 1) Definujte funkci gen, ktera se vstupnim parametrem typu Int vytvori nekonecny seznam seznamu prirozenych cisel, serazenych maximo-lexikograficky, tzn.: a) pro libovolne takove 2 seznamy S1 a S2 plati, ze je-li maximum S1 < maximum S2, pak je S1 pred S2 ve vytvarenem seznamu b) je-li max S1 = max S2, pak rozhoduje lexikograficke pravidlo, tzn. "jdi tak dlouho v obou seznamech, dokud nenarazis na prvni prvek, kde se lisi, a seznam s mensim prvkem umisti pred druhy" Priklad: take 10 (gen 2) => \[\[0,0],\[0,1],\[1,0],\[1,1],\[0,2],\[1,2],\[2,0],\[2,1],\[2,2],\[0,3]] Reseni: gen n = genN n 0 genN n max = (filter (any (==max)) (genS n max)) ++ (genN n (max+1)) genS 0 _ = [] genS 1 max = [[a] | a<-[0..max]] genS n max = [a:b | a<-[0..max], b <- predchozi] where predchozi = genS (n-1) max 2) Datovy typ binarni strom mame zadan jako: data BStrom a = List | Vrchol (BStrom a) a (BStrom a) Definujte funkci fold pro takovy binarni strom, tzn.: fold:: ... Tenhle priklad jsem nedelal (a dokonce ani nemuzu zarucit, ze tenhle malej kus je dobre), takze prosim omluvte mou nedostatecnou pamet a komentujte :p Mno, a zbyva velky priklad (jako obvykle, jazyk jste si mohli vybrat): 5) Mame zadane dvojice vet ve dvou jazycich, tzn. veta a jeji preklad - oboje zadano jako usporadany seznam slov. Z toho mame pomoci nami zvolene heuristiky nalezt co nejlepsi vykladovy slovnik typu: (Slovo prvniho jazyka) -> (Slovo druheho jazyka). Mejte na pameti, ze: a) jedno slovo muze mit vice prekladu b) pocet slov vety a jejiho prekladu se muze povelmi ruznit c) na slovosled nemuzeme brat ohled d) nemusime resit sklonovani atd (jedno slovo se vyskytuje ve vsech vetach prave v jednom tvaru) e) neco, co moje pamet hodila do trychtyre. Alespon takhle nejak jsem to pochopil a takhle nejak si to pamatuju :) <{/ForumPost}> <{ForumPost(poster="Filatko", timestamp=2010-06-15 11:18:54)}> > DarkAngeL wrote:Zacneme sadou "lehkych prikladu": (predpoklada se, ze vstupy jsou korektni) > > 2) Datovy typ binarni strom mame zadan jako: > data BStrom a = List | Vrchol (BStrom a) a (BStrom a) > Definujte funkci fold pro takovy binarni strom, tzn.: > fold:: ... > Tenhle priklad jsem nedelal (a dokonce ani nemuzu zarucit, ze tenhle malej kus je dobre), takze prosim omluvte mou nedostatecnou pamet a komentujte :p Mel se definovat obecny pruchod stromem (fold) a pomoci nej funkce pro vysku stromu a pocet uzlu. Mohlo to jit treba: data Btree a = Nil | Node (Btree a) a (Btree a) binFold::b->(b->a->b->b)->Btree a->b binFold z _ Nil = z binFold z f (Node l v r) = f (binFold z f l) v (binFold z f r) vyska::Btree a->Int vyska = binFold 0 (\x y z -> (max x z) + 1) uzlu::Btree a->Int uzlu=binFold 0 (\x y z -> x+z+1) <{/ForumPost}> <{ForumPost(poster="Filatko", timestamp=2010-06-15 11:24:27)}> Spis me ale jeste zajima (neb si to pro velky uspech zopakuju), jak je to hodnoceny? Tj. vztah mezi tema mensima ulohama, tou vetsi a vyslednou znamkou. <{/ForumPost}> <{ForumPost(poster="venca", timestamp=2010-06-15 13:43:00)}> > Filatko wrote:Spis me ale jeste zajima (neb si to pro velky uspech zopakuju), jak je to hodnoceny? Tj. vztah mezi tema mensima ulohama, tou vetsi a vyslednou znamkou. Já byl dneska na ústní u Dvořáka a dopad jsem následovně: Za každou menší úlohu bylo max. 5 bodů, tj. dohromady 20 a pro postup do dalšího kola bylo třeba 13. Já měl přesně 13 :) U velký úlohy jsem mu popsal jaká byla moje myšlenka, on si jen tak lehce prošel nějaký moje predikáty...a i když sem to zdaleka neměl hotový, tak naštěstí z toho byla vidět ta moje myšlenka. Hodnocení menších úloh bylo za 3, větší úloha spíš za 2, tak mi dal šanci na celkovou 2, pokud napíšu tu menší úlohu č.3, kterou jsem v písemce nestih. Dal mi na to čtvrt hodiny, ale nevymyslel sem to. Tak sem odešel s trojkou <{/ForumPost}> <{ForumPost(poster="Filatko", timestamp=2010-06-15 14:01:30)}> > venca wrote: > > Filatko wrote:Spis me ale jeste zajima (neb si to pro velky uspech zopakuju), jak je to hodnoceny? Tj. vztah mezi tema mensima ulohama, tou vetsi a vyslednou znamkou. > > > Já byl dneska na ústní u Dvořáka a dopad jsem následovně: > Za každou menší úlohu bylo max. 5 bodů, tj. dohromady 20 a pro postup do dalšího kola bylo třeba 13. Já měl přesně 13 :) > U velký úlohy jsem mu popsal jaká byla moje myšlenka, on si jen tak lehce prošel nějaký moje predikáty...a i když sem to zdaleka neměl hotový, tak naštěstí z toho byla vidět ta moje myšlenka. > Hodnocení menších úloh bylo za 3, větší úloha spíš za 2, tak mi dal šanci na celkovou 2, pokud napíšu tu menší úlohu č.3, kterou jsem v písemce nestih. Dal mi na to čtvrt hodiny, ale nevymyslel sem to. Tak sem odešel s trojkou Nechce se ti lehce naznacit tu tvou myslenku? :D <{/ForumPost}> <{ForumPost(poster="venca", timestamp=2010-06-15 14:13:32)}> > Filatko wrote: > > venca wrote: > > > Filatko wrote:Spis me ale jeste zajima (neb si to pro velky uspech zopakuju), jak je to hodnoceny? Tj. vztah mezi tema mensima ulohama, tou vetsi a vyslednou znamkou. > > > > > > Já byl dneska na ústní u Dvořáka a dopad jsem následovně: > > Za každou menší úlohu bylo max. 5 bodů, tj. dohromady 20 a pro postup do dalšího kola bylo třeba 13. Já měl přesně 13 :) > > U velký úlohy jsem mu popsal jaká byla moje myšlenka, on si jen tak lehce prošel nějaký moje predikáty...a i když sem to zdaleka neměl hotový, tak naštěstí z toho byla vidět ta moje myšlenka. > > Hodnocení menších úloh bylo za 3, větší úloha spíš za 2, tak mi dal šanci na celkovou 2, pokud napíšu tu menší úlohu č.3, kterou jsem v písemce nestih. Dal mi na to čtvrt hodiny, ale nevymyslel sem to. Tak sem odešel s trojkou > > > Nechce se ti lehce naznacit tu tvou myslenku? :D Nic světobornýho...jednoduše sem vytvořil z každý tý dvojice vět všechny možný dvojice slov a do slovníku sem dával ty dvojice slov, který se vyskytovali nejčastějc... Docela rozumná byla taky poznámka, že těch dvojic vět na vstupu byli třeba miliony, aby člověk nehledal nějakou závratnou heuristiku... <{/ForumPost}>