Zkouška 30.5.2022 09:30 Jan Hric

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

Zkouška 30.5.2022 09:30 Jan Hric

Příspěvek od Xerneis »

1.
a) Formulujte Master Theorem.
b) Pomocí Master Theoremu odhadněte složitost v závislosti na parametru a:
T(n) = aT(n/3) + O(n^2)

2.
a) Definujte univerzální množinu hashovacích funkcí.
b) Popište konstrukci univerzální množiny hashovacích funkcí.

3.
Máte algoritmus na hledání minimální kostry grafu:
-> Vstup: souvislý G s ohodnocenými hranami

-> Dokud jsou v G cykly:
-> Z nějakého cyklu smažete jeho nejdražší hranu

-> Výstup: zbývající hrany
a) Dokažte, že výstupem je minimální kostra.
b) Navrhněte implementaci algoritmu a odvoďte časovou složitost.
Odpovědět

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