Předmět: Algoritmizace a datové struktury

» Seznam fakult » FM » NTI
Název předmětu Algoritmizace a datové struktury
Kód předmětu NTI/ALD
Organizační forma výuky Přednáška + Cvičení
Úroveň předmětu Bakalářský
Rok studia nespecifikován
Semestr Zimní
Počet ECTS kreditů 6
Vyučovací jazyk Čeština
Statut předmětu Povinný, Povinně-volitelný
Způsob výuky Kontaktní
Studijní praxe Nejedná se o pracovní stáž
Doporučené volitelné součásti programu Není
Vyučující
  • Satrapa Pavel, doc. RNDr. Ph.D.
Obsah předmětu
Témata přednášek: 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. Řazení - popis problematiky. Kritéria členění algoritmů. BogoSort, SelectSort, InsertSort, BubbleSort, 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. Náplň cvičení odpovídá přednáškám - na praktických příkladech jsou procvičovány techniky, principy a algoritmy probírané na přednáškách.

Studijní aktivity a metody výuky
Přednáška, Cvičení
  • Domácí příprava na výuku - 60 hodin za semestr
  • Příprava na zkoušku - 20 hodin za semestr
  • Příprava na zápočet - 16 hodin za semestr
  • Kontaktní výuka - 84 hodin za semestr
Výstupy z učení
Cílem předmětu je seznámit studenty s pokročilejšími datovými strukturami, možnostmi jejich počítačové reprezentace a algoritmy pro jejich zpracování. Nemalá pozornost je věnována práci s grafy (jejich reprezentaci) a algoritmům pro základní grafové úlohy. Z probíraných algoritmů je třeba především zmínit mechanismy pro třídění a vyhledávání v datech.

Předpoklady
nespecifikováno

Hodnoticí metody a kritéria
Kombinovaná zkouška

Doporučená literatura


Studijní plány, ve kterých se předmět nachází
Fakulta Studijní plán (Verze) Kategorie studijního oboru/specializace Doporučený ročník Doporučený semestr
Fakulta: Fakulta mechatroniky, informatiky a mezioborových studií Studijní plán (Verze): Aplikované vědy v inženýrství (2019) Kategorie: Speciální a interdisciplinární obory 2 Doporučený ročník:2, Doporučený semestr: Zimní