- Výroková logika, jazyk, formule, pravdivost, vyplývání, tautologie, základní syntaktické a sémantické pojmy výrokové logiky
- Booleovské funkce, funkčně úplné systémy
- Úplné konjunktivní a disjunktivní normální formy
- Přehledově dokazatelnost ve výrokové logice
- Syntax a sémantika predikátové logiky
- 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
- Uzávěry binárních relací
- Ekvivalence a rozklady
- Uspořádání, Hasseovy diagramy, význačné prvky, svazy
- Konečné a nekonečné množiny, spočetné množiny, příklady, existence, nespočetné množiny, diagonální metoda
- Porovnání velikosti množin, Cantorova-Bernsteilova věta, Cantorova věta
- Indukce a rekurze, matematická indukce a její varianty, strukturální indukce
- Pravidlo součtu a součinu, permutace, variace, kombinace
- Binomická věta
- Princip inkluze a exkluze
- Pravděpodobnost, Laplaceova definice, pravděpodobnostní prostor, náhodná veličina, střední hodnota, vlastnosti pravděpodobnosti
- Orientované a neorientované grafy, izomorfismus, podgrafy, pojmy k cestování, stupně vrcholů, souvislost
- 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ů
- Čí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í, transformace a jejich matice
- Funkce jedné reálné proměnné, základní vlastnosti
- Posloupnosti a jejich limity, limes superior, limes inferior
- Limita a spojitost funkce
- 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é a nedeterministické
- Turingův stroj (TS), 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í
- 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
- Lineární datové struktury - seznam, zásobník, fronta
- 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í