IOI 8.9.2011 (odpolední skupina)

Vše co se týká bakalářských státních závěrečných zkoušek.
Kubees
Matfyz(ák|ačka) level II
Příspěvky: 65
Registrován: 12. 1. 2007 22:22
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

IOI 8.9.2011 (odpolední skupina)

Příspěvek od Kubees »

Pridavam zadani odpoledni skupiny:

1. Grafove algoritmy
- definujte strom
- definujte korenovy strom
- kolik je korenovych stromu na 9 vrcholech?
- kolik je korenovych stromu na n vrcholech?

Jak jsem pochopil ze suskani za mnou, tak jsem nebyl jediny, kdo pojem "korenovy strom" slysel poprve v zivote :D Nicmene dalo se spravne tipnout ze je to strom kde jeden vrchol oznacime za koren. (a nastesti jsem si tipnul zrovna tohle, vahal jsem, strilel jsem od boku :) ) Na n vrcholech jich je n^(n-1), viz pocet koster uplneho grafu.

2. Diferencialni pocet
- definujte Tayloruv polynom
- navrhnete postup na priblizny vypocet sin(5) pomoci TP

Pohoda, rozvoj v nule, dosadit 5 a je to. Na ustni Cepek trochu vrtal do tvaru zbytku a prisel se na to ze ho neumim, ale presel to bez karani jen slovy "podle me to neni ono" a slo se dal.

3. Vektorove prostory
- definujte skalarni soucin, rozeberte pripad realnych i komplexnich vektoru
- definujte normu vektoru
- dokazte, ze ||x+y|| <= ||x||+||y||

I kdyz jsem se SS (trochu)ucil, tak me docela zarazil ten dukaz trojuhelnikove nerovnosti, protoze pomoci ni jsem definoval normu (mozna chteli definici normy pres skalarni soucin) Tak jsem napsal aspon CSB-nerovnost. Na usni se pak Hladik ptal jestli to umim dokazat a ze tam mam jen CSB-nerovnost, tak jsem aspon strelil od bodku, ze to je proto, ze CSB-nerovnost se v tom dukazu pouzije, coz mi odkyval a slo se dal.

4. Logika
- definujte pojmy tautologie, splnitelnost, dokazatelnost (vyrokova logika)
- jaky je vztah mezi tautologii a splnitelnou formuli?
- uvedte netrivialni priklady obou vyse zminenych

...za takovou otazku bych se pomalu stydel i u maturity :lol:

5. ADS
- popiste algoritmus insersort, proc je vhodne pouzivat ho na predtridene pole?
- popiste algoritmus quicksort, jak zavisi jeho slozitost na vyberu pivota?

Tak insertsort jsem se pokousel vycucat z prstu coz mi vubec neslo, takze jsem po 20 ztracenych minutach rezignoval a cesky ho okecal ze se tam vkladaji prvky do pole a ty vetsi se posouvaji doprava (doted nevim jak to je), ale komise byla moc hodna a presla to jako ze to mam spravne. Na ustni se zajmali i o pametovou slozitost, kterou jsem na papire vubec neresil, ale to jsem uhadl ze oba algoritmy se daji resit v jednom poli, takze n.

6. Databaze
- co je to transakce, co jsou vlastnosti ACID?
- popiste dvoufazovy zamykaci protokol
- necht T1,T2 jsou transakce: T1: read(x), write(y=x+1) T2: read(y), write(x=t+1). Popiste jejich beh pri dvoufazovem zamykacim protokolu

U zamykaciho protokolu stacilo napsat ze spociva ve fazi pridelovani zamku a vraceni zamku, ze transakce ktera jednou vrati zamek uz zadny nedostane.
Vic jsem nevedel, ale pan Hnetnyka me dokopal ke spravne odpovedi, ze se ty transakce serializuji za sebe, aby nevznikl deadlock. (na papir jsem nakreslil krasny deadlock :) )

Kdyz jsem sel na ustni, tak jsem daval tak 60% tomu, ze me vykopnou, jelikoz u 1. jsem neznal definici, u 3. jsem netusil tu nerovnost u 5. jsem algoritmus cucal z prsu a u 6. jsem si kreslil nejake schema uplne od boku aniz bych vedel, co se po me chce. Nakonec to ale dobre dopadlo a po kratke porade komise mi dali s odrenyma usima za 1 8)

Jinak dojmy k postupu:
1. I kdyz nevite, nevzdavejte, zkuste neco vypotit a strilet od boku, horsi nez prazdny papir to urcite nebude, a muze to vyjit! :wink:
2. Napiste i veci na ktere se primo neptaji, ale s otazkou uzce souvisi, u ustni mi to pochvalne odkyvali a urcite to bylo +
3. Pokud vam zbyva malo casu na uceni, tak podle me je lepsi naucit se otazky tady z fora, nez prochazet podrobne latku. Od doby co je zkouska pisemna se otazky dost opakuji. :)

GL vsem pristim generacim.
BTW Letos se mi zda ze ty statnice fakt zmirnili, asi se rozhodli ze nechteji tolik vyhazovat lidi co dosli az sem. :)
Sylverlinn

Re: IOI 8.9.2011 (odpolední skupina)

Příspěvek od Sylverlinn »

Lidimarja, já tam měl jít dneska odpoledne :D tohle zadáni chci!

/Tum tu dum. Zbývá 9 hodin, 31 minut./
pjn

Re: IOI 8.9.2011 (odpolední skupina)

Příspěvek od pjn »

pro obor IP tam bylo misto logiky:

int* ptr = null;

void Producent()
{
int data = SomeCoplexOperation();
ptr = &data;
}

void Consumer()
{
while(ptr == null) { }
printf("%i
",&ptr);
}


Definujte rozhrani semaforu a jeho semantiku.
Dale predpokladejme, ze cteni a prirazeni do promene ptr jsou atomicke, potom stale tento kod obsahuje race condition.
Urcete kde k ni dochazi, a opravte ji pomoci semaforu (ci jinak). Fce Consumer a Producer jsou spusteny prave jednou
kazda z jineho vlakna.
blabla
Matfyz(ák|ačka) level II
Příspěvky: 70
Registrován: 27. 1. 2010 23:14
Typ studia: Informatika Mgr.

Re: IOI 8.9.2011 (odpolední skupina)

Příspěvek od blabla »

je uz trosku neskoro tak mi az tak nezapaluje, ale je tam ta race condition kvoli tomu, ze do ptr davame adresu lokalnej premennej ata moze byt uz odalokovana v dobe ked chce ku ptr pristupovat consumer?

a mozne riesenie by mohlo byt:

Kód: Vybrat vše

int* ptr = null;
int semaphore = 0;

void Producent()
{
int data = SomeCoplexOperation();
ptr = &data;
down(semaphore);
}

void Consumer()
{
while(ptr == null) { }
printf("%i
",&ptr);
up(semaphore);
}
?
pjn

Re: IOI 8.9.2011 (odpolední skupina)

Příspěvek od pjn »

blabla píše:je uz trosku neskoro tak mi az tak nezapaluje, ale je tam ta race condition kvoli tomu, ze do ptr davame adresu lokalnej premennej ata moze byt uz odalokovana v dobe ked chce ku ptr pristupovat consumer?

a mozne riesenie by mohlo byt:

Kód: Vybrat vše

int* ptr = null;
int semaphore = 0;

void Producent()
{
int data = SomeCoplexOperation();
ptr = &data;
down(semaphore);
}

void Consumer()
{
while(ptr == null) { }
printf("%i
",&ptr);
up(semaphore);
}
?
jj, je to presne tak
no v tom reseni se to podle me odalokuje uplne stejne ne ?, metoda Producent skonci, a pak se zavola ten Consumer a ta promena uz davno nebude ....
blabla
Matfyz(ák|ačka) level II
Příspěvky: 70
Registrován: 27. 1. 2010 23:14
Typ studia: Informatika Mgr.

Re: IOI 8.9.2011 (odpolední skupina)

Příspěvek od blabla »

no ale odalokovanie sa deje az ked predsa skonci telo procedury a to nemoze skoncit kym si consumer neprecita hodnotu pointera, nakolko na zaciatku je semafor nastaveny na nulu a tak down(semaphore) v tele producent uspi tuto proceduru/vlakno az kym sa nezavola up(semaphore) v tele consumer po precitani ptr
hmfg

Re: IOI 8.9.2011 (odpolední skupina)

Příspěvek od hmfg »

Neznám pravda správnou odpověď a v případě chyby, kterou popisujete, se mi zdá, že to až tak nesouvisí s problémem producent-konzument, jak by mělo. Každopádně mi Bulej řekl, že jsem nenapsal to, co by tam mělo být a že tam byla chyba s tím "zásobníkem". Neměl jsem chuť se ho ptát na detaily, takže mi z toho zůstalo opravdu jen to klíčové slovo zásobník a moc jsem nechápal, co tam s ním chce řešit. Spíš mi připadlo, že má deadlock v hlavě a potřeboval by semafor :D
pjn

Re: IOI 8.9.2011 (odpolední skupina)

Příspěvek od pjn »

blabla píše:no ale odalokovanie sa deje az ked predsa skonci telo procedury a to nemoze skoncit kym si consumer neprecita hodnotu pointera, nakolko na zaciatku je semafor nastaveny na nulu a tak down(semaphore) v tele producent uspi tuto proceduru/vlakno az kym sa nezavola up(semaphore) v tele consumer po precitani ptr
jo jo, mas pravdu nejako sem si nevsim ze tam je ta inicializace semaphore = 0;
Odpovědět

Zpět na „Bakalářské SZZ“