|
Vyučující
|
-
Sýkorová Květuše, Mgr.
-
Oliva Karel, doc. RNDr. Dr.
-
Škvor Jiří, RNDr. Ph.D.
|
|
Obsah předmětu
|
1. Terminologie - řád algoritmu, časové náročnosti, paměťová náročnost aj. 2. Základní datové struktury - pole, zásobník, fronta, seznam. 3. Třídící algoritmy řádu O(n^2) - SelectSort, InsertSort, BubbleSort 4. Třídící algoritmy řádu O(n^k) - ShellSort, KnuthSort, HeapSort 5. Třídící algoritmy řádu O(n.log_k n) - QuickSort, MergeSort 6. Třídící algoritmy řádu O(k.n) - RadixSort, BucketSort 7. Vyhledávací algoritmy - Brute Force, Binary Search, Interpolation Search 8. Indexové soubory - Dense Index, Sparse Index, Multilevel Index 9. Rozptylovací funkce - Close Hash Table, Open Hash Table, Perfect Hash, Rehash 10. Stromové struktury - základní vlastnosti, Binary Tree, Binary Search Tree 11. Stromové struktury - Digi Tree, B-Tree 12. Stromové struktury - vyvážené stromy (AVL-tree, Red-Black tree) 13. Stromové struktury - speciální stromy (Trie, Splay, Treap, Randomized BST)
|
|
Studijní aktivity a metody výuky
|
|
nespecifikováno
|
|
Výstupy z učení
|
Kurs je zaměřený na získání přehledu o základních abstraktních datových strukturách (pole, fronta, zásobník, spojový seznam, index, hash table, speciální vyhledávací stromové struktury). Současně s tím jsou studenti seznámeni s vybranými algoritmy nad těmito strukturami. Pozornost je věnována nejen formálnímu popisu struktur a algoritmů, ale i praktické implementaci.
|
|
Předpoklady
|
nespecifikováno
|
|
Hodnoticí metody a kritéria
|
nespecifikováno
Požadavky pro udělení zápočtu - aktivní účast na cvičeních (docházka, povoleny jsou nejvýše 3 absence) - prezentace řešení vybraných úloh v programovacím jazyce C# a jejich vysvětlení Zkouška je ústní a proběhne v časovém rozsahu zhruba 20-30 minut. Prověřovány jsou teoretické znalosti z předmětu, schopnost popisu a rozboru vybraných algoritmů, a to včetně odvození jejich vlastností.
|
|
Doporučená literatura
|
-
D. E. Knuth. "The Art of Computer Programming - Sorting and Searching", Addison-Wesley, USA1998.
-
Keogh, J., Davidson, K. Datové struktury bez předchozích znalostí. ComputerPress, Brno, 2006. ISBN 80-251-0689-6.
-
Sedgewick, R. Algoritmy v C. SoftPress, Praha, 2003. ISBN 80-86497-56-9.
-
Wirth, N. Algoritmy a štruktúry údajov. Alfa, Bratislava, 1989. ISBN 80-05-00153-3.
-
Wróblewski, P. Algoritmy, datové struktury a programovací techniky. ComputerPress, Brno, 2004. ISBN 80-251-0343-9.
|