Čepek 1. 6.

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
existence
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 1. 6. 2018 12:50
Typ studia: Informatika Bc.

Čepek 1. 6.

Příspěvek od existence »

Dělá písemnou a ústní část

V písemné byly nésledující otázky:

1) Najděte pomocí master theoremu složitost T(n) = 2 T(n/5) + T(n/2) + n a poté dokažte jeho správnost substituční metodou

2) Budujeme ropovod, který vede severo-jižním směrem (rovně) , na který je kolmými přípojkami napojeno n vrtů ropy, každý má nějaké zadané souřadnice (x_i,y_i), každá vždy unikátní. Chceme co nejmenší součet délek přípojek. Určete optimální algoritmus a čas.
poznámky: Ropovod může vést skrz nějaký vrt a souřadnice můžou být reálné (ne celočíselné).

3) orientovaný graf je polosouvislý, pokud pro libovolnou dvojici existuje cesta z jednoho do druhého nebo naopak (nebo obě). Popište optimální algoritmus na určení, zda graf je či není polosouvislý a určete jeho časovou složitost.

Možná řešení:

1) Vyjde 9/10 < 1, takže lineární (prostě master theorem, není co vymejšlet - zjednodušená verze je i na wiki)

2) Je to jen složitě položená otázka na to, že hledáme medián všech x_i. To se dá ukázat tim, že se to nakreslí a pak se řekne, že když na jedný straně je připojeno víc přípojek než na druhý, tak posunutím k nim se jejich celková délka sníží (o násobek rozdílu počtů na jedné a druhé straně - např napravo 5 a nalevo 3, tak posunutím ropovodu napravo o metr se součet zmenší o 1*(5-3)=2, o dva metry.)

Čas je lineární, používá se algoritmus na hledání mediánu

3) To je vyřešitelný přes nalezení silně souvislých komponent (mělo by být součástí přednášky) a pak z výsledného acyklického orientovaného grafu, jehož vrcholama jsou ty komponenty, se jen ověří, zda je to orientovaná cesta (lze uvést protipříklady A->B<-C a A<-B->C, kdyby se to větvilo v nějakém B, že mezi A a C není žádná cesta; kdyby přecejen byla nějak okolo, tak určitě není acyklickej, což je spor)

čas je Theta(n+m)

--------------------------------------

Pak u ústní dává věci typu "napište princip dvojitého hashování" nebo "dokažte časovou složitost n log n Kruskalova algoritmu".
Odpovědět

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