čeština

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;

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

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

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

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

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.

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)