Detail předmětu

Algoritmy a datové struktury

FEKT-BPC-ALDAk. rok: 2019/2020

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í.

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í.

Doporučená nebo povinná literatura

VEČERKA, Arnošt. Základní algoritmy. Skriptum Olomouc 2007. 91 s. (CS)
MAREŠ, Martin, VALLA, Tomáš. Průvodce labyrintem algoritmů. Praha: CZ.NIC 2017. 490 s. ISBN 978-80-88168-22-5. (CS)
WRÓBLEWSKI,Piotr. Algoritmy – Datové struktury a programovací techniky. Brno: Computer Press, 2004. 351 s. ISBN 80-251-0343-9. (CS)
PROKOP, Jiří. Algoritmy v jazyku C a C++. Praha: Grada Publishing, 2008. 176 s. ISBN 978-80-247-3929-8. (CS)
RICHTER, Miloslav, PETYOVSKÝ, Petr, HORÁK Karel a KALOVÁ Ilona. Praktické programování v CPP SL. Elektronické texty. Brno: 2004. (CS)

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ě.

Jazyk výuky

čeština

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.

Cíl

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.

Zařazení předmětu ve studijních plánech

  • Program BPC-AMT bakalářský, 1. ročník, letní semestr, 7 kreditů, povinný

  • Program EEKR-CZV celoživotní vzdělávání (není studentem)

    obor ET-CZV , 1. ročník, letní semestr, 7 kreditů, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

eLearning