Obsah přednášek NMIN112 Programování 2
školní rok 2023/2024
13 přednášek
20. 2. 2024 - Algoritmy a jejich efektivita
Algoritmus - vlastnosti, důkaz správnosti, porovnávání kvality algoritmů.
Příklad: Eukleidův algoritmus.
Časová a prostorová složitost algoritmů.
Asymptotická složitost, notace „velké O, Omega, Theta“.
VIDEO z distanční výuky 2020/21
27. 2. 2024 - Základní algoritmy
Složitost algoritmu v nejhorším, nejlepším a průměrném případě.
Složitost problému.
Dělitelnost, rozklad čísla na cifry, ciferný součet.
Prvočísla – test prvočíselnosti, Eratosthenovo síto.
„Dlouhá čísla“ – uložení, operace.
Polynomy – vyhodnocení (Hornerovo schéma), operace.
Převody mezi číselnými soustavami.
Rychlé umocňování.
VIDEO z distanční výuky 2020/21
5. 3. 2024 – Vyhledávání a třídění
Vyhledávání v poli – sekvenční, pomocí zarážky, binární vyhledávání (půlení intervalů).
Třídění čísel v poli – přímé metody (SelectSort, InsertSort, BubbleSort).
Rychlejší třídění – iterativní implementace třídění sléváním (MergeSort).
Vnější třídění.
Složitost problému vnitřního třídění.
VIDEO z distanční výuky 2020/21
12. 3. 2024 - Základní datové struktury
Reprezentace dat v paměti – uložení čísel a znaků, pole a seznamy, objekty.
Abstraktní datové typy: zásobník, fronta, halda.
Implementace haldy v poli, haldové třídění (HeapSort).
Sestrojení haldy v lineárním čase.
VIDEO z distanční výuky 2020/21
19. 3. 2024 - Spojové seznamy
Další abstraktní datové typy: prioritní fronta, slovník (hešování, kolize).
Dynamické datové struktury spojované ukazateli.
Lineární spojové seznamy – operace, příklady použití.
Druhy spojových seznamů.
VIDEO z distanční výuky 2020/21
26. 3. 2024 - Rekurze, binární a obecné stromy
Rekurze – princip, příklady, efektivita.
Jednoduché rekurzivní funkce.
Rekurzivní výpočet Fibonacciho čísel, kešování mezivýsledků (memoizace).
Binární strom – reprezentace, procházení do hloubky a do šířky.
Obecný strom – reprezentace, průchod.
VIDEO z distanční výuky 2020/21
2. 4. 2024 - Binární vyhledávací stromy, rekurzivní generování
Binární vyhledávací strom – reprezentace, operace.
Princip vyvažování, dokonale vyvážený strom a AVL-strom.
Rekurzivní generování – příklady.
VIDEO z distanční výuky 2020/21
9. 4. 2024 - Grafy - reprezentace, procházení
Základní pojmy z teorie grafů, základní grafové problémy.
Reprezentace grafu v programu.
Procházení grafu do hloubky a do šířky.
Řešení grafových problémů procházením do hloubky a do šířky.
VIDEO z distanční výuky 2020/21
16. 4. 2024 - Grafové algoritmy
Faktorové množiny, jejich využití při řešení grafových problémů.
Topologické uspořádání orientovaného grafu.
Minimální kostra v ohodnoceném grafu (Kruskalův algoritmus).
Nejkratší cesta v ohodnoceném grafu (Dijkstrův algoritmus).
VIDEO z distanční výuky 2020/21
23. 4. 2024 - Prohledávání stavového prostoru do hloubky, algoritmus minimaxu
Prohledávání do hloubky – princip, příklady použití, implementace.
Zrychlení pomocí ořezávání a heuristik.
Strom hry, algoritmus minimaxu, alfa-beta prořezávání.
VIDEO z distanční výuky 2020/21
Plán na 30. 4. 2024 - Prohledávání stavového prostoru do šířky, metoda Rozděl a panuj
Prohledávání do šířky – princip, příklady použití, implementace.
Metoda Rozděl a panuj – princip, příklady použití (vyhodnocení výrazu, Hanojské věže).
MergeSort – rekurzivní implementace.
QuickSort, možnosti volby pivota.