Sylabus
* Algoritmy a jejich efektivita.
- Algoritmus - vlastnosti, důkaz správnosti, porovnávání kvality algoritmů.
- Časová a paměťová složitost algoritmů, asymptotická složitost, notace „velké O“.
- Složitost algoritmu v nejhorším, nejlepším a průměrném případě.
* Základní algoritmy a techniky.
- Dělitelnost - Eukleidův algoritmus, prvočíselný rozklad.
- Prvočísla - test prvočíselnosti, Eratosthenovo síto.
- Rozklad čísla na cifry, převody mezi číselnými soustavami.
- „Dlouhá čísla“ - uložení, operace.
- Hornerovo schéma, rychlé umocňování.
* Základní datové struktury.
- Vyhledávání v poli - sekvenční, binární.
- Abstraktní datové typy: zásobník, fronta, prioritní fronta, slovník.
- Hešovací tabulky - princip, řešení kolizí.
- Halda. Binární vyhledávací strom, princip vyvažování.
* Třídění.
- Třídění čísel v poli - přímé metody (SelectSort, InsertSort, BubbleSort).
- Haldové třídění (HeapSort), QuickSort.
- Složitost problému vnitřního třídění.
- Přihrádkové třídění (CountingSort, BucketSort, RadixSort).
- Poznámka o vnějším třídění.
* Rekurze.
- Rekurze - princip, příklady, efektivita.
- Binární strom - reprezentace, prohledávání, použití.
- Reprezentace aritmetického výrazu binárním stromem.
- Notace aritmetického výrazu (infix, prefix, postfix) - vyhodnocení, převody.
- Obecný strom - reprezentace, průchod, použití.
* Prohledávání stavového prostoru.
- Rekurzivní algoritmy založené na zkoušení všech možností - backtracking.
- Prohledávání do hloubky a do šířky - princip, použití, realizace.
- Zrychlení pomocí ořezávání a heuristik.
- Strom hry, algoritmus minimaxu, alfa-beta prořezávání.
* Základní grafové algoritmy.
- Reprezentace grafu.
- Prohledávání grafů do hloubky a do šířky a jejich aplikace.
* Obecné metody návrhu algoritmů.
- Zrychlení předvýpočtem.
- Hladový algoritmus.
- Metoda „Rozděl a panuj“.
- Memoizace.
Anotace
Úvodní kurz základních algoritmů, složitosti algoritmů a datových struktur pro posluchače prvního ročníku bakalářského studia informatiky a učitelství informatiky.