12. 6. 2014 - Čepek

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
sstepan

12. 6. 2014 - Čepek

Příspěvek od sstepan »

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

Re: 12. 6. 2014 - Čepek

Příspěvek od Petrroll »

Mohl by někdo prosím rozepsat trochu víc tu trojku? Snažím se na to nějak přijít jak to má fungovat, ale zatím nic.
//Nechvátá to, zkoušku z ADS už mám, ale trápí mě, že tohle nechápu :)
Uživatelský avatar
petrroll
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 23. 5. 2015 22:27
Typ studia: Informatika Bc.

Re: 12. 6. 2014 - Čepek

Příspěvek od petrroll »

Už to chápu. Prostě ten graf rozbijeme na Komponenty Silné Souvislosti (což je DAG) a aby pro něj platila polosouvislost, tak musí jít o cestu.
Odpovědět

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