[Zk] 11.2.2009

Přednáška navazuje na přednášky Algoritmy a datové struktury I a II a Programování I a II bakalářského studia. Bude věnována dvěma základním datovým strukturám, hašování a $(a,b)$-stromům (tato struktura se také nazývá $B$-stromy). Popisují se zde základní vlastnosti těchto struktur a jejich složitost. Na závěr přednášky se provede stručné zhodnocení třídicích algoritmů.
Jochanan
Matfyz(ák|ačka) level II
Příspěvky: 85
Registrován: 12. 5. 2007 15:58
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

[Zk] 11.2.2009

Příspěvek od Jochanan »

Kdyby se někdo cítil, že by rád zašel na zkoušku zítra, ale nechce to riskovat, protože je plno... Tak nemusí zoufat, protože já jsem si bohužel termín zapsal, ale úplně jsem na něj zapoměl, takže nedorazím :oops:
Uživatelský avatar
QED
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 21. 6. 2005 20:39
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: [Zk] 11.2.2009

Příspěvek od QED »

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.
Odpovědět

Zpět na „TIN066 Datové struktury I“