Zk 24.1. 2006

[mike04]

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

[Trupik]

Ad 3 - ja myslel, ze ta funkce ma vratit k nejmensich prirozenych cisel, ktere ve vstupnim seznamu NEjsou? Ááá herdek...

[tutchek]

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

co je to fold?

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.)

[mike04]

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...

[mike04]

Ad 3 - ja myslel, ze ta funkce ma vratit k nejmensich prirozenych cisel, ktere ve vstupnim seznamu NEjsou? Ááá herdek...

no sorry, to jsem ve spechu opomel. Je to tak, meli se hledat cisla, ktery tam nejsou.

[Trupik]

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).

[Dawe]

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...

[Necroman]

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

[Almer]

2) Kartezky soucin 2 grafu (bez orientace hran)

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 vrcholy

1) Najdi maximalni nezavislou mnozinu v grafu (nemusi byt nejvetsi mozna)

S tim neporadim...zkusi nekdo jiny

[rastik]

U prikladov s grafom je zadana/pozadovana nejaka konkretna reprezentacia? Alebo si mozem vybrat taku, co mi bude najviac vyhovovat?

[Trupik]

U prikladov s grafom je zadana/pozadovana nejaka konkretna reprezentacia? Alebo si mozem vybrat taku, co mi bude najviac vyhovovat?

Ne, mohli jsme si vybrat. Já měl tu nejprimitivnější - seznam vrcholů + seznam dvojic vrcholů (mezi nimi je hrana)

[Trupik]

OMG , to ze jsou lehke priklady??
Mohl by pls nekdo upresnit to zadani:
1) Najdi maximalni nezavislou mnozinu v grafu (nemusi byt nejvetsi mozna)

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žinu

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

Formálně takhle :
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}

[Dawe]

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ě...

[Tuetschek]

Bylo nejaky omezeni na slozitost tech "lehkych" prikladu?

[mike04]

Bylo nejaky omezeni na slozitost tech "lehkych" prikladu?

Hlavni kriterium bylo, abys to vyresil. Slozitost byla vedlejsi...