Detail předmětu
Algoritmy a datové struktury
FEKT-BPC-ALDAk. rok: 2024/2025
První část předmětu je zaměřena na seznámení studentů se základními pojmy: algoritmus, časová a paměťová složitost algoritmu, pojem datový kontejner / kolekce.
Druhá část předmětu se zabývá pojmy: abstraktní datový typ: (Vektor, Zásobník, Fronta, Množina, Strom) a využití iterátorů pro tyto datové typy.
Ve třetí části se studenti seznámí s rekurzivními a nerekurzivními algoritmy, algoritmy pro třídění a vyhledávání.
Jazyk výuky
Počet kreditů
Garant předmětu
Zajišťuje ústav
Vstupní znalosti
Pravidla hodnocení a ukončení předmětu
Až 60 bodů za závěrečnou písemnou zkoušku. Minimální požadovaný počet bodů ze závěrečné zkoušky je 20 bodů.
Počítačová cvičení jsou povinná, řádně omluvené zmeškané počítačové cvičení lze po domluvě s vyučujícím nahradit.
Učební cíle
Absolvent zná:
- pojmy abstraktní datový typ, časová a paměťová složitost a její odhady,
- pojem rekurze,
- základní algoritmy pro přímé a nepřímé třídění a vyhledávání dat.
Absolvent předmětu je schopen:
- provést rozbor úlohy pomocí vývojového diagramu,
- stanovit pro jednoduchý algoritmus jeho časovou a paměťovou složitost,
- používat základní abstraktní datové typy (Vektor, Zásobník, Fronta, Množina, Strom) a využívat iterátorů pro tyto datové typy,
- řešit problém pomocí rekurzivních a nerekurzivních algoritmů,
- navrhnout a implementovat základní třídicí a vyhledávací algoritmy.
Prerekvizity a korekvizity
- povinná prerekvizita
Úvod do programování
Základní literatura
VEČERKA, Arnošt. Základní algoritmy. Skriptum Olomouc 2007. 91 s. (CS)
WRÓBLEWSKI,Piotr. Algoritmy – Datové struktury a programovací techniky. Brno: Computer Press, 2004. 351 s. ISBN 80-251-0343-9 (CS)
Elearning
Zařazení předmětu ve studijních plánech
- Program BPC-AMT bakalářský 1 ročník, letní semestr, povinný
Typ (způsob) výuky
Přednáška
Vyučující / Lektor
Osnova
2. Abstraktní datové typy, signatura abstraktního datového typu, pojem (kolekce / kontejner), pojem lineární a nelineární datové struktury (pole, jednosměrně vázaný seznam), popis a vlastností ADT: Zásobník, implementace ADT Zásobník pomocí pole a jednosměrně vázaného seznamu.
3. Popis a vlastnosti ADT: Fronta, Množina, pojem iterátor, využití iterátorů u ADT.
4. Pojem: unordered a ordered kontejner/kolekce. Popis a vlastnosti datového typu: Halda, Strom.
5. Úvod do třídicích algoritmů, vlastnosti třídicích metod, vnější a vnitřní třídění, třídění "in situ / in place". Algorithms Insert Sort, odvození složitosti algoritmu.
6. Třídění přímou výměnou (BubbleSort), modifikace algoritmu BubbleSort, odvození složitosti algoritmu, třídění přímým výběrem (SelectSort), odvození složitosti algoritmu.
7. Rekurzivní a iterativní algoritmus, využití rekurze pro výpočet Fibonacciho posloupnosti, Wildcard matching (zástupné symboly ?*). Varianty rekurzivních algoritmů: přímá, nepřímá rekurze (rekurze s pomocnou funkcí).
8. Účinnější metody vnitřního třídění - Shellovo třídění (Shell Sort), Quick Sort.
9. Stromy - základní informace, třídění s využitím haldy.
10. Vnější třídění se stejným počtem vstupních a výstupních souborů, odvození složitost algoritmu. Vnější třídění s využitím vnitřního třídění, odvození složitosti.
11. Vyhledávání v lineární datové struktuře, Binární vyhledávání v poli, složitost algoritmu. Binární vyhledávací stromy, určení odhadu složitosti algoritmu vyhledávání.
12. Vázaný seznam s přeskoky (SkipList). Tabulka s rozptýlenými hesly - hašování, volba hašovací funkce, kolize. Metody řešení kolize: zřetězení, otevřené adresování a vyhledávání volné pozice v tabulce. Očekávaná složitost operací nad hašovací tabulkou.
13. AVL stromy, B-stromy, závěr kurzu.
Cvičení na počítači
Vyučující / Lektor
Osnova
2. ADT: TStack_array, TStack_list.
3. ADT: TQueue_list.
4. ADT: Dokončení TQueue_list, TQueue_array, implementace iterátorů.
5. Test #1 (ADT).
6. Algoritmy: Insert Sort, Select Sort, Bubble Sort.
7. Algoritmy: Bubble Sort (včetně optimalizace s pomocným příznakem), Bubble Sort (s výpočtem indexu poslední změny), Shaker Sort, TVector element struct (třídění prvků typu struktura dle různých klíčů).
8. Rekurzivní algoritmy: Faktoriál, Fibonacciho posloupnost, Wildcard matching.
9. Algoritmy pokročilého třídění: Shell Sort, Quick Sort, Heap Sort, Merge Sort.
10. Algoritmy: Vnější třídění se stejným počtem vstupních/výstupních souborů.
11. Vyhledávání v poli (ADT Množina s binárním vyhledáváním).
12. Hašování (ADT Množina realizovaná Hash mapou).
13. Test #2 (Algoritmy).
Elearning