IOI - 27.6.2013 - 8:30

Vše co se týká bakalářských státních závěrečných zkoušek.
cre8or
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 26. 1. 2011 10:58
Typ studia: Informatika Mgr.

IOI - 27.6.2013 - 8:30

Příspěvek od cre8or »

1) Definujte limitu fce v bode. Spocitejte:
lim_{n->\infty} {[\sqrt n]  \over \sqrt n}
kde [x] znaci dolni celou cast z x.

2) Definujte nezavislost jevu. Necht pravdepodobnosti prostor je tvoren {001,100,010,111}. Oznacme jev Ai - "Na i-tem miste je 0". Jsou jevy A1, A2 a A3 po dvou nezavisle? Jsou nezavisle vsechny tri?

3) Je Z4 s obvyklou definici scitani a nasobeni teleso? Lze nejak definovat scitani a nasobeni, aby to teleso bylo?

4) Definujte strom, popiste jak souvisi pocet hran s poctem vrcholu. Dokazte, ze kdyz se do stromu prida hrana, vznikly graf bude obsahovat prave jednu kruznici.

5) Definujte CNF. Da se kazda formule zapsat v CNF? Rozlozte formuli A & (B | (C & D)) do CNF.

6) AVL stromy - popsat, popsat vkladani prvku.

7) Definujte vlakno. Mejme nasledujici kod:

Kód: Vybrat vše

class X {
  int value = 0;
  bool locked = false;
  int increment() {
     while (locked);
     locked = true;
     int last = value;
     value++;
     locked = false;
     return last;
   }
}
Rozhodnete, zda se fce increment() bude chovat spravne i pri volani z vice vlaken a pokud ne, tak ji vhodne upravte.

8 ) Co jsou to vyjimky, jak se chovaji. Mejme nasledujici kod:

Kód: Vybrat vše

class X {
    Data read() {
       File f = File.open("file.text");
       Data d = f.readall();
       f.close();
       return d;
    }
}
Prepokladejte, ze kazda metoda muze vyhazovat vyjimku - upravte kod tak, aby je osetroval.

Prubeh byl nasledujici - prijdete tam, s sebou do lavice si smite vzit pouze propisku a piti, a dve a pul hodiny pisete. Potom odevzdate, zhruba 40 minut cekate nez si komise projdou vase reseni a pak si pro vas zacnou chodit. Komisi je nekolik paralelnich, u nas byly 4. Bylo nas tam neco pres 20 a zhruba za 2 hodiny byli vsichni venku. Hloupe je, ze celou tu dobu nesmite pouzivat mobil, nic cist a ani se spolu moc bavit - takze tam tak 2 hodiny clovek zira do stropu. Doporucuju vzit si s sebou neco k jidlu :-).
Jinak samotne zkouseni trvalo tak 10-15 minut - ptaji se doplnkove otazky k tomu co (ne)mate na papire. Ja mel kus jedne otazky spatne, kus jine spatne na papire ale neco jsem vymyslel pri ustnim (diky p. Maresovi :-) ) a s bakalarkou za 1 to byla 1 dohromady. Dulezite je napsat co nejvic na ten papir, i kdyz to neni primo to, na co se ptaji.
Norek
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 22. 12. 2011 21:11
Typ studia: Informatika Bc.

Re: IOI - 27.6.2013 - 8:30

Příspěvek od Norek »

Obor IP to samé, jen místo 5) byla otázka na architektury PC:

a) Načrtněte architekturu počítače (stačí použít "krabičky" CPU, paměti, zařízení, ...) a vysvětlete, jak probíhá komunikace CPU se zařízením, konkrétně jak určí CPU zařízení, se kterým chce komunikovat a jak mu předá příkazy, které má vykonat.
b) Uveďte příklad zařízení, které se vyplatí obsluhovat pomocí přerušení a proč.
c) Uveďte příklad zařízení, kterému se vyplatí poskytnout přístup do paměti (skrze DMA) a proč.

S dojmy a pocity kolegy souhlasím.
malta.x
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 24. 9. 2010 21:37
Typ studia: Informatika Bc.

Re: IOI - 27.6.2013 - 8:30

Příspěvek od malta.x »

