Technická univerzita v Liberci
Studijní programy a katalog předmětů
Technická univerzita v Liberci
English
Hledání
FAQ

Předmět: Algoritmy a datové struktury

« Zpět
Název předmětu Algoritmy a datové struktury
Kód předmětu NTI/ADA
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ů 5
Vyučovací jazyk Čeština
Statut předmětu Povinný
Způsob výuky Kontaktní
Studijní praxe Nejedná se o pracovní stáž
Doporučené volitelné součásti programu Není
Vyučující
  • Kopetschke Igor, Ing.
  • Satrapa Pavel, doc. RNDr. Ph.D.
  • Hybš Jan, Ing.
Obsah předmětu
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í

Studijní aktivity a metody výuky
Monologický výklad (přednáška, prezentace, vysvětlování)
  • Účast na výuce - 56 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.
Studenti se seznámí s vlastnostmi vybraných datových struktur a algoritmů a naučí se je používat.
Předpoklady
Základy algoritmizace.

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

Podmínkou zápočtu je aktivní účast na cvičeních, úspěšné absolvování testů. Zkouška je písemná a ústní.
Doporučená literatura
  • 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.


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): Informační technologie (2013) Kategorie: Informatické obory 2 Doporučený ročník:2, Doporučený semestr: Zimní
Technická univerzita v Liberci, data aktuální k: 17.04.2024 23:51.