IOI - 27.6.2013 - 11:30

Limita funkce

1. Definujte limitu funkce

2. Spocitejte $\lim_{x \to \infty} \frac{n + \sqrt{n}}{n - \sqrt{n}}$, pokud existuje.

Zobrazeni

1. Definujte, kdy je zobrazeni proste.

2. Definujte, kdy je zobrazeni na.

3. Mejme mnoziny X = {1,2,3} a Y = {1,2,3,4,5}. Rozhodnete zda je vice prostych zobrazeni X -> Y nebo zobrazeni na Y -> X.

Teorie grafu

1. Definujte obarveni grafu.

2. Definujte barevnost grafu.

3. Dokazte, ze kazdy graf, ktery obsahuje prave jednu kruznici liche delky ma barevnost 3.

Pravdepodobnost

1. Definujte podminenou pravdepodobnost.

2. Vime, ze P[A] > 0, P** > 0 a mame zadane i P[A|B]. Umime zjistit P[B|A]?

3. Priklad na Bayese a uplnou pravdepodobnost.

Automaty

1. Definujte jazyk.

2. Mame jazyk nad abecedou {1,0,X}, ketry ma uprostred X a jinak je symetricky. Napiste pro nej gramatiku.

3. Napiste mu automat.

Toky

1. Definujte maximalni tok.

2. Napiste algoritmus pro nalezeni maximalniho toku.

SQL

1. Nakreslit tabulky pro studenty - kazdy ma jmeno a prijmeni (ktere jsou nejednoznacne) a pro predmety - kazdy ma unikatni nazev a seznam studentu, kteri jsou na nej prihlaseni.

2. SQL dotaz: Pocet studentu, kteri chodi alespon na nejaky predmet.

3. SQL dotaz: Pocet studentu na kazdem z predmetu.

4. SQL dotaz: Seznam studentu, kteri chodi na predmet s nazvem 'nazev'.

Strankovani

1. 32-bitova architektura, dvouurovnove strankovani a tabulky po 10-ti bitech. Urcete velikost stranky. Je tato velikost obvykla?

2. Mejme prevody z VA na FA. Ktere z dvojic nedavaji smysl? (stacilo dat pozor na offsety a aby byl prevod konzistentni)

napriklad:
12345678 na 12345678 a 12345123 na 12345456
abcdef na 123def a abc987 na 456987**

Pro obor Programovani to bylo stejne, ale miesto toku v siti bylo:

TCP/IP

1. Popsat proc je potreba prekladat IP adresy na linkove adresy a za jakych predpokladu. Popsat nejkay k tomu pouzivany protokol.

2. Cim je omezena velikost IP packetu

3. Jaky je rozdil mezi "flow control" a "congestion control"

4. Proc vubec existuje protokol UDP, kdyz je tak podobny protokolu IP

Jinak u tech jazyku a automatu, pry to vetsina studentu a dokonce i autor zadani chapali tak, ze X muxe byt jenom uprostred a tudiz lze setrojit jednoduch zasobnikovy automat, ktery ten jazyk rozpozna. Zadani ovsem nevylucuje slova jako XXX, takze kdyz automat precte symbol X, tak si nemuze byt jisty, ze je uprostred slova a ze ma zacit ze zasobniku odebirat... I komisi to docela zaskocilo :)

Jinak u tech jazyku a automatu, pry to vetsina studentu a dokonce i autor zadani chapali tak, ze X muxe byt jenom uprostred a tudiz lze setrojit jednoduch zasobnikovy automat, ktery ten jazyk rozpozna. Zadani ovsem nevylucuje slova jako XXX, takze kdyz automat precte symbol X, tak si nemuze byt jisty, ze je uprostred slova a ze ma zacit ze zasobniku odebirat... I komisi to docela zaskocilo :)

Já měl jazyky s X uprostřed a 0 1 jinde a komisi se to nelíbilo. Snadná úprava gramatiky a automatu. Zásobníkový automat (pro bezkontextové jazyky) je v principu nedeterministický, takže XXX nevadí, sám "uhodne" prostředek, kdy začít číst zásobník.

Otázky příjemné, komise vlídná. Ufff... :D