od Jookyn » 28. 5. 2009 12:59
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...
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...