Obsah přednášek NMIN112 Programování 2
školní rok 2024/2025
14 přednášek
19. 2. 2025 - 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“.
26. 2. 2025 - 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í.
5. 3. 2025 – 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í.
Třídění s lineární složitostí (CountingSort).
12. 3. 2025 - Základní datové struktury
Reprezentace dat v paměti – uložení čísel a znaků, pole a seznamy.
Slovník - hešování, řešení kolizí, efektivita operací.
Abstraktní datové typy: zásobník, fronta, halda, prioritní fronta.
Implementace haldy v poli, haldové třídění (HeapSort).
19. 3. 2025 - Spojové seznamy
Doplnění k minulé přednášce: Sestrojení haldy v lineárním čase.
Dynamické datové struktury spojované ukazateli.
Lineární spojové seznamy – operace, příklady použití.
Druhy spojových seznamů.
26. 3. 2025 - 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.
2. 4. 2025 - 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.
9. 4. 2025 - 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.
16. 4. 2025 - Grafové algoritmy
Informace o zkouškách – termíny, úlohy, hodnocení.
Faktorové množiny (struktura Union-Find), použ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).
23. 4. 2025 - 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í.
30. 4. 2025 - 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.
7. 5. 2025 - Dynamické programování
Princip metody dynamického programování, příklady použití.
14. 5. 2025 - K-tý nejmenší prvek, aritmetické výrazy
Informace o zkouškách – typy zadávaných úloh.
Reprezentace aritmetického výrazu binárním stromem.
Notace aritmetického výrazu (infix, prefix, postfix) – vyhodnocení výrazu.
Převody aritmetických notací.
K-tý nejmenší prvek, medián.
Algoritmus QuickSelect, řešení s lineární složitostí.
21. 5. 2025 - Různé algoritmy
Třídění s lineární složitostí (CountingSort, BucketSort, RadixSort).
Předvýpočty.
Hladové algoritmy.
Problém batohu.