# 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)