Čepek 8.6.2012

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
LordG
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 11. 1. 2012 13:08
Typ studia: Informatika Bc.

Čepek 8.6.2012

Příspěvek od LordG »

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.
Miso

Re: Čepek 8.6.2012

Příspěvek od Miso »

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

Zpět na „TIN060 Algoritmy a datové struktury I“