Obsah přednášek NMIN112 Programování 2
školní rok 2025/2026
13 přednášek
18. 2. 2026 - 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“.
Složitost algoritmu v nejhorším, nejlepším a průměrném případě.
Složitost problému.
25. 2. 2026 - Základní algoritmy
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í.
Vyhledávání v poli – sekvenční, pomocí zarážky, binární vyhledávání (půlení intervalů).
4. 3. 2026 - Řazení dat v poli
Řazení dat v poli – přímé metody (SelectSort, InsertSort, BubbleSort).
Rychlejší metody řazení – iterativní implementace třídění sléváním (MergeSort).
Princip a použití vnějšího třídění.
Složitost problému vnitřního třídění.
Řazení s lineární složitostí (CountingSort, BucketSort).
11. 3. 2026 - Základní datové struktury
Reprezentace dat v paměti – uložení čísel a znaků, pole a seznamy.
Abstraktní datové typy: zásobník, fronta, halda.
Implementace haldy v poli.
Haldové třídění (HeapSort).
18. 3. 2026 – Další datové struktury, spojové seznamy
Sestrojení haldy v lineárním čase.
Prioritní fronta.
Slovník - implementace pomocí hešování, řešení kolizí, efektivita operací.
Dynamické datové struktury spojované ukazateli.
Lineární spojové seznamy – operace, příklady použití.
25. 3. 2026 - Rekurze, binární stromy
Druhy spojových seznamů.
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.
1. 4. 2026 - Binární vyhledávací stromy, rekurzivní generování
Informace o zkouškách – termíny, úlohy, hodnocení.
Výpočty v binárních stromech.
Binární vyhledávací strom – reprezentace, operace.
Princip vyvažování, dokonale vyvážený strom a AVL-strom.
Rekurzivní generování – příklady.
8. 4. 2026 - 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.
15. 4. 2026 - Grafové algoritmy
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).
22. 4. 2026 - 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í.
29. 4. 2026 - 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.
6. 5. 2026 - Dynamické programování
Princip metody dynamického programování, typy řešených úloh a způsoby implementace.
Příklady použití dynamického programování při řešení různých úloh.
13. 5. 2026 - rektorský den (výuka zrušena)
20. 5. 2026 - K-tý nejmenší prvek, aritmetické výrazy
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í.