Hric - 28.5.

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Jookyn
Matfyz(ák|ačka) level III
Příspěvky: 115
Registrován: 13. 9. 2008 21:42
Typ studia: Informatika Mgr.

Hric - 28.5.

Příspěvek od Jookyn »

Otázky na písemce:

1 a) Dokázat dolní odhad O(n log n) pro třídící algoritmy založené na porovnávání dvou prvků
b) Upravit counting sort, aby byl stabilní (= každé 2 prvky vstupu se stejnou hodnotou klíče jsou na výstupu ve stejněm pořadí jako na vstupu, což věděl jen někdo, Hric odmítl říct, co to je, že prej to bylo na přednášce)

2 a) Dokázat nebo vyvrátit f = o(g) => g = maléomega(f)
b) Pomocí substituční metody dokázat, že T(n) = 2T(n/3) + 2T(n/6) + bn je O(n log n)

3 a) Dokázat správnost Floyd-Warshalla
b) Určit složitost Dijkstrova algoritmu v závislosti na datových strukturách

Každá otázka za 5 bodů (15 celkem), měli bychom mít 9 bodů.

Výsledky ještě nejsou, ústní bude odpoledne, jestli se k ní dostanu, dam nějaký info...
Odpovědět

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