Zápočťák

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.

Hlavní témata

• Hornerovo schéma
• datové struktury – zásobník, fronta, halda, prioritní fronta, slovník
• rekurze
• třídění
  • SelectSort = procházení pole, vždy se hledá největší prvek
  • InsertSort = zařazení prvku mezi již setříděné
  • BubbleSort = výměna dvou prvků
  • HeapSort = nejprve zhaldování pole, potom vyndávám minimum
  • QuickSort = určíme pivota, rozdělíme na prvky menší rovny a větší rovny
  • MergeSort = slévání setříděných runů
  • složitost problému vnitřního třídění = n log n
  • CountingSort = počítáme počet výskytů daného čísla
  • BucketSort = nejprve pomocí CountingSortu spočítáme velikosti přihrádek, potom v daném poli určíme začátky přihrádek a nakonec data do přihrádek umístíme
  • RadixSort = víceprůchodový BucketSort, využívá stability, postupně třídí podle důležitosti parametru (vzestupně – nejdůležitější nakonec)
  • BucketSort třídění celých čísel podle číslic – čísla rozdělím do kyblíků podle číslice na dané pozici (postupuji zprava doleva – nejdříve řadím podle jednotek)
• halda
  • haldové operace
    • přidání prvku – přidává se na konec a vybublává se
    • odebrání minima – odebere se kořen, poslední prvek se dá na místo kořene a zabublá se (vyměňuju s menším)
  • rychlé zhaldování – postupuje se zprava doleva; nejdříve se zhaldujou podstromy, ty se spojí pomocí kořene a ten se zabublá atd.
• binární strom – průchod preorder/inorder/postorder
• binární vyhledávací strom
• rotace
  • pokud je balance B rovna 0 nebo 1, provádím rotaci
  • pokud je rovna 0 nebo –1, provádím dvojrotaci
• vyhledávání
  • DFS – pomocí rekurze nebo zásobníku
  • BFS – pomocí fronty
• výrazy
  • prefixová notace – rekurzí
  • postfixová notace – zásobníkem
  • infixová notace – rekurzí bez parametru nebo převodem na postfix
• (odhad faktoriálu)
• (složitost)