zkouška 19.1.2010

Dnešní zkouška vypadala poměrně tradičně, alespoň v duchu toho, co se píše zde na fóru.
Přislo nás poměrně hodně (19 přihlášených), skoro plná S7. Doc. Koubek ihned začal rozdávat otázky, co jsem zaslechl byly

• AVL a RB stromy

• dvojité hešování

• fibonaciho a binomialni haldy

• A-sort

• vyhledávání v uspořádaném poli

Ja jsem dostal univerzální hešování (definice a konstrukce c-univerzalniho systému), což jsem si vůbec ale vůbec nepřál, a podle toho taky vypadalo. Pomrdal jsem už samotnou definici a konstrukci jsem sice popsal, ale ke správnosti jí chybělo mnohé (uměl jsem to z Čepkových slajdů z ADS1 a ne moc přesně). Koubek si to pročetl a prohlásil: "No, tak to opravíme" a chvíli mě nechal přemýšlet. Po 5 minutách ticha se do toho vložil a začal mi říkat, co by jak asi mělo být. Za mého postupného přitakávání jsme se dostali k "tak nevim jestli vás mám vyhodit nebo vám dát trojku". Dostal jsem doplňující otázku na hešování přemísťováním a s dvěma ukazateli, což jsem bez větších potíží vyplodil a dostal za 3. Na to jak jsem byl dutej při první otázce luxusní známka a nebyl potřeba jediný důkaz. Od 4 mě pravděpodobně zachránilo to, že u první otázky jsem slovy popsal, jak by to mělo celé vypadat a tím dal najevo, že alespoň rámcově tomu rozumím.
Koubek je skutečně v pohodě, při samotném zkoušení docela pomáhá a pokud máte něco špatně (snad nikdo to neměl "do puntíku"), tak vám dá šanci to opravit.
Ostatni - 1 se zvednul asi po 5 minutách sám, další 3 lidi jsem viděl jak vyhodil (ale poměrně přátelsky), asi 2 lidi jsem slyšel za tři, zbytek nevím.

Ano, zkouška vypadá zhruba tak, jak jsem čekal po přečtení informací z předchozích let. Já měl to hledání v uspořádaném poli. Korektní popis a pochopení funkce algoritmů a nějaká základní fakta/pozorování na trojku stačí, to ostatně doc. Koubek říkal už na přednášce. Já jsem k tomu u zobecněného kvadratického vyhledávání vyplodil ještě horní odhad počtu bloků O(log log n) a z něj odhad složitosti v nejhorším případě O(log n). Tušil jsem, že by se dala nějak počítat i očekávaná složitost, ale nepamatoval jsem si vůbec jak (podle Čebyševovy nerovnosti). Nevím jestli by stejně přísný u těžších otázek (tahle byla myslím objektivně jedna z těch snažších), ale na dvojku to nestačilo. Ještě mi dal možnost si to zlepšit amortizovanou složitostí operací na (a,b)-stromech...;), takže za tři.

(Z posledních dvou přispěvků to vypadá, že nerozhodné známky mají tendenci konvergovat ke trojce. To by mohla být náhrada za již vyvrácenou populární domněnku, že lidé v první řadě dostávají univerzální hashování;).)

Jinak zkouška probíhá v příjemné atmosféře a Koubek je sympatický pán, jak už tu bylo několikrát psáno, ale... ...těch datových struktur je opravdu dost a ze skript se učí opravdu špatně, takže až se budete na zkoušku připravovat, doporučuju dohledat si, co můžete, někde jinde než v Koubkových skriptech. Na něco stačí Čepkovo ADS, velmi srozumitelně bývají algoritmy popsané a hlavně analyzované v CLRS: Introduction to Algorithms (i když ani tam mnoho věcí z DS prostě vůbec není). Ta Koubkova skripta jsou informačně bohatá, všechno v nich je a většinou bez chyb, ale formou jsou nestravitelná. Až vám něco nepoleze do hlavy, nebude to zpravidla proto, že je to složité, ale proto, že je to tam nešikovně popsané. Já jsem se snažil chápat věci nejdříve z nich, ale kdybych se to měl učit znova, asi bych tím už neztrácel čas. Na závěr ještě poznamenám, že jsem chodil na přednášky, a i když jsem z nich nebyl přímo nadšený, tak výklad na nich byl místy jasnější než v těch skriptech.