Zkouška 29.5. Kučera

Oproti minulému semestru Kučera změnil systém. V učebně jsou vždy jen čtyři lidi, ostatní čekají na chodbě. Když někdo odejde, tak Kučera dojde pro dalšího v pořadí (podle data narození). Každému dá téma ke zpracování a jde si sednout dopředu. Když má někdo hotovo, tak za ním Kučera dojde a projede mu ten papír a dá nějakou doplňující otázku, pokud jsou nějaké chyby, tak přihodí třeba nějaký důkaz...

Já jsem měl Odhad nejmenší složitosti (v nejhorším případě) třídění na základě porovnávání, zaslechl jsem ještě tato témata: AVL stromy, Červeno-černé stromy, Dijkstrův algoritmus, Hledání minimální kostry, Hašování (důkaz průměrného počtu kolizí v univerzálním hašování)...

Jako doplňující otázku jsem dostal hloubku červeno-černého stromu (bez důkazu, ale jeden co měl hašování a měl v tom takový trošku nejasnosti, tak po něm chtěl i důkaz jestli se nepletu).

Dneska to bylo naprosto v pohodě. Já jsem měl hledání minimální kostry, tak sem popsal to jeho obecné schéma, jarníka a kruskala a pak jsem se pustil do důkazu s tím, že jsem si jen pamatoval, že kučera to dokazoval sporem a pak sem si z algovision pamatoval náznakem ten obrázek. Tak jsem ten důkaz vedl tím směrem a přestože jsem tam měl drobné nepřesnosti - myslel jsem to jinak, než jsem to napsal (je to jen hraní se slovama a na to si prostě moc nepotrpím) a na konci jsem se do toho trochu zamotal, takže konec tam nebyl, tak kučera byl natolik hodnej, že vhodně položenejma otázkama ze mě aspoň něco dostal. Dostal jsem za dva. Jiný otázky než psal šlupka nebyly. Jinak co jsem zahlídl v jeho papíru, tak skoro všichni měli za jedna, já za dva, jeden neudělal, ale kdyby se nezamotal do těch doplňujících otázek, tak na tu trojku by to taky uhrál. Řekl bych, že oproti lingebře v zimě jsou algoritmy rozhodně schůdnější.

A to bylo keců, že tě vyhodí :mrgreen:

Kdybych dostal to hešování nebo hloubku BST tak jo, ale dneska sem měl konečně u zkoušky štěstí :-)

PS: Ještě jsem zapoměl dodat, že mě se ani na žádnou doplňující otázku neptal. A co se týče formality definic a důkazů, tak to jsem opravdu moc nehrotil dneska a stejně to vyšlo (na začátku jsem napsal, že mám graf G(V,E), ale dál jsem stejně psal všechno slovně, takže nějaký super přesný matematický zančení u těch grafů být taky nemusí)