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

č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)

Vstupní znalosti

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

Pravidla hodnocení a ukončení předmětu

Až 40 bodů za počítačová 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 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

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

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)

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, B-stromy, závěr kurzu.

Cvičení na počítači

39 hod., povinná

Vyučující / Lektor

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

Osnova

1. Realizace ADT TVector, zopakování vlastností knihoven jazyka C: printf, scanf formátovacích řetězců. 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).