# zkouška 10-6-2009 HRIC

<{ForumPost(poster="ian", timestamp=2009-06-10 13:54:08)}>
Dnes jsme tam byli jen čtyři, písemná část klasicky 3 x 2 otázky za 15 bodů celkem.  
  
1 a) delete v AVL stromech  
   b) dokázát, že výška RB-stromu je O(log n)  
2 a) dokázát nebo vyvrátit, že v souvislém grafu je množina všech lehkých hran pro všechny řezy minimální kostra  
   b) složitost Jarníkova (Primova) algoritmu v závislosti na volbě datových struktur  
3 a) definovat topologické uspořádání  
   b) popsat algoritmus na hledání nejkratší cesty v acyklickém grafu a dokázat jeho správnost  
  
na ústím jsem dostal dolní odhad složitosti třídicích algoritmů založených na porovnávání prvků
<{/ForumPost}>