zkouška 18.5. u Čepka

JM
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 18. 5. 2007 16:52

zkouška 18.5. u Čepka

Příspěvek od JM »

Tak jsem byl dneska na předtermínu z ADS.

Nejdřív písemka - 3 příklady, 2 hodiny, pro připuštění k ústní zkoušce jsme měli vyřešit aspoň 2 příklady.
Zadání(zhruba):
1. Algoritmus má složitost T(n) = 2T(n/2 + 1) + n^2. Pro n<n0 uvažujte T(n)=1 (kde n0 je vhodně zvolená konstanta). Uhodněte fci f(n), pro kterou platí, že T(n) = [velké omega](f(n)) a dokažte to indukcí.
2. X a Y jsou dvě setříděná pole přirozených čísel, obě o délce n. Najděte medián (jeden z mediánů) těchto 2n čísel.
3. Vymyslete algoritmus, který vynásobí dvě obdélníkové matice rozměru (kn x n) a (n x kn), kde k je přirozené číslo. Použijte jako podprogram Strassenův algoritmus, určete časovou složitost a porovnejte ji s časovou složitostí klasického násobení.

Na zkoušce jsme byli jenom dva. Místo Čepka nám ty písemky opravil nějaký mladý člověk (nevím, kdo to byl, ale byl hodný :)). Pak jsme šli za Čepkem do pracovny. Já jsem měl 2,5 bodu, tak se mě zeptal na Bellman-Fordův algoritmus. Nechal mě si to sepsat. Pak jsme to spolu probrali, docela se v tom šťoural. Pak se mě během asi 20 vteřin poptal na AVL stromy a nakonec mi dal jedničku :D
Kamarád měl z písemky 1,5 bodu. Bylo vidět, že se mu nechce ho vyhodit, ale nakonec řekl, že mu to nebude počítat jako neúspěšný pokus a ať teda přijde příště.

Tož tak...
Odpovědět

Zpět na „2006“