# zkouška 27.5.08 hric

<{ForumPost(poster="kaja", timestamp=2008-05-27 13:10:10)}>
tak jo, zadání zkoušky  
  
1)a) randomizovaný quicksort - popsat ho a uvést výhody proti nerandomizovanému  
1)b) zdola odhadnout všechny *vyhledávací* **kecám, třídící** algoritmy a dokázat ... teď nevim přesně to zadání, ale je to to jak vyjde n log (n) ... nevěděl jsem, co dál od log<sub>2</sub> (n!) (musí se to n! přepsat na (n/2)<sup>n/2</sup>, na což jsem si nevzpomněl) a bral to jako špatně  
  
2)a) popsat Bellman-Fordův algoritmus na hledání nejkr. cesty, zdůvodnit správnost  
2)b) složitost Dijkstra při využití různých datových struktur  
  
3)a) definice silně souvislých komponent grafu  
3)b) popsat vytváření topologického uspořádání, zdůvodnit správnost   
  
4) těsně odhadnout fci F(n)=F(n/2)+2F(n/4)+b*n fcí g(n), aby g(n) byla  Θ(F(n)) nebo tak něco... vubec netušim jak se to dělá  
  
za každý příklad 5 bodů, tj. maximum je 20, minimum na projití k ústní je 13, já měl 10 :( co jsem viděl ústní, tak si na stůl položí tohle - [http://kti.ms.mff.cuni.cz/~hric/vyuka/alg/ads_poz.pdf](http://kti.ms.mff.cuni.cz/~hric/vyuka/alg/ads_poz.pdf) - zahledí se na to a něco z toho vybere
<{/ForumPost}>

<{ForumPost(poster="onashackem", timestamp=2008-05-27 13:48:52)}>
Mohl by někdo naznačit, jak by se mělo řešit?
<{/ForumPost}>

<{ForumPost(poster="BlackBerryTea", timestamp=2008-05-27 13:51:26)}>
ta uloha 1. b) bola zdola odhadnut zlozitost algoritmov zalozenich na porovnavani a dokazat ju  
  
inac dr. Hric sa mi vzhladom na opravovanie testu zdal celkom benevolentny, dostal som 17/20  
  
na ustnu som mal Master Theorem a po asi 10 minutach som odisiel s jednickou ....  :D
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2008-05-27 15:23:26)}>
A co se stane, kdyz nekdo da test a neda ustni? opakuje se cela zkouska nebo jen to ustni?
<{/ForumPost}>

<{ForumPost(poster="Petr Cech", timestamp=2008-05-27 16:32:52)}>
Jestli nedas ustni tak potom aspon ziskas 3, ne??  
 :lol:  :lol:
<{/ForumPost}>

<{ForumPost(poster="in5inity", timestamp=2008-05-28 14:38:25)}>
Písemka byla zvládatelná, ale chce to napsat ji na 13 bodů z 20. Jinak vás pan doktor nemilosrdně vyhodí.  
Všem, co se učí a nechápou Hricovy slajdy, doporučuji tyto stránky:  
  
[http://ocw.mit.edu/OcwWeb/Electrical-En ... tureNotes/](http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/LectureNotes/)  
  
  
je tam sice pár věcí navíc, ovšem nádherně vysvětleno vše, co jsem probírali s Hricem, perfektně vysvětlený Master Theorem, substituční metoda atd. Můžete se kouknut i na videa:D Vše ale v angličtině..... Ale opravdu doporučuju. Mě to nejspíš pomohlo k absolvování této zkoušky.   
  
  
Na ústní dostanete otázku, kterou Hric vybírá z požadavků, ovšem zkouší jen věci, co se stihly probrat....   
  
Občas chce dokázat správnost nějakého algoritmu. To jsem řešil tak, že jsem tak nakreslil obrázek, vyplatí se odvolat na nějaký invariant...   
  
  
Moje otázka z ústní: speciální násobení matic. Hric se dost ptal, ptá se na každý index dost dopodrobna. Důležité je chápat, proč to tak má fungovat a nějak to vysvětlit...   
  
Hodně štěstí všem!
<{/ForumPost}>

<{ForumPost(poster="Bimbosh", timestamp=2008-05-28 15:48:09)}>
Kdyz das pisemku, mas uz alespon 3ku jistou? Nebo te stale muze nakrasne vykopnout?
<{/ForumPost}>

<{ForumPost(poster="in5inity", timestamp=2008-06-01 09:51:48)}>
Nejsem si jistý, jestli Ti absolvování písemky stačí. Někde na minulém fóru jsem četl(2005), že snad někdo měl i na písemce plný počet bodů, ale přesto, když nevěděl na ústní, tak ho poslal domů....  
  
Tak asi tak...Nevím jak tento rok...
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2008-06-02 12:18:30)}>

 > kaja wrote:
 > 4) těsně odhadnout fci F(n)=F(n/2)+2F(n/4)+b*n fcí g(n), aby g(n) byla  Θ(F(n)) nebo tak něco... vubec netušim jak se to dělá

A jak se to tedy dělá, máte někdo tušení?
<{/ForumPost}>