od sstepan » 12. 6. 2014 14:53
Dnešní písemka
1) T(n)=2T(n/5)+T(n/2)+n a pro vhodné n_0 (můžete si zvolit) platí T(n)=1 pro n<=n_0. Najděte f(n), aby T(n)=theta(f(n)) a dokažte substituční metodou.
2) V rovině jsou dány ropné vrty na pozicích (x_i,y_i) - žádné dva nemají stejnou x-ovou ani y-ovou souřadnici. Chceme postavit ropovod, který povede v severojižním směru. Každý vrt k němu bude připojenou přípojkou vedoucí kolmo na ropovod. Najděte ideální pozici ropovodu, aby součet délek přípojek byl co nejmenší. Určete a zdůvodněte složitost algoritmu.
3) Orientovaný graf nazveme polosouvislý, pokud mezi každými dvěma vrcholy vede cesta alespoň jedním směrem. Zjistěte, jestli je graf na vstupu polosouvislý a určete složitost algoritmu. Algoritmy z přednášky můžete používat bez důkazu jejich složitosti.
návod:
1) Zřejmě T(n)>=n, indukcí T(n)<=10n.
2) na y-ových souřadnicích nezáleží. Hledáme, x, že f(x)=sum |x-x_i| je minimální. Kdyby bylo nalevo od x méně bodů než napravo, posunutím x o jedna doprava se hodnota zmenší (několik absolutních hodnot se o jedna zvětší a více se jich o jedna zmenší). Stačí tedy najít medián a případně vybrat správný ze dvou středů (je-li sudo vrcholů). Složitost O(n).
3) Hledáme SSK jako na přednášce - DFS nám dá pořadí vrcholů, sestavíme transponovaný graf a pouštíme DFS v daném pořadí vrcholů. Jednotlivé stromy, které dostáváme jsou jednotlivé SSK. Navíc víme, že všechny hrany vedou jen v rámci stromu nebo zpět. Stačí si tedy všimnout, že graf je polosouvislý vede-li z každého stromu nějaká hrana do toho předchozího.
Dnešní písemka
1) T(n)=2T(n/5)+T(n/2)+n a pro vhodné n_0 (můžete si zvolit) platí T(n)=1 pro n<=n_0. Najděte f(n), aby T(n)=theta(f(n)) a dokažte substituční metodou.
2) V rovině jsou dány ropné vrty na pozicích (x_i,y_i) - žádné dva nemají stejnou x-ovou ani y-ovou souřadnici. Chceme postavit ropovod, který povede v severojižním směru. Každý vrt k němu bude připojenou přípojkou vedoucí kolmo na ropovod. Najděte ideální pozici ropovodu, aby součet délek přípojek byl co nejmenší. Určete a zdůvodněte složitost algoritmu.
3) Orientovaný graf nazveme polosouvislý, pokud mezi každými dvěma vrcholy vede cesta alespoň jedním směrem. Zjistěte, jestli je graf na vstupu polosouvislý a určete složitost algoritmu. Algoritmy z přednášky můžete používat bez důkazu jejich složitosti.
návod:
1) Zřejmě T(n)>=n, indukcí T(n)<=10n.
2) na y-ových souřadnicích nezáleží. Hledáme, x, že f(x)=sum |x-x_i| je minimální. Kdyby bylo nalevo od x méně bodů než napravo, posunutím x o jedna doprava se hodnota zmenší (několik absolutních hodnot se o jedna zvětší a více se jich o jedna zmenší). Stačí tedy najít medián a případně vybrat správný ze dvou středů (je-li sudo vrcholů). Složitost O(n).
3) Hledáme SSK jako na přednášce - DFS nám dá pořadí vrcholů, sestavíme transponovaný graf a pouštíme DFS v daném pořadí vrcholů. Jednotlivé stromy, které dostáváme jsou jednotlivé SSK. Navíc víme, že všechny hrany vedou jen v rámci stromu nebo zpět. Stačí si tedy všimnout, že graf je polosouvislý vede-li z každého stromu nějaká hrana do toho předchozího.