Přednášky: 1. Organizace dat ve vnitřní a vnější paměti, datové typy (částečně opakování i jednoduchých DT), ordinalita. Strukturované datové typy. 2. Abstraktní datové typy (ADT) ? definice, význam ADT. Členění dle několika kritérií, základní operace nad ADT (FIFO, LIFO, 4 typy seznamů, dynamické pole, kruhový buffer, množina, multimnožina). 3. Úvod do strom s důrazem především na binární stromy. 4. Význam a jednotlivé typy procházení binárních stromů, možnosti jejich implementace, halda. 5. Algoritmus ? co to je, definice, kritéria dělení algoritmů, Divide & Conquer. 6. Asymptotická a amortizovaná složitost ? teorie složitosti, tipy na stanovení složitosti v praxi, příklady. 7. Rekurze, typy rekurzí, výhody a rizika. Backtracing, problém 8 dam. 8. Vyhledávací algoritmy ? popis problematiky, terminologie. 9. Lineární, binární interpolační vyhledávání, analýza, kdy použít ještě lineární vyhledávání a kdy je výhodnější seřadit a vyhledat binárně. Prune and Search. 10. Binární vyhledávací stromy (BST) ? teorie, procházení, implementace a základní operace nad BST. 11. Vyvažování stromů. AVL stromy, popis problematiky, termín bal, jednotlivé typy rotací, kritéria pro implementaci a použití jednotlivých rotací,nutnost vyvážení AVL po operacích insert a delete. 12. Sorting ? řazení, popis problematiky. Kritéria členění algoritmů řazení. BogoSort, SelectSort, InsertSort, BubbleShort, ShakerSort(CoctailSort), CombSort, ShellSort, QuickSort, MergeSort, HeapSort. 13. Hashování, hashovací tabulky ? terminologie, úvod, princip hashování. Asociativní vyhledávání, adresní vyhledávání přímé a hašováním. Hashovací funkce, jejich typy. Kolize a jejich vznik a řešení. Zřetězené a otevřené hashování, linear probing, double hashing. 14. Prohledávání řetezců, pattern matching ? terminologie, přirozené prohledávání, Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp. Chybová funkce, preprocessing. 15. Komprese dat Cvičení: Datové typy Rekurze Řazení Vyhledávání Hashování
|
-
Wirth, N. Algoritmy a štruktúry údajov. Alfa, Bratislava, 1987.
-
Knuth, D. The Art of Computer Programming. Reading, Massachutes: Addison-Wesley, 1997.
-
Kučera, L. Kombinatorické algoritmy. Praha, SNTL 1989.
|