- Výroková logika, jazyk, formule, pravdivost, vyplývání, tautologie
- Booleovské funkce, funkčně úplné systémy
- Úplné konjunktivní a disjunktivní normální formy
- 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
- Relace, binární relace a jejich reprezentace, operace s relacemi
- Funkce (zobrazení) a jejich vlastnosti
- Binární relace na množině a jejich vlastnosti
- Ekvivalence a rozklady
- Uspořádání, Hasseovy diagramy, význačné prvky, svazy
- Indukce a rekurze, matematická indukce a její varianty, strukturální indukce
- Permutace, variace, kombinace
- Pravděpodobnost, Laplaceova definice pravděpodobnosti, pravděpodobnostní prostor, vlastnosti pravděpodobnosti
- Náhodná veličina, střední hodnota
- Orientované a neorientovaný grafy, izomorfismus, podgrafy, pojmy k cestování
- Hledání nejkratší cesty, Dijkstrův algoritmus
- Minimální kostra grafu, Kruskalův algoritmus
- Stromy, kořenové stromy, vztahy mezi výškou, počtem vrcholů, počtem listů
- Binomická věta
- Princip inkluze a exkluze
- Dirichletův princip
- Základní syntaktické a sémantické pojmy výrokové logiky
- Přehledově dokazatelnost ve výrokové logice
- Syntax a sémantika predikátové logiky
- Čísla a číselné obory
- Vybrané číselné funkce a rychlosti jejích růstu
- Dělitelnost, prvočísla, věty o jednoznačnosti
- Největší společný dělitel a nejmenší společný násobek
- Euklidův algoritmus
- Kongruence modulo n a její vlastnosti
- Matice, operace s maticemi, hodnost, determinant
- Vektorové prostory, podprostory, báze a dimenze, matice přechodu
- Eukleidovské vektorové prostory, ortogonální a ortonormální báze, Schwarzova nerovnost, Schmidtova ortogonalizační metoda
- Soustavy lineárních rovnic, Frobeniova věta, Gaussova eliminační metoda, Cramerovo pravidlo
- Lineární zobrazení a transformace a jejich matice
- Funkce jedné reálné proměnné, základní vlastnosti
- Posloupnosti a jejich limity, limes superior, limes inferior
- Limita funkce včetně nevlastních, jednostranné limity
- Spojitost funkce - spojitost v bodě, spojitost na intervalu
- Vlastnosti spojitých funkcí, spojitost složené a inverzní funkce
- Derivace funkce a její geometrický význam - Pravidla pro derivování funkcí, derivace složené funkce, derivace inverzní funkce, derivace elementárních funkcí
- Průběh funkce - základní věty diferenciálního počtu, extrémy funkce, konvexní a konkávní křivky, asymptoty
- Neurčitý integrál a metody jeho výpočtu
- Riemannův určitý integrál - definice, základní věta integrálního počtu, metody výpočtu
- Geometrická interpretace určitého integrálu
- Formální jazyky a jejich hierarchie
- Regulární jazyky (definice, uzávěrové vlastnosti)
- Konečné automaty deterministické a nedeterministické
- Regulární výrazy, automaty s e-přechody
- Minimalizace konečného deterministického automatu
- Pumping lemma
- Bezkontextové jazyky a jejich vlastnosti (uzávěrové vlastnosti, jednoznačnost)
- Zásobníkové automaty
- Deterministické zásobníkové automaty
- Deterministické bezkontextové jazyky
- Turingův stroj, nedeterministický TS
- Jazyk přijímaný TS, jazyk rozhodovaný TS
- Church-Turingova teze, varianty TS
- Částečně rekurzivní a rekurzivní jazyky, jazyky a rozhodovací problémy
- Vztah rekurzivních a částečně rekurzivních jazyků
- Uzávěrové vlastnosti jazyků TS
- Riceova věta
- Složitost algoritmu (časová a paměťová)
- Třída P, třída NP, důvody jejich zavedení, jejich vzájemný vztah
- NP-úplné problémy
- Cook-Levinova věta
- Příklady NP-úplných problémů, dokazování NP-úplnosti
- Třída PSPACE, její vztah k třídám P a NP, PSPACE-úplné problémy
- Algoritmus, problém, časová složitost algoritmu v nejhorším a průměrném případě
- O-notace a růst funkcí, definice, vlastnosti, příklady použití
- Lineární datové struktury - seznam, zásobník, fronta
- Problém třídění, rozdělení třídicích algoritmů, dolní mez složitosti třídění porovnáváním
- Základní metody třídění - insertion sort, select sort, bubble sort
- Quick sort a jeho složitost
- Merge sort a jeho složitost
- Heap sort a jeho složitost
- Další metody třídění - counting sort, radix sort, bucket sort
- Vnější třídění
- Pořádkové statistiky
- Vyhledávání v lineárních datových strukturách
- Binární vyhledávací stromy, operace a jejich složitosti
- AVL stromy, operace a jejich složitost
- B stromy, operace a jejich složitost
- Hashovací tabulky, metody řešení kolizí
- Základní grafové algoritmy - průchod do šířky, průchod do hloubky, topologické uspořádání