Ještě u tý 7) byl místo intu long a bylo mi řečeno, že se mělo odhalit i to, protože se long nikdy nebude inkrementovat atomicky.
Tommassino
Matfyz(ák|ačka) level I
Příspěvky: 35
Registrován: 10. 9. 2009 21:03
Typ studia: Informatika Mgr.

Re: IOI - 27.6.2013 - 8:30

Příspěvek od Tommassino »

malta.x píše:Ještě u tý 7) byl místo intu long a bylo mi řečeno, že se mělo odhalit i to, protože se long nikdy nebude inkrementovat atomicky.
presne tak, dokonce se me na to ptali u ustni, takze to tam opravdu bylo schvalne

Kód: Vybrat vše

  long value = 0;
Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
Příspěvky: 98
Registrován: 22. 9. 2010 16:07
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: IOI - 27.6.2013 - 8:30

Příspěvek od Davpe »

Přikládám moji zkušenost a řešení. Až na ty AVL stromy mi to přišlo opravdu jednoduché.

1) Omezit [\sqrt{n}] pomocí n/2 zdola a n shora a použít strážníky, limita vyjde 1.

2) Jsou po dvou nezávislé, nezávislé nejsou. Definice nezávislosti měla být pro obecně n jevů. Nezapomenout, že se to definuje pro každou k-tici. MJ mi pak říkal že jsem byl jeden z mála kdo to měli dobře (u komise kde jsem byl).

3) Není - dvojka nemá vzhledem k násobení invers. Dodefinovat lze neboť existuje (Galoisovo) těleso velikosti mocnina prvočísla.

4) Využil jsem ekvivalentní definici stromu: Mezi dvěma vrcholy existuje právě jedna cesta. Přidáním jedné hrany pak vznikne (jediná) kružnice.
Pak stačí dokázat jen implikace graf je strom implikuje existenci právě jedné cesty mezi dvěma vrcholy. Důkaz stačí indukcí, přidáním listu v indukčním kroku.

5) Ekvivalentní formule je A & (B | C) & (B | D)
U podotazky zda lze každá formule zapsat do CNF jsme měli vysvětlit proč. Jenom jsem tam převedl základní formule (and, or, implikace, ekvivalence) do cnf.

7) První vlákno projde přes while, než stihne zamknout, přerušení, projde druhé vlákno a uloží last = 0; přerušení, první vlákno uloží last = 0; a value = 1 a opustí increment, druhé vlákno value = 2 a opustí inkrement. Nyní value = 2 ale předchozí hodnota last se rovná 0.

Vyřešil jsem to tak, že jsem nahradil while(busy) na while(test_and_set(busy)) kde test_and_set(busy) otestuje zda je busy false a pokud ano, nastaví ji na true. To všechno atomicky. Napsal jsem že to je aktivní čekání a udělal tam řešení kde jsem přidal lock(mutex) a unlock(mutex).

8) Obalil jsem metody bloky try a v catch zachytil ruzne vyjimky. Ve finally bloku jsem napsal {f.close()}. Jeste tam byla podotazka jak by se to resilo bez konstrukce finally a jaky je mezi tim rozdil.

U AVL stomů jsem měl jen definici a zhruba jak se vkládá (což určitě nebylo dobře) a neměl jsem tam žádnou rotaci. Co je vlákno a vyjimka (a nejake podotazky k tomu) jsem popsal hodně nepřesně a lidsky (a hloupě).

Komise (Nečaský, Valtr, Mareš, Kopecký) mi oznámila že matika celá v pohodě. Pak se mě ptala na AVL stromy kde jsem jim hned řekl že to nevymyslím. Dále se mě ptali na to že mám ve finally f.close() a co kdyby se soubor neotevřel. Moje odpověď že v Céčku přece nevadí když zavírám otevřený soubor je moc neuspokojila. Netuším co chtěli slyšet.
Závěrem docela překvapivě za 1. Když jsem se pak MJe ptal proč mi nedali horší známku za ty AVL stromy tak mi opověděl že prý věděli že bych to tak do půl hodiny s jejich pomocí vymyslel a že se jim tím nechtělo ztrácet čas :D (kamarád u jiné komise dostal za chybé rotace za 2 a já tam rotace neměl vůbec). Komise byla opravdu skvělá a hodná, dokonce dopoledne tahle komise ani nikoho nevyhodila.

