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.
Koukám, že odpolední zadání tu ještě není, tak doufám, že si to ještě po čtyřech dnech pamatuju:
[b]1. Vlastnosti čísel[/b]
Definujte pojmy suprema a maxima.
Popište, jaký je mezi nimi rozdíl.
Je pravda, že každá podmnožina [b]R[/b] má supremum?
Napište příklad podmnožiny racionálních čísel, která v racionálních číslech nemá supremum.
[b]2. Metrické prostory[/b]
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á.
[b]3. Algebra[/b]
Definujte pojem grupa a homomorfismus.
Definujte permutační grupu.
Potom tam byly obrázky dvou stavů hry ekvivalentní Loydově patnáctce ([url]http://cs.wikipedia.org/wiki/Patn%C3%A1ctka[/url]). Za úkol bylo rozhodnout, jestli lze nějakou posloupností tahů dospět z jednoho stavu do druhého a zdůvodnit.
[b]4. Programování[/b]
Definujte rozhrani semaforu a jeho semantiku.
Implementujte problém producent a konzument.
[b]5. Databáze[/b]
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ěť.
[b]6. Algoritmy[/b]
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 ([url]http://cs.wikipedia.org/wiki/Souvisl%C3%A1_mno%C5%BEina[/url]) 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.