NPRG062 Algoritmizace
školní rok 2025/2026
11 přednášek
30. 9. 2025 – Algoritmy a jejich efektivita
Úvodní informace o obsahu přednášky a studijních materiálech.
Algoritmus - vlastnosti, důkaz správnosti, porovnávání kvality algoritmů.
Příklady: Eukleidův algoritmus, problém stabilních manželství.
Časová a prostorová složitost algoritmů.
7. 10. 2025 – Asymptotická složitost, základní algoritmy s čísly
Č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.
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í.
14. 10. 2025 – Číselné soustavy, vyhledávání a řazení dat
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ů).
Řazení dat v poli – přímé metody (SelectSort, InsertSort, BubbleSort).
Rychlejší třídění – iterativní implementace třídění sléváním (MergeSort).
Princip vnějšího třídění (třídění souborů).
21. 10. 2025 – imatrikulace (výuka v 1. ročníku celý den zrušena)
28. 10. 2025 – státní svátek
4. 11. 2025 – Třídicí algoritmy, reprezentace dat
Složitost problému vnitřního třídění.
Třídění s lineární složitostí (CountingSort, BucketSort, RadixSort).
Reprezentace dat v paměti, pole a seznamy, složitost operací.
Lineární spojový seznam jako alternativa k poli a seznamu.
Abstraktní datové typy: zásobník, fronta.
11. 11. 2025 – Základní datové struktury
Další abstraktní datové typy: halda, prioritní fronta, slovník, vyhledávací strom.
Haldové operace, implementace haldy v poli.
Třídění haldou (HeapSort).
Konstrukce haldy v lineárním čase.
Prioritní fronta, implementace haldou.
Slovník a jeho implementace pomocí hešování.
Hešovací tabulky, metody řešení kolizí.
Binární vyhledávací strom, porovnání se slovníkem.
18. 11. 2025 – Rekurze, rekurzivní generování
Rekurze – princip, příklady, efektivita (kešování mezivýsledků - memoizace).
Rekurzivní generování – algoritmy založené na zkoušení všech možností.
25. 11. 2025 – Binární stromy
Binární strom – způsoby reprezentace, příklady použití.
Procházení binárním stromem do hloubky a do šířky.
Různé způsoby řešení jednoduchých úloh na binárních stromech (počet vrcholů, výška).
Binární vyhledávací strom – definice, operace.
Dokonale vyvážený strom a výškově vyvážený strom, princip vyvažování.
Obecný strom – možnosti reprezentace, průchod, příklady použití (trie).
2. 12. 2025 – Prohledávání stavového prostoru do hloubky a do šířky
Informace o zkouškách – termíny, průběh, hodnocení, typy příkladů.
Prohledávání stavového prostoru do hloubky – princip, příklady použití, realizace.
Zrychlení výpočtu pomocí ořezávání a heuristik.
Prohledávání stavového prostoru do šířky – princip, příklady použití, realizace (algoritmus vlny a zpětný chod).
Plán na 9. 12. 2025 – Algoritmus minimaxu, metoda Rozděl a panuj
Hra s úplnou informací, strom hry, algoritmus minimaxu, alfa-beta prořezávání.
Metoda Rozděl a panuj – princip, příklady použití.
Vyhodnocení aritmetického výrazu.
MergeSort (rekurzivní implementace).