A ještě bych chtěl dodat, že před rozdáním zadání nás upozorňovali, že kdybychom v zadání dostali něco co nebylo v požadavcích na státnice tak se máme okamžitě ozvat a vyřeší se to.
Naposledy upravil(a) Davpe dne 30. 6. 2013 09:45, celkem upraveno 1 x.
malta.x
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 24. 9. 2010 21:37
Typ studia: Informatika Bc.

Re: IOI - 27.6.2013 - 8:30

Příspěvek od malta.x »

Tak taky přidám zkušenost s jinou komisí - Šámal, Majerech, Hnětynka, Hoksza

1) jsem měl ok a Šámal se jen ptal, jak by se definice dala upravit, aby fungovala i v nekonečnu - řekl jsem jen, jak vypadá okolí nekonečna a víc se neptal

2) napsal jsem definici dvou jevů, nezávislost n po dvou a pak i tu pro n - tam jsem napsal, že jsou nezávislé, když každá jejich podmnožina je nezávislá a za to napsal to s tim jejich průnikem, že se rovná psti jejich součinu - v tom se Šámal vrtal a říkal mi, že je to kruhová definice - nejdřív jsem proto vůbec nechápal, co vlastně chce - ale asi byl zakopán pes jenom v tom, že ten vztah psti průniku a součinu pokračoval až na dalším řádku. Ale odešlo se od toho s tím, že jsme se snad nějak domluvili.

Pak jsem úplně přesně nepochopil, jak zadání myslí ty jevy, takže jsem napsal různý možnosti a komentoval je slovně, tam jsme se chvíli domlouvali, jak se to teda mělo pochopit.

3) opravoval Majerech - byla tam napsána jako na jedinym známka - 1. Řekl mi, že ok. U GF jsem napsal, že bude navíc komutativní i díky Wedderburnově větě, tak ho zajímalo, kde jsme tuhle větu brali :D. Ještě jestli vím, jak přesně GF vypadá - no, o polynomech jsem se zmínil, ale přesně bych nevěděl - to ale snad moc nevadilo.

4) napsal jsem několik těch definic, vztah a důkaz psal spíš slovně - Šámal to chtěl podložit nějakým hlubším tvrzením - jakým? To netušim.

5) u toho převodu jsem se jednou překouk a napsal místo D znova C, takže mi prostě D zmizelo, ale to snad Hnětynka vzal. Taky jsem napsal, jak se převádí - deMorganovy pravidla, implikaci a tak. + jsem se ještě zmínil o Karnaughových mapách

6) AVL - všechny rotace jsem fakt nevěděl, měl jsem správně definici, nějaký vlastnosti a u insertu jednu rotaci - opravoval to Hoksza, tak se jen ptal, proč tam nemám další rotace, co je to vlastně vyhledávací strom a jak vysoko se musí propagovat změna. Navíc jsem k tomu ještě připsal i jak vypadaj červenočerný stromy, abych trochu vyplnil místo na papíře.

7) taky jsem napsal tsl a mutex, připsal případně monitor. Psal jsem, jak vypadá proces, vlákna a tak - měl jsem asi stránku a půl. Hnětynka na to řekl, že je to je pravda, co tam mám a ptal se, jestli jdou vlákna udělat bez podpory OS. Pak se ale vrhnul na to, že to přeci není všechno, co jsme měli odhalit, takže se ještě řešil ten long.

8 ) to byla pro mě hodně špatná otázka. Vysvětlovat na konkrétním jazyce výjimky jsem na IOI nečekal. Chodil jsem jen na C++, na cvikách jsme si o nich řekli, ale nijak se necvičily, ani jsem je nikdy jinak nepoužíval. Takže jsem byl za sebe rád, že jsem aspoň obalil metody try a catch a napsal slovně, jak to zhruba funguje. Co je to finally jsem netušil, ani jsem to nikdy neslyšel. Hnětynka se na to mrknul a řeknul, že pomocí try catch to jde, ale že to bych musel mít všude a finally nemám vůbec - vyhodnotil to jako zcela nezodpovězenou otázku.

Po poradě jsem odešel s trojkou a byl jsem rád. Strávil jsem tam docela dost času a bylo mi řečeno, že poslední otázka nebyla vůbec a past byla skoro na hraně, tudíž i vzhledem k 1 z bakalářky, dostanu 3 celkově. Co jsem slyšel od ostatních, byly jiný komise hodnější, takže nepotřebujete jen štěstí na otázky, ale i štěstí na komisi.
J4rd4
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 14. 4. 2011 10:54
Typ studia: Informatika Mgr.

Re: IOI - 27.6.2013 - 8:30

Příspěvek od J4rd4 »

Davpe píše:1) Omezit [\sqrt{n}] pomocí n/2 zdola a n shora a použít strážníky, limita vyjde 1.
Nechci prudit, ale ten spodní policajt je špatně. Např. při n=16 neplatí, že dolní celá část odmocniny je větší než polovina.
Já jsem si výraz [\sqrt{n}] omezil zdola výrazem \sqrt{n} - 1, díky čemuž se dá pak celý výraz v dolní limitě rozložit na dva zlomky a pak krásně limitovat k jedné.

To jen tak pro příští generace k procvičení...
Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
Příspěvky: 98
Registrován: 22. 9. 2010 16:07
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: IOI - 27.6.2013 - 8:30

Příspěvek od Davpe »

J4rd4 píše:ten spodní policajt je špatně.
I kdepak, není :) (mimochodem, pak by musel být špatně i horní policajt - pro n = 2).

V limitách posloupnosti často na prvních konečně mnoha členech nezáleží. A abych nemluvil do prázdna, tak jsem si otevřel poznámky přednášejícího z analýzy - věta 2.7.
Věta o strážnících píše: Nechť (a_n), (b_n), (c_n) jsou posloupnosti splňující:
1. \exists n_0 \in N \ \forall n_0 \in N, n \geq n_0: a_n \leq c_n \leq b_n,
2. \lim a_n = \lim b_n = A \in R
Pak \lim c_n = A.
V první podmínce požadujeme aby nerovnost třech posloupností byla splněna až od jistého indexu n_0. V tomto případě stačí položit třeba n_0=36. Takže je to skutečně korektní (v odkazovaných poznámkách je dokonce tentýž příklad uveden jako příklad k této větě o strážnících ;))
J4rd4 píše:Já jsem si výraz [\sqrt{n}] omezil zdola výrazem \sqrt{n} - 1, díky čemuž se dá pak celý výraz v dolní limitě rozložit na dva zlomky a pak krásně limitovat k jedné.
Dva zlomky a ještě tam někde pobíhá odmocnina? Brrr...krása je skutečně relativní! ;)
J4rd4 píše:To jen tak pro příští generace k procvičení...
Copy that.
Uživatelský avatar
emu
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 24. 1. 2011 16:24
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: IOI - 27.6.2013 - 8:30

Příspěvek od emu »

Davpe, cože?
Vždyť se ten policajt liší v řádu. Odhadnout odmocninu zdola lineární funkcí přece nejde. Pro jakoukoliv funkci ax bude pro x od 1/a2 výše ta odmocnina menší. Dolní celá část jí s tím určitě nepomůže.
Druhak, limita n/(n/2) je 2, nebo mi snad něco uniká? Ale výsledek toho příkladu má být opravdu 1. J4rdův postup je ten, co jsme si tehdy před lety ukazovali na cvičení.
Když mám zajímavý podpis, nepotřebuju psát zajímavé věci do těla zprávy.
Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
Příspěvky: 98
Registrován: 22. 9. 2010 16:07
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: IOI - 27.6.2013 - 8:30

Příspěvek od Davpe »

emu píše:Davpe, cože?
Vždyť se ten policajt liší v řádu. Odhadnout odmocninu zdola lineární funkcí přece nejde.
Ééé, no jasně už to vidím, jsem úplně mimo. Díky oboum za opravení a nakopnutí, jdu si sypat popel na hlavu. (Jinak na papírech jsem měl naštěstí i postup který sem psal jarda, takže tenhleten nesmysl se nejspíš rozhodli ignorovat)
Odpovědět

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