Přidávám dojmy ze zkoušky:
Bylo nás tam zhruba osmnáct, takže se asi protočily všechny otázky - jistě to nevím, Koubek mluví moc potichu. Seděl jsem vpředu (zbyla na mě první lavice před katedrou) a dostal jsem Quicksort, takže mýtus o perfektním hašování je definitivně vyvrácen. Kolega za mnou, který ho dostal po pár minutách vzdal.
Quicksort
Napsal jsem:
malé úvodní povídání (třídící algoritmus, vstup, výstup...)
popis algoritmu (dva pointry, překřížení rekurse) - neměl jsem tam přesně vyřešené všechny případy, ale Koubek říkal že to není nutné.
důkaz složitosti v průměrném případě: o to mu šlo především. Bohužel ani jeden ze dvou důkazů ve skriptech jsem nepochopil, naučil jsem se místo toho Čepkův jednoduchý důkaz z prváku.
Koubek byl spokojen (byl podle mě rád, že vidí něco nového) a dal mi za jedna. :D
Důležitý postřeh:
Nabyl jsem přesvědčení, že za 80% potíží s tímto předmětem jsou zodpovědná ta jeho skripta :shock: . Moje doporučení pro všechny, kteří budou dělat zkoušku: vyhněte se jim a tytéž důkazy se naučte odjinud. Namátkou QS - Čepek. Konstrukce primitivní hašovací fce - odvození, které dělával Koubek na přednáškách, než napsal skripta je celkem stravitelné (asi jako středně těžký mat. důkaz), viz zápisky Lenka.
Matfyz Wiki