IP 9.9.2011 11:30

Vše co se týká bakalářských státních závěrečných zkoušek.
Uživatelský avatar
mifeet
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 27. 1. 2010 14:37
Typ studia: Informatika Ph.D.

IP 9.9.2011 11:30

Příspěvek od mifeet »

Koukám, že odpolední zadání tu ještě není, tak doufám, že si to ještě po čtyřech dnech pamatuju:

1. Vlastnosti čísel
Definujte pojmy suprema a maxima.
Popište, jaký je mezi nimi rozdíl.
Je pravda, že každá podmnožina R má supremum?
Napište příklad podmnožiny racionálních čísel, která v racionálních číslech nemá supremum.

2. Metrické prostory
Definujte metrický prostor a euklidovskou metriku.
Definujte souvislou množinu.
Dokažte s pomocí definovaných termínů, že podmnožina reálných čísel s euklidovskou metrikou je souvislá právě když je to interval nebo je jednobodová.

3. Algebra
Definujte pojem grupa a homomorfismus.
Definujte permutační grupu.
Potom tam byly obrázky dvou stavů hry ekvivalentní Loydově patnáctce (http://cs.wikipedia.org/wiki/Patn%C3%A1ctka). Za úkol bylo rozhodnout, jestli lze nějakou posloupností tahů dospět z jednoho stavu do druhého a zdůvodnit.

4. Programování
Definujte rozhrani semaforu a jeho semantiku.
Implementujte problém producent a konzument.

5. Databáze
Definujte B-strom.
Určete časovou složitost operací vyhledání, vkládání a mazání z B-stromu.
Popište, proč je výhodné používat B-stromy při ukládání na externí paměť.

6. Algoritmy
Definujte třídy složitosti P a NP.
Definujte NP-těžký problém a NP-úplnost.
Jaké metody se v praxi používají k řešení NP-těžkých prolémů?
Uveďte tři příklady NP-úplných problémů.

Do odpovědí jsem napsal jenom to, co bylo v zadání, nic navíc. Stačilo to na jedničku a zkoušející se už ani moc neptali. Ale je pravda, že podle zkušeností ostatních je lepší napsat toho víc než míň.

Důkladněji se ptali jenom na metrické prostory. Definici souvislé množiny (http://cs.wikipedia.org/wiki/Souvisl%C3%A1_mno%C5%BEina) jsem totiž v životě neslyšel, tak jsem tam napsal definici souvislosti z rovinných grafů pomocí oblouků a pokusil se to nějak zobecnit na metrické prostory (pro každé dva body v množině existuje spojité zobrazení z [0,1] takové, že množina jejích hodnot leží v množině a spojuje ony dva body). Překvapivě to zkoušející vzal, jenom ten důkaz jsem převedl na nějakou větu z analýzy o spojitých funkcích, kterou jsem nedokázal. Řekl jsem jim, že bych se nad důkazem musel trochu zamyslet a s tím se spokojili. Jinak se mě už ptali jenom na vztah normy a metriky (správná odpověď měla být norma určuje metriku).

Postřeh k producentovi/konzumentovi byl, že většina lidí zapomněla zamykat přístup k frontě mutexem.
Odpovědět

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