Zk 24.1. 2006
-
- Donátor
- Příspěvky: 79
- Registrován: 23. 9. 2004 12:00
- Typ studia: Informatika Mgr.
- Bydliště: Děčín/ Praha
- Kontaktovat uživatele:
Zk 24.1. 2006
Zkouska ma dve casti - 4 "lehke" priklady - cas: 60 min
1 velky priklad - cas: 90 min
Veskera zadani nam psal na tabuly, takze nez dopsal posledni ze 4 lehkyh prikladu, mohl uz nekdo mit 1 priklad hotov. Dale je cas se ptat na zadani. Pote nastavi priblizne tech 60 minut.
Po 4 lehkych prokladch je 5 minut pauza. Pote opet napise zadani velkeho prikladu.
Nase priklady:
Lehke - prolog
1) Najdi maximalni nezavislou mnozinu v grafu (nemusi byt nejvetsi mozna)
2) Kartezky soucin 2 grafu (bez orientace hran)
Lehke Haskell:
3) Najdi k nejmensich cisel v seznamu prirozenych cisel. (seznam neni setrizen. Lze predpokladat, ze se tam prvky neopakuji)
4) data T12 a= Nil
|N1 a (T12 a )
|N2 a (T12 a ) (T12 a )
pro tento strom napis fold a pomoci funkce fold napis funkci pro vypsani hodnot z vrcholu typu (N2 a b c) jako seznam (v preorder)
Tezky priklad:
Je dan seznam strojovych instrukci, pro nektere z instrukci je dan casovy odstup mezi nimi i a j -> r(i,j) a J(i,j) - jestli je mozne instukce i a j prohodit (nemusi platit ze J(i,j) = J(j,i) )
Pricemz nejmensi odstup mezi 2 instrukcemi je nejmene 1 a procesor zvladne zacit nejvyse 1 instrukci za cyklus.
Ukol je nalezt posloupnost instrukci, ktera bude nejrychleji zpracovana v procesoru. Instrukci priradit cas, kdy se dostane na radu.
K tezkemu prikladu dodal, ze nemusi byt supr efektivni.. Hlavne abychom ho zvladli napsat...
Pro vysledku se chodi odpoledne - cas urci, pri odevzdani tezkeho prikladu
1 velky priklad - cas: 90 min
Veskera zadani nam psal na tabuly, takze nez dopsal posledni ze 4 lehkyh prikladu, mohl uz nekdo mit 1 priklad hotov. Dale je cas se ptat na zadani. Pote nastavi priblizne tech 60 minut.
Po 4 lehkych prokladch je 5 minut pauza. Pote opet napise zadani velkeho prikladu.
Nase priklady:
Lehke - prolog
1) Najdi maximalni nezavislou mnozinu v grafu (nemusi byt nejvetsi mozna)
2) Kartezky soucin 2 grafu (bez orientace hran)
Lehke Haskell:
3) Najdi k nejmensich cisel v seznamu prirozenych cisel. (seznam neni setrizen. Lze predpokladat, ze se tam prvky neopakuji)
4) data T12 a= Nil
|N1 a (T12 a )
|N2 a (T12 a ) (T12 a )
pro tento strom napis fold a pomoci funkce fold napis funkci pro vypsani hodnot z vrcholu typu (N2 a b c) jako seznam (v preorder)
Tezky priklad:
Je dan seznam strojovych instrukci, pro nektere z instrukci je dan casovy odstup mezi nimi i a j -> r(i,j) a J(i,j) - jestli je mozne instukce i a j prohodit (nemusi platit ze J(i,j) = J(j,i) )
Pricemz nejmensi odstup mezi 2 instrukcemi je nejmene 1 a procesor zvladne zacit nejvyse 1 instrukci za cyklus.
Ukol je nalezt posloupnost instrukci, ktera bude nejrychleji zpracovana v procesoru. Instrukci priradit cas, kdy se dostane na radu.
K tezkemu prikladu dodal, ze nemusi byt supr efektivni.. Hlavne abychom ho zvladli napsat...
Pro vysledku se chodi odpoledne - cas urci, pri odevzdani tezkeho prikladu
- Trupik
- Matfyz(ák|ačka) level III
- Příspěvky: 251
- Registrován: 3. 1. 2005 14:45
- Typ studia: Informatika Mgr.
- Kontaktovat uživatele:
Ad 3
Ad 3 - ja myslel, ze ta funkce ma vratit k nejmensich prirozenych cisel, ktere ve vstupnim seznamu NEjsou? Ááá herdek...
Domovská stránka: http://www.jakubmaly.cz/, blog: http://blog.jakubmaly.cz/
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
- tutchek
- Site Admin
- Příspěvky: 795
- Registrován: 21. 9. 2004 00:40
- Typ studia: Informatika Mgr.
- Login do SIS: tulam4am
- Bydliště: Praha, Bohnice
- Kontaktovat uživatele:
Re: Zk 24.1. 2006
co je to fold?mike04 píše:Zkouska ma dve casti - 4 "lehke" priklady - cas: 60 min
1 velky priklad - cas: 90 min
Veskera zadani nam psal na tabuly, takze nez dopsal posledni ze 4 lehkyh prikladu, mohl uz nekdo mit 1 priklad hotov. Dale je cas se ptat na zadani. Pote nastavi priblizne tech 60 minut.
Po 4 lehkych prokladch je 5 minut pauza. Pote opet napise zadani velkeho prikladu.
Nase priklady:
Lehke - prolog
1) Najdi maximalni nezavislou mnozinu v grafu (nemusi byt nejvetsi mozna)
2) Kartezky soucin 2 grafu (bez orientace hran)
Lehke Haskell:
3) Najdi k nejmensich cisel v seznamu prirozenych cisel. (seznam neni setrizen. Lze predpokladat, ze se tam prvky neopakuji)
4) data T12 a= Nil
|N1 a (T12 a )
|N2 a (T12 a ) (T12 a )
pro tento strom napis fold a pomoci funkce fold napis funkci pro vypsani hodnot z vrcholu typu (N2 a b c) jako seznam (v preorder)
Tezky priklad:
Je dan seznam strojovych instrukci, pro nektere z instrukci je dan casovy odstup mezi nimi i a j -> r(i,j) a J(i,j) - jestli je mozne instukce i a j prohodit (nemusi platit ze J(i,j) = J(j,i) )
Pricemz nejmensi odstup mezi 2 instrukcemi je nejmene 1 a procesor zvladne zacit nejvyse 1 instrukci za cyklus.
Ukol je nalezt posloupnost instrukci, ktera bude nejrychleji zpracovana v procesoru. Instrukci priradit cas, kdy se dostane na radu.
K tezkemu prikladu dodal, ze nemusi byt supr efektivni.. Hlavne abychom ho zvladli napsat...
Pro vysledku se chodi odpoledne - cas urci, pri odevzdani tezkeho prikladu
slovniky.atlas.cz píše:fold: církev; přen., dát se složit, do sebe zapadat, falcovat, fald (tuku apod.), kotlina (v horách), lom (ohyb), ohyb (lom), ovčinec (církev); přen., ovčinec (ohrada pro ovce), ovinout (plachty), přehnout, zkrachovat; hovor., přestat vycházet (časopis), přitisknout, přivinout (plachty), rýha (geol.), salaš, sevřít (v náručí), složit (přehnutím zmenšit), stádo ovcí, svinout (plachty), zahnout, záhyb, zavírat se, vrása (rýha) (geol.), záhyb (plica) (med.), řasa (gyn.), zřasit, složit do záhybů (med.)
exAdmin. Magistr přes umělou inteligenci. Právník přes daně.
-
- Donátor
- Příspěvky: 79
- Registrován: 23. 9. 2004 12:00
- Typ studia: Informatika Mgr.
- Bydliště: Děčín/ Praha
- Kontaktovat uživatele:
v tomto pripade byla fold definovana takto:
fold::b->(a->b->b)->(a->b->b->b)->T12 a->b
b nahradi vrcholy konstruovane Nil
na vrchol s konstruktorem N1 a (T12 a) zavola funkci (a->b->b)
a na N2 a (T12 a) (T12 a) zavola funkci (a->b->b->b)
cele se to vola rekurzivne
Kdyz jsme se ho ptaly taky, tak uvedl, ze je to funkce z prednasky...
Jeste ze jeden chytry clovek si ji pamatoval, a rekl, ze na prednasce byla definovana jinak, takze nam k tomu rekl trochu vic...
fold::b->(a->b->b)->(a->b->b->b)->T12 a->b
b nahradi vrcholy konstruovane Nil
na vrchol s konstruktorem N1 a (T12 a) zavola funkci (a->b->b)
a na N2 a (T12 a) (T12 a) zavola funkci (a->b->b->b)
cele se to vola rekurzivne
Kdyz jsme se ho ptaly taky, tak uvedl, ze je to funkce z prednasky...
Jeste ze jeden chytry clovek si ji pamatoval, a rekl, ze na prednasce byla definovana jinak, takze nam k tomu rekl trochu vic...
-
- Donátor
- Příspěvky: 79
- Registrován: 23. 9. 2004 12:00
- Typ studia: Informatika Mgr.
- Bydliště: Děčín/ Praha
- Kontaktovat uživatele:
Re: Ad 3
no sorry, to jsem ve spechu opomel. Je to tak, meli se hledat cisla, ktery tam nejsou.Trupik píše:Ad 3 - ja myslel, ze ta funkce ma vratit k nejmensich prirozenych cisel, ktere ve vstupnim seznamu NEjsou? Ááá herdek...
- Trupik
- Matfyz(ák|ačka) level III
- Příspěvky: 251
- Registrován: 3. 1. 2005 14:45
- Typ studia: Informatika Mgr.
- Kontaktovat uživatele:
Heh, tak Kuba to má. Po napsané písemce vás čeká ještě různě dlouhá disputace nad řešením. Krátké příklady má opravené, na velký se nejspíš vůbec nedíval - takže mi řekl "Tak mi povezte, ako ste to robil". Tak jsem mu to povedel, řekl, že moje řešení nieije příliš vhodné, ale odpustil mi to a za jedna (v malejch příkladech prej chyby nenašel).
Jinak ten velkej jsem dělal tak, že jsem si každý nalezený řešení uložil do databáze a po prolezení všech jsem vybral nejlepší - ukládáním do databáze se mi všechno náramně zjednodušilo, ale asi to není ta pravá prologovina.
V celku je asi jedno, jak kterej příklad vyřešíte - hlavně, že to máte, s efektivitou si není třeba lámat hlavu.
Podle mě to bylo o poznání lehčí, než písemky, které jsou na fearu, ale možná časem přitvrdí (užitesi).
Jinak ten velkej jsem dělal tak, že jsem si každý nalezený řešení uložil do databáze a po prolezení všech jsem vybral nejlepší - ukládáním do databáze se mi všechno náramně zjednodušilo, ale asi to není ta pravá prologovina.
V celku je asi jedno, jak kterej příklad vyřešíte - hlavně, že to máte, s efektivitou si není třeba lámat hlavu.
Podle mě to bylo o poznání lehčí, než písemky, které jsou na fearu, ale možná časem přitvrdí (užitesi).
Domovská stránka: http://www.jakubmaly.cz/, blog: http://blog.jakubmaly.cz/
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
- Dawe
- Supermatfyz(ák|ačka)
- Příspěvky: 360
- Registrován: 12. 10. 2004 12:32
- Typ studia: Informatika Mgr.
- Bydliště: Doma a nebo na koleji
taky mám
Já jsem se k tomu čtvrtýnu příkladu ani nedostal, ale ty tři jsem měl dobře.Jen po mně chtěl zoptimalizovat to.Pak se dostalo na velkej příklad a to byl trochu problé, spíš jsem popsal jakto řešit, než abych to programoval. Zvolil jsem ale asi dost přesné řešení a tudíž dost složité. Chtěl tam po mně, abych mu vymyslel (napsal v kódu) jak budu přesně dělat nějaký kroky mýho alg. No nakonec se mi to víceméně podařilo, ale docela mně to stálo úsilý. Řekl mi, že OK, ale za to že sem mu to vymyslel až tam, tak že za 2. Jsem nad míru spokojenej a hlavně rád že to mám za sebou.
Jo ještě dodatek, původně tam plánoval dát místo k.součinu převést DNF na KNF (nebo naopak?).Ale když zjistil, že nikdo moc netuší, co to je, tak tam dal ten součin - myslím že i to docela helplo...
Přeji všem hodně zdaru nejen u NP
Ještě k výsledkům - co jsemmu do toho koukal tak většinou 1,2, někdy 3, 4 asi jen jedna. Teda byl jsem tam asi v půlce, takže jak se to vyvíjelo dál nevím...
Jo ještě dodatek, původně tam plánoval dát místo k.součinu převést DNF na KNF (nebo naopak?).Ale když zjistil, že nikdo moc netuší, co to je, tak tam dal ten součin - myslím že i to docela helplo...
Přeji všem hodně zdaru nejen u NP
Ještě k výsledkům - co jsemmu do toho koukal tak většinou 1,2, někdy 3, 4 asi jen jedna. Teda byl jsem tam asi v půlce, takže jak se to vyvíjelo dál nevím...
- Necroman
- Supermatfyz(ák|ačka)
- Příspěvky: 459
- Registrován: 20. 1. 2005 19:46
- Typ studia: Informatika Mgr.
- Login do SIS: suchm4am
- Bydliště: Louny / kolej Jednota, Praha
- Kontaktovat uživatele:
Re:
OMG , to ze jsou lehke priklady??
Mohl by pls nekdo upresnit to zadani:
1) Najdi maximalni nezavislou mnozinu v grafu (nemusi byt nejvetsi mozna)
2) Kartezky soucin 2 grafu (bez orientace hran)
Podle toho nemam paru, co se po me vubec chce...
...asi jsem to kapku podcenil... jdu se ucit
Mohl by pls nekdo upresnit to zadani:
1) Najdi maximalni nezavislou mnozinu v grafu (nemusi byt nejvetsi mozna)
2) Kartezky soucin 2 grafu (bez orientace hran)
Podle toho nemam paru, co se po me vubec chce...
...asi jsem to kapku podcenil... jdu se ucit
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
- Almer
- Site Admin
- Příspěvky: 686
- Registrován: 12. 10. 2004 10:58
- Typ studia: Informatika Ph.D.
- Login do SIS: lasap4am
- Bydliště: Mala Strana - 203
- Kontaktovat uživatele:
Re:
Vezmes si mnozinu vrcholu jednoho grafu, a mnozinu vrcholu druheho. Provedes KS na techto mnozinach (vynasobis vse se vsim) a dostanes novou mnozinu vrcholu, kde plati, ze existuje hrana, pokud existovala mezi obema dvojicema vrcholu, ktere tedka tvori ty dva nove vrcholy2) Kartezky soucin 2 grafu (bez orientace hran)
S tim neporadim...zkusi nekdo jiny1) Najdi maximalni nezavislou mnozinu v grafu (nemusi byt nejvetsi mozna)
Zakládající člen klubu Ortodoxních Matfyzáků
Jsem LAMER ale neumim se ani podepsat ]
Jsem LAMER ale neumim se ani podepsat ]
- Trupik
- Matfyz(ák|ačka) level III
- Příspěvky: 251
- Registrován: 3. 1. 2005 14:45
- Typ studia: Informatika Mgr.
- Kontaktovat uživatele:
Ne, mohli jsme si vybrat. Já měl tu nejprimitivnější - seznam vrcholů + seznam dvojic vrcholů (mezi nimi je hrana)rastik píše:U prikladov s grafom je zadana/pozadovana nejaka konkretna reprezentacia? Alebo si mozem vybrat taku, co mi bude najviac vyhovovat?
Domovská stránka: http://www.jakubmaly.cz/, blog: http://blog.jakubmaly.cz/
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
- Trupik
- Matfyz(ák|ačka) level III
- Příspěvky: 251
- Registrován: 3. 1. 2005 14:45
- Typ studia: Informatika Mgr.
- Kontaktovat uživatele:
Re:
vypadá to složitě, ale je to jednoduché: postupně bereš vrcholy a přidáváš je do množiny, přidat ho můžeš, jen jestli není spojen s žádným vrcholem, který již v množině je. Až probereš věechny vrcholy, máš požadovanou mnnožinuNecroman píše: OMG , to ze jsou lehke priklady??
Mohl by pls nekdo upresnit to zadani:
1) Najdi maximalni nezavislou mnozinu v grafu (nemusi byt nejvetsi mozna)
Formálně takhle :Necroman píše: 2) Kartezky soucin 2 grafu (bez orientace hran)
Podle toho nemam paru, co se po me vubec chce...
...asi jsem to kapku podcenil... jdu se ucit
G1 = (V1, H1),
G2 = (V2, H2),
G3 = (V3, H3),
V3 = V1 x V2,
H3 = {((u1, v1)(u2,v2)) | u1, u2 z V1, v1, v2 z V2, (u1,u2) je v H1, (v1, v2) je v H2}
Naposledy upravil(a) Trupik dne 25. 1. 2006 13:38, celkem upraveno 1 x.
Domovská stránka: http://www.jakubmaly.cz/, blog: http://blog.jakubmaly.cz/
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
- Dawe
- Supermatfyz(ák|ačka)
- Příspěvky: 360
- Registrován: 12. 10. 2004 12:32
- Typ studia: Informatika Mgr.
- Bydliště: Doma a nebo na koleji
reprezentace
Nic o reprezentaci neříkal, takže jsem zvolil seznam dvojic vrcholů = hrany. Díky této reprezentaci se oba příklady na grafy řeší docela jednoduše.
1) - znamená to že je to množina vrcholů, kde žádné dva vrcholy z množiny nejsou spojeny hranou. Maximální je tehdy, když už nelze zvětšit. že nemusí být ta největší znamená, že může existovat jiná (jiné vrcholy) která je větší.
řešení: jednoduše se vezme libovolný vrchol a přidávají se další, pokud s těmi z množiny nemají žádnou hranu. Udělal jsem si seznam vrcholů, a z něho postupně bral vrcholy, a přidával je pokud neležely na hraně s žádným vrcholem ze stávající množiny.
2)Jsou dva seznamy dvojic[(a,b)...], [(c,d)...]
a pro každé dvě takové dvojice se vytvoří [(a,c),(a,d),(b,c),(b,d)], pak se seznam sleje s ostatnímy sznamy...
Doufám, že jsem to napsal aspoň trochu pochopitelně...
1) - znamená to že je to množina vrcholů, kde žádné dva vrcholy z množiny nejsou spojeny hranou. Maximální je tehdy, když už nelze zvětšit. že nemusí být ta největší znamená, že může existovat jiná (jiné vrcholy) která je větší.
řešení: jednoduše se vezme libovolný vrchol a přidávají se další, pokud s těmi z množiny nemají žádnou hranu. Udělal jsem si seznam vrcholů, a z něho postupně bral vrcholy, a přidával je pokud neležely na hraně s žádným vrcholem ze stávající množiny.
2)Jsou dva seznamy dvojic[(a,b)...], [(c,d)...]
a pro každé dvě takové dvojice se vytvoří [(a,c),(a,d),(b,c),(b,d)], pak se seznam sleje s ostatnímy sznamy...
Doufám, že jsem to napsal aspoň trochu pochopitelně...