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.

Plán na 11. 11. 2025 - Základní datové struktury

Další abstraktní datové typy: halda, prioritní fronta, slovník, množina, vyhledávací strom.

Haldové operace, implementace haldy v poli.

Haldové třídění (HeapSort).

Konstrukce haldy v lineárním čase.

Slovník a jeho implementace pomocí hešování.

Hešovací tabulky, metody řešení kolizí.

Vyhledávací stromy.