[ZK] 1.2., 8:30

gASK
Admin(ka) level I
Příspěvky: 635
Registrován: 9. 6. 2005 12:33
Typ studia: Informatika Mgr.
Bydliště: Konečně Vinohrady:)
Kontaktovat uživatele:

[ZK] 1.2., 8:30

Příspěvek od gASK »

Proboha, proč tak brzo? :evil:

Takže, protože sem nikdo ještě nedal zadání, dovoluji si tak učinit já. Takže poslouchejte, pohádka začíná:

PROLOG

Kód: Vybrat vše

1. Maté orientovaný graf. Máte množinu vrcholů. Slučte tuto množinu vrcholů do jednoho. (Tzn místo této množiny bude ve výsledném grafu jen jeden nový vrchol, místo všech hran vedoucích z nějakého vrcholu do / z libovolného vrcholu této množiny jen jedna vedoucí do / z toho nového vrcholu)

Kód: Vybrat vše

2. Máte dán n-ární strom, který má v každém uzlu OKNO (dané souřadnicí levého horního a pravého dolního rohu). Napište predikát, co tento strom projde a ořeže každé okno podle jeho předka (tzn. to co přes předka "přečuhuje" uřízne a vrátí nový strom). Pokud je celé mimo předka, zahoďte uzel i jeho potomky.
HASKELL

Kód: Vybrat vše

3. Máte dán n-ární strom. Napište predikát co vrátí seznam cest ze všech listů ke kořeni.

Kód: Vybrat vše

4. Máte dán seznam xs a číslo n. Napište funkci co vám vrátí takovou podmnožinu xs, že její součet je <= n a to tak, že co "nejblíže".
Velká úloha je dlouhá, tak mi dovolte pauzu, napíšu ji pod to do nového příspěvku. :wink:
gASK
Admin(ka) level I
Příspěvky: 635
Registrován: 9. 6. 2005 12:33
Typ studia: Informatika Mgr.
Bydliště: Konečně Vinohrady:)
Kontaktovat uživatele:

Příspěvek od gASK »

Takže tady je slibovaná velká úloha. Tentokrát byla opravdu hyper :twisted:

Kód: Vybrat vše

Máte dán orientovaný hypergraf: orientovaný hypergraf je dán množinou vrcholů a množinou hyperhran - hyperhrana je hrana, co má právě jeden výstupní vrchol a alespoň jeden (ale může jich být víc) vstupní vrchol. 

Vrchol v je dosažitelný z množiny M právě tehdy, když existuje hrana (resp. cesta), jejíž vstupní vrcholy jsou všechny z M a jejíž výstupní vrchol je v. Máte dánu množinu M, kde každý vrchol je dostupný ze všech ostatních. Máte najít všechny vrcholy dostupné z této množiny a určit jejich vzdálenost (viz dole). Použijte k tomu modifikovaný Dijkstrův algoritmus.

Vzdálenost nějakého vrcholu je rovna součtu vzdáleností všech vstupních vrcholů hyperhrany, jež do něj vede, plus jedna. Vzdálenost všech vrcholů z M je pochopitelně 0. Viz obrázek dole 


Tož pěkné, ne? :twisted:
Přílohy
Vzdálenosti pro ty z vás, co by se jim zdála slovní definice nejasná. Červeně jsou vrcholy z M, černě normální vrcholy, modré šipky jsou hyperhrany.
Vzdálenosti pro ty z vás, co by se jim zdála slovní definice nejasná. Červeně jsou vrcholy z M, černě normální vrcholy, modré šipky jsou hyperhrany.
hypergraf.JPG (11.44 KiB) Zobrazeno 7962 x
Uživatelský avatar
nytram
Matfyz(ák|ačka) level II
Příspěvky: 68
Registrován: 4. 1. 2005 15:54
Typ studia: Informatika Bc.
Bydliště: da B-9'th floor
Kontaktovat uživatele:

Příspěvek od nytram »

inak, jeho pismo a vysvetlovanie stoja za h0vn0, zadanie tam naskrabal a vysvetlil to este "lepsie"... :evil: :twisted:

po polhodiny vahania, ci tam ostat do konca som dospel k zaveru : radsej zdrhnut! .... snaaad nabuduce :(
Quod Erat Demonstrandum.
Kuba
Matfyz(ák|ačka) level II
Příspěvky: 92
Registrován: 2. 6. 2005 22:55
Typ studia: Informatika Mgr.
Bydliště: Praha - Dejvice
Kontaktovat uživatele:

Re: [ZK] 1.2., 8:30

Příspěvek od Kuba »

gASK píše:

Kód: Vybrat vše

2. Máte dán n-ární strom, který má v každém uzlu OKNO (dané souřadnicí levého horního a pravého dolního rohu). Napište predikát, co tento strom projde a ořeže každé okno podle jeho předka (tzn. to co přes předka "přečuhuje" uřízne a vrátí nový strom). Pokud je celé mimo předka, zahoďte uzel i jeho potomky.
Můžu si to představit jako okna s podokny ve Windows?
Uživatelský avatar
wintermute
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 23. 5. 2005 22:06
Typ studia: Informatika Mgr.

Re: [ZK] 1.2., 8:30

Příspěvek od wintermute »

Kuba píše:Můžu si to představit jako okna s podokny ve Windows?
Nemůžeš!!!
Návštěvník

Příspěvek od Návštěvník »

Kuba napsal:
Můžu si to představit jako okna s podokny ve Windows?

Nemůžeš!!!

Ale muzes! :) Nekdo se na to Hricaka ptal......


Mam pocit, ze je dneska v nedobrej nalade, pri opravovani tech pisemek tam bouchal hlavou do stolu :(
Kuba
Matfyz(ák|ačka) level II
Příspěvky: 92
Registrován: 2. 6. 2005 22:55
Typ studia: Informatika Mgr.
Bydliště: Praha - Dejvice
Kontaktovat uživatele:

Příspěvek od Kuba »

Anonymous píše:
Kuba napsal:
Můžu si to představit jako okna s podokny ve Windows?

Nemůžeš!!!

Ale muzes! :) Nekdo se na to Hricaka ptal......


Mam pocit, ze je dneska v nedobrej nalade, pri opravovani tech pisemek tam bouchal hlavou do stolu :(
To si asi rikal "Ja blbec, jak jsem je to naucil?!"

A kdy se vlastne chodi na ustni?
Naposledy upravil(a) Kuba dne 1. 2. 2006 14:41, celkem upraveno 1 x.
Uživatelský avatar
wintermute
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 23. 5. 2005 22:06
Typ studia: Informatika Mgr.

Příspěvek od wintermute »

Anonymous píše:
Kuba napsal:
Můžu si to představit jako okna s podokny ve Windows?

Nemůžeš!!!

Ale muzes! :) Nekdo se na to Hricaka ptal......


Mam pocit, ze je dneska v nedobrej nalade, pri opravovani tech pisemek tam bouchal hlavou do stolu :(
A jéje... no, tak já letim, v 15:30 mám ústní část zkoušky. Docela si i věřim na 1, ale jestli ho třeba bolí zub... :(
Uživatelský avatar
Necroman
Supermatfyz(ák|ačka)
Příspěvky: 459
Registrován: 20. 1. 2005 19:46
Typ studia: Informatika Mgr.
Bydliště: Louny / kolej Jednota, Praha
Kontaktovat uživatele:

Re:

Příspěvek od Necroman »

Tak je to doma... priklady byly celkem pohodove, ten prvni vysel na 4 radky :-)

Kód: Vybrat vše

hrany zadany jako h(a,b). ->hrana z A do B
seznam vrcholu, ktery se mel sloucit do jednoho (napr vrcholu n): x(a). x(b). ...
reseni:

vyres(S):- setof(h2(X,Y),h2(X,Y),S).
h2(X,Y):-h(X,Y),\+ x(X), \+ x(Y).
h2(n,Y):-h(X,Y),x(X), \+ x(Y).
h2(X,n):-h(X,Y),\+ x(X), x(Y).
Jeste jedna rada, zkuste nepouzivat k reseni velkych prikladu "naivni" algoritmy, me dal kvuli tomu za tri :roll: .
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
gASK
Admin(ka) level I
Příspěvky: 635
Registrován: 9. 6. 2005 12:33
Typ studia: Informatika Mgr.
Bydliště: Konečně Vinohrady:)
Kontaktovat uživatele:

Příspěvek od gASK »

Nevím v jaké je náladě, ale mně dal za jedna. A vůbec, co jsem mu koukal pod ruku, tak většina co zatím rozdal byly jedničky...jinak ústni jela od dvou, já tam měl být na půl třetí, na řadu jsem se dostal o čtvrt na čtyři, přesvědčil mne, že mý řešení druhý příkladu nefunguje, přečetl velkej, pokejval hlavou a pravil: "Index". Tak asi tak.

Jinak ono i řešení třetího a čtvrtého příkladu bylo všeho všudy po šesti řádcích. Jen ten proklatej druhej mi zabral dvě stránky :twisted:
Návštěvník

Příspěvek od Návštěvník »

gASK píše: Jinak ono i řešení třetího a čtvrtého příkladu bylo všeho všudy po šesti řádcích. Jen ten proklatej druhej mi zabral dvě stránky :twisted:
slo by to sem prosim napsat? urcite by to mnoha lidem pomohlo a kdyz je to tak kratke, tak by to nemuselo zabrat moc casu ani vam. diky (mam na mysli 3. a 4.)
Uživatelský avatar
wintermute
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 23. 5. 2005 22:06
Typ studia: Informatika Mgr.

Příspěvek od wintermute »

Takže za 1. Ale myslim, že jsem na něj neudělal moc dobrej dojem, když zjistil, že vlastně pořádně neumim Dijkstrův algoritmus.
Kuba
Matfyz(ák|ačka) level II
Příspěvky: 92
Registrován: 2. 6. 2005 22:55
Typ studia: Informatika Mgr.
Bydliště: Praha - Dejvice
Kontaktovat uživatele:

Příspěvek od Kuba »

Anonymous píše:
gASK píše: Jinak ono i řešení třetího a čtvrtého příkladu bylo všeho všudy po šesti řádcích. Jen ten proklatej druhej mi zabral dvě stránky :twisted:
slo by to sem prosim napsat? urcite by to mnoha lidem pomohlo a kdyz je to tak kratke, tak by to nemuselo zabrat moc casu ani vam. diky (mam na mysli 3. a 4.)
Moje reseni neni zrovna na 6 radku, ale tohle (3) jsem si psal doma:

Kód: Vybrat vše

data NTree a = Tr a [NTree a]

-- Prochazi strom a pamatuje si, kudy sel (cur - prvky pridava dopredu, jde o cestu z listu do korene!)
-- Kdyz dojde do listu, prida cestu do seznamu cest, ktery se vsude taha (sezn)

hledej :: NTree a -> [[a]]
hledej (Tr x (y:ys)) = ses [x] (y:ys) [[]]

ses :: [a] -> [NTree a] -> [[a]] -> [[a]]		              -- projde vsechny podstromy aktualniho uzlu
ses _ [] [[]] = []		                                     -- aby to nevracelo prazdny seznamy navic
ses _ [] x = x                                               -- kdyz jsem prosel vsechny podstromy
ses cur (y:ys) sezn = sestup cur y sezn ++ ses cur ys sezn   -- cesty z aktualniho podstromu ++ z ostatnich

sestup :: [a] -> NTree a -> [[a]] -> [[a]]	                -- zpracuje jeden podstrom
sestup cur (Tr x []) [[]] = [(x:cur)]			               -- aby to nevracelo prazdny seznamy navic
sestup cur (Tr x []) sezn = (x:cur):sezn		               -- list
sestup cur (Tr x (y:ys)) sezn = ses (x:cur) (y:ys) sezn	   -- nelist
gASK
Admin(ka) level I
Příspěvky: 635
Registrován: 9. 6. 2005 12:33
Typ studia: Informatika Mgr.
Bydliště: Konečně Vinohrady:)
Kontaktovat uživatele:

Příspěvek od gASK »

Anonymous píše:
gASK píše: Jinak ono i řešení třetího a čtvrtého příkladu bylo všeho všudy po šesti řádcích. Jen ten proklatej druhej mi zabral dvě stránky :twisted:
slo by to sem prosim napsat? urcite by to mnoha lidem pomohlo a kdyz je to tak kratke, tak by to nemuselo zabrat moc casu ani vam. diky (mam na mysli 3. a 4.)
Takže řešení trojky:

Kód: Vybrat vše

data Tree a = Leaf a | Branch a [Tree a]

cesta::Tree a -> [[a]]
cesta Leaf x  =  [[x]]
cesta Branch x xs  =  map (++[x]) (fold [cesta y | y <- xs])

fold::[[a]] -> [a]
fold [] = []
fold (x:xs) = x++(fold xs)
Jinak řečeno jsem si v každém vrcholu nechal do seznamu nasypat všechny cesty do všech jeho synů, ke všem připojil na konec daný uzel (nejsem si jist, jestli mám ten map správně, něco se mi tam nezdá).
Fold pouze zajišťuje "správný počet závorek", páč mi po kadžý iteraci cesty jedny "přebývají".

A čtyřka:

Kód: Vybrat vše

soucet::[a] -> a -> [a]
soucet  []  _  =  0
soucet  _   0  =  0
soucet  (x:xs) n  =  
                  if (sum Batoh1 <= n) then
                        if (sum Batoh2 > n) then
                               (Batoh1)
                        elseif (sum Batoh1 >= sumBatoh2) then
                               (Batoh1)
                         else
                                (Batoh2)
                  else
                      (Batoh2)
                  where
                       Batoh1 = x:(soucet xs n-x)
                       Batoh2 = soucet xs n
Tohle není ouplně šest řádků, ale je to zase pro změnu úplně triviální program.
Naposledy upravil(a) gASK dne 2. 2. 2006 22:35, celkem upraveno 1 x.
Uživatelský avatar
rastik
Supermatfyz(ák|ačka)
Příspěvky: 661
Registrován: 19. 10. 2005 21:45
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Příspěvek od rastik »

gASK píše:(nejsem si jist, jestli mám ten map správně, něco se mi tam nezdá). Fold pouze zajišťuje "správný počet závorek", páč mi po kadžý iteraci cesty jedny "přebývají".
Map je spravne, ale definicia fold-u ma byt:

Kód: Vybrat vše

fold :: [[a]] -> [a]
Inac velmi pekne riesenie, paci sa mi.
Odpovědět

Zpět na „2005“