Detail předmětu

Algoritmy a datové struktury

FEKT-BPC-ALDAk. rok: 2022/2023

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

čeština

Počet kreditů

7

Garant předmětu

Ing. Petr Petyovský, Ph.D.

Zajišťuje ústav

Ústav automatizace a měřicí techniky (UAMT)

Výsledky učení předmětu

Absolvent předmětu je schopen:
- provést rozbor úlohy pomocí vývojového diagramu;
- stanovit pro jednoduchý algoritmus jeho časová a paměťová 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;
- správně určit datový typ pro daný typ výpočtu (základní datové typy, typ ukazatel na datový typ, a složený datový typ);
- pracovat s dynamicky alokovanou pamětí (získání a uvolnění paměti, manipulace s daty v alokované paměti);
- pracovat se standardními vstupy, výstupy a soubory;

Prerekvizity

Absolvování kurzu BPC-UDP nebo kurzu s podobnou náplní.

Plánované vzdělávací činnosti a výukové metody

Metody vyučování zahrnují přednášky a počítačová cvičení. Student musí ve cvičeních odladit zadané úlohy.

Způsob a kritéria hodnocení

Až 40 bodů za laboratorní cvičení (2 testy každý za max. 20 bodů). Podmínkou udělení zápočtu je získání minimálně 15 bodů z testů ve cvičeních.
Až 60 bodů za závěrečnou zkoušku. Minimální požadovaný počet bodů ze závěrečné zkoušky je 20 bodů.
Zkouška z předmětu bude probíhat prezenčně.

Osnovy výuky

1. Úvod kurzu, pojem algoritmus, časová a paměťová složitost, dynamická alokace paměti, návrh API pro práci se soubory.
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. ADT TStack_array, ADT TStack_list.
3. Popis a vlastnosti ADT: Fronta, Množina, ADT TQueue_list, ADT TQueue_array, pojem iterátor, využití iterátorů u ADT.
4. Popis a vlastnosti ADT: Množina, Strom, (SkipList), unordered a ordered kolekce.
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 Fibonacci 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í složitost algoritmu.
12. Hašování.
13. AVL stromy, B-stromy, závěr kurzu.

Učební cíle

Cílem předmětu je seznámit studenty se základními pojmy z oblasti algoritmu a datových struktur jako: pojem algoritmus, výpočetní a paměťová složitost algoritmu, abstraktní datový typ, rekurzivní a nerekurzivní algoritmy, algoritmy třídění a vyhledávání.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

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.

Prerekvizity a korekvizity

Základní literatura

PROKOP, Jiří. Algoritmy v jazyku C a C++. Praha: Grada Publishing, 2008. 176 s. ISBN 978-80-247-3929-8 (CS)
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

eLearning: aktuální otevřený kurz

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

26 hod., nepovinná

Vyučující / Lektor

Ing. Petr Petyovský, Ph.D.

Osnova

1. Úvod kurzu, Pojem algoritmus, časová a paměťová složitost, dynamická alokace paměti, návrh API pro práci se soubory, signatura datového typu.
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, závěr kurzu.

Cvičení na počítači

39 hod., povinná

Vyučující / Lektor

Ing. Petr Petyovský, Ph.D.
Ing. Miloslav Richter, Ph.D.
Ing. Martin Čala, Ph.D.
Ing. Tomáš Macho, Ph.D.

Osnova

1. Krátké zopakování informací o standardních knihovnách jazyka C: printf, scanf formátovacích řetězců. Realizace ADT TVector, uložení vektoru do souboru pomocí API.
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

eLearning: aktuální otevřený kurz