# Čepek 8.6.2012

<{ForumPost(poster="LordG", timestamp=2012-06-08 10:50:04)}>
Zadání bylo podle mého triviální. Ale tak jestli bylo se ukáže na ústní části v jednu  :D   
  
1) Odhadnout f(n) takové, že T(n) = T(n/3) + 2T(n/4) + 3n náleží theta(f(n)) a dokázat substituční metodou; navíc předpokládáme, že pro vhodné n0 T(n0) je O(1).  
  
2) Platí/neplatí: Y je cesta od kořene k listu v AVL-stromu. X je množina prvků vlevo od Y, Z množina prvků vpravo od Y. Pak pro každé x z X, y z Y a z ze Z platí:  
klíč(x) <= klíč(y) <= klíč(z).  
  
3) Platí/neplatí: máme orientovaný graf, v něm vrchol u, jehož vstupní i výstupní stupeň je >=1. Potom každý DFS strom, do něhož náleží u, má alespoň dva vrcholy. Navíc G neobsahuje smyčky.  
  
Můj názor  
1) f(n) = n; položíme n0 = 12. Vyjde z IP že d>=12, c<=6, potom pro n-->n+1 vyjde c<=18, d>=18, tedy pro n>=12 6n <= T(n) <= 18(n).  
  
2) neplatí; obecně platí jen pro x, y a z ze stejné hladiny podstromu, vtip je v tom, že y může být otcem x nebo z, ale nepřímým, tudíž x může být v pravém podstromu y a vice versa  
  
3) platí; buď byl u od někud objeven a tedy DFS strom má kořen různý od u, tedy má vrcholy alespoň dva, nebo DFS v u začínalo a došlo do některého ze sousedních vrcholů, které existují, protože podle zadání deg out (u) >= 1 a na u není smyčka.
<{/ForumPost}>

<{ForumPost(poster="Miso", timestamp=2012-06-08 14:15:51)}>
Trojka neplati, staci si vziat trivialny protipriklad X --> U --> V. Ak DFS prechadza vrcholy v poradi V, U, X, tak z U-cka narazime len na cierny vrchol V, a tak U tvori DFS strom s 1 vrcholom.
<{/ForumPost}>