1. Teoretické základy informatiky

1. Výroková logika, jazyk, formule, pravdivost, vyplývání, tautologie
2. [-] Booleovské funkce, funkčně úplné systémy
3. [-] Úplné konjunktivní a disjunktivní normální formy
4. Množiny, množinové operace a vztahy, potenční množina, kartézský součin, číselné množiny, spočetné a nespočetné množiny
5. [-] Relace, binární relace a jejich reprezentace, operace s relacemi
6. [-] Funkce (zobrazení) a jejich vlastnosti
7. [-] Binární relace na množině a jejich vlastnosti
8. [-] Ekvivalence a rozklady
9. Uspořádání, Hasseovy diagramy, význačné prvky, svazy
10. Indukce a rekurze, matematická indukce a její varianty, strukturální indukce
11. [-] Permutace, variace, kombinace
12. Pravděpodobnost, Laplaceova definice pravděpodobnosti, pravděpodobnostní prostor, vlastnosti pravděpodobnosti
13. Náhodná veličina, střední hodnota
14. Orientované a neorientovaný grafy, izomorfismus, podgrafy, pojmy k cestování
15. [-] Hledání nejkratší cesty, Dijkstrův algoritmus
16. [-] Minimální kostra grafu, Kruskalův algoritmus
17. [-] Stromy, kořenové stromy, vztahy mezi výškou, počtem vrcholů, počtem listů
18. [-] Binomická věta
19. [-] Princip inkluze a exkluze
20. [-] Dirichletův princip
21. Základní syntaktické a sémantické pojmy výrokové logiky
22. [-] Přehledově dokazatelnost ve výrokové logice
23. Syntax a sémantika predikátové logiky
24. [-] Čísla a číselné obory
25. Vybrané číselné funkce a rychlosti jejích růstu
26. Dělitelnost, prvočísla, věty o jednoznačnosti
27. Největší společný dělitel a nejmenší společný násobek
28. Euklidův algoritmus
29. Kongruence modulo n a její vlastnosti

---

1. [-] Matice, operace s maticemi, hodnost, determinant
2. [-] Vektorové prostory, podprostory, báze a dimenze, matice přechodu
3. [-] Eukleidovské vektorové prostory, ortogonální a ortonormální báze, Schwarzova nerovnost, Schmidtova ortogonalizační metoda
4. [-] Soustavy lineárních rovnic, Frobeniova věta, Gaussova eliminační metoda, Cramerovo pravidlo
5. [-] Lineární zobrazení a transformace a jejich matice

---

1. [-] Funkce jedné reálné proměnné, základní vlastnosti
2. Posloupnosti a jejich limity, limes superior, limes inferior
3. Limita funkce včetně nevlastních, jednostranné limity
4. Spojitost funkce - spojitost v bodě, spojitost na intervalu
5. Vlastnosti spojitých funkcí, spojitost složené a inverzní funkce
6. Derivace funkce a její geometrický význam - Pravidla pro derivování funkcí, derivace složené funkce, derivace inverzní funkce, derivace elementárních funkcí
7. Průběh funkce - základní věty diferenciálního počtu, extrémy funkce, konvexní a konkávní křivky, asymptoty
8. Neurčitý integrál a metody jeho výpočtu
9. Riemannův určitý integrál - definice, základní věta integrálního počtu, metody výpočtu
10. Geometrická interpretace určitého integrálu

---

1. [-] Formální jazyky a jejich hierarchie
2. [-] Regulární jazyky (definice, uzávěrové vlastnosti)
3. [-] Konečné automaty deterministické a nedeterministické
4. [-] Regulární výrazy, automaty s e-přechody
5. [-] Minimalizace konečného deterministického automatu
6. [-] Pumping lemma
7. [-] Bezkontextové jazyky a jejich vlastnosti (uzávěrové vlastnosti, jednoznačnost)
8. [-] Zásobníkové automaty
9. [-] Deterministické zásobníkové automaty
10. [-] Deterministické bezkontextové jazyky

---

1. [-] Turingův stroj, nedeterministický TS
2. [-] Jazyk přijímaný TS, jazyk rozhodovaný TS
3. [-] Church-Turingova teze, varianty TS
4. [-] Částečně rekurzivní a rekurzivní jazyky, jazyky a rozhodovací problémy
5. [-] Vztah rekurzivních a částečně rekurzivních jazyků
6. [-] Uzávěrové vlastnosti jazyků TS
7. [-] Riceova věta
8. [-] Složitost algoritmu (časová a paměťová)
9. [-] Třída P, třída NP, důvody jejich zavedení, jejich vzájemný vztah
10. [-] NP-úplné problémy
11. [-] Cook-Levinova věta
12. [-] Příklady NP-úplných problémů, dokazování NP-úplnosti
13. [-] Třída PSPACE, její vztah k třídám P a NP, PSPACE-úplné problémy

---

1. [-] Algoritmus, problém, časová složitost algoritmu v nejhorším a průměrném případě
2. [-] O-notace a růst funkcí, definice, vlastnosti, příklady použití
3. [-] Lineární datové struktury - seznam, zásobník, fronta
4. Problém třídění, rozdělení třídicích algoritmů, dolní mez složitosti třídění porovnáváním
5. Základní metody třídění - insertion sort, select sort, bubble sort
6. [-] Quick sort a jeho složitost
7. [-] Merge sort a jeho složitost
8. [-] Heap sort a jeho složitost
9. [-] Další metody třídění - counting sort, radix sort, bucket sort
10. Vnější třídění
11. [-] Pořádkové statistiky

---

1. [-] Vyhledávání v lineárních datových strukturách
2. [-] Binární vyhledávací stromy, operace a jejich složitosti
3. [-] AVL stromy, operace a jejich složitost
4. [-] B stromy, operace a jejich složitost
5. [-] Hashovací tabulky, metody řešení kolizí
6. [-] Základní grafové algoritmy - průchod do šířky, průchod do hloubky, topologické uspořádání