Most of this page has been . Only Czech version will be used at the state exam: English version only serves the basic informative purpose to those not mastering Czech.
Theoretical Computer Science
- Probability. Basic concepts and probability properties;
random variable and its characteristics (mean value, variance, moments,…) and their use;
binomial, geometric and other distributions and their characteristics.
Markov and Čebyšev's inequality and their use;
Chernobyl estimates and their use;
random, especially Markov, processes and their properties;
entropy and information and their properties;
applications in Computer science.
- Algebra. Linear algebra; vector and matrix counts;
groups, circuits and arrays and their basic properties;
associations and their basic characteristics;
distributive, modular and Boolean unions;
universal algebras (basic terms, homomorphisms, congruences and factor algebras), variety, Birkhoff's theorem.
- Graphs and graph algorithms.
Basic concepts and ways of representation and searching;
trees and their representation and search;
planar charts and their properties, algorithms for minimal skeleton construction, for finding the shortest path,
for optimal pairing, for maximum flows, etc.;
data structures for graph algorithms;
random charts and their use; random graph algorithms.
- Automata. Finite deterministic, non-deterministic and probability automata and their properties (minimization, equivalence, decision making); regular languages and their properties; pumping lemma, storage automata and their properties; context-free languages and their properties; Chomsky grammars and their normal forms and their relation to automata models. Syntactic analysis of the most used models of context-free grammars; finite automata over infinite words; Turing machines and their properties (recursive and recursive countable sets, universality and halting problem); RAM and PRAM models and their categories. Cellular automata.
- Computational, communication and Kolmogorov's complexity.
Time and memory complexity and their properties;
Complexity classes for deterministic, non-deterministic and random
calculations and relationships between them; complete, especially
NP-complete, problems; evidence of NP-completeness;
P-NP problem and its implication; approximation of NP-problems;
approximation classes of complexity;
interactive proofing systems and zero-knowledge proofing systems;
communication complexity and its applications;
methods of proving lower estimates of communication complexity;
classes of communication complexity, basic concepts and
properties of Kolmogorov's complexity.
- Algorithms for solving computationally challenging problems.
Random algorithms of Monte Carlo and Las Vegas; random walks;
approximation algorithms and their potential; genetic algorithms;
quantum algorithms (Shor's factorization and Grover search algorithm).
- Coding, cryptography and cryptographic protocols.
Linear codes (definitions, properties, coding and decoding, important
examples of linear codes, cyclic codes (definitions,
algebraic characterization, coding and decoding, important
examples of cyclic codes), turbo codes and low-density codes,
private key cryptosystems, DES and AES cryptosystems,
public key cryptosystems, RSA cryptosystem and its properties,
cryptographic systems based on elliptic curves,
digital signature schemes, authentication protocols,
protocols for coin tossing, bit commitment and oblivious transfer,
steganography and watermarking, cryptographic machines and their history,
quantum cryptography (generating random secret class keys, quantum teleportation).
- Mathematical analysis. Systems of linear differential equations
and methods of their solution; curve integral.
Specialization on Logic
- Mathematical logic and computability. Pronunciation logic (propositional formulas, veracity, verifiability, completeness clause); predicate logic (axioms, semantics, verifiability); sentences of correctness, completeness, deduction and compactness; theories and models; Löwenheim-Skolem theorem; Gödel's theorem of completeness and incompleteness.
- Rice's theorem; creative and immune sets;
primitive, totally and partially recursive sets and functions.
Arithmetic sets and functions; Gödel and Rosser's theorem about incompleteness;
the second Gödel incompletness theorem.
MA007, IA038, IA046
- Semantics of programming languages.
Basic approaches to semantics of programming languages
(operational, denotational and axiomatic);
structural operational semantics and its variants;
equivalence of semantics;
basic concepts and methods of denotation semantics (CPO concept,
continuous functions between CPO, fixed point clause, recursion semantics);
equivalence of denotational and operational semantics.
- Petri nets. Basic features of the Petri nets (Border,
Coverage, Karp-Miller Tree, Weak Petri Computer,
Availability and Lifetime);
(non-)decisiveness of semantic equivalences and temporal logic
for the Petri nets; S-systems and S-variants, T-systems and T-variants;
Petri nets with free choice; Petri network modeling.
- Formal verification methods.
Principal verification methods and their comparison;
state explosion problem;
theorem proving as a deductive verification method;
LTL-model checking for finite and infinite state systems;
bounded model checking; symbolic execution; static analysis;
abstract interpretation; verification means.
- Theory, specifications and logic of processes.
Processes and transition systems with labels and their specifications;
operational semantics; process hierarchy;
the basic semantic equivalence of processes on transition
systems and their interrelationships;
possibilities of algorithmic verifiability of
semantic equivalences on infinite-state processes.
Modal logic (propositional modal logic, modal mu-calculus);
temporal logic (temporal operators, propositional temporal logic,
linear and branching time); processes and their properties;
verification of temporal properties;
model checking; automated verification.
- Lambda calculus. Lambda-Calculus Elements; transformation and reduction;
lambda-calculus and calculations (coding, recursive definitions,
lambda-computability, undecidable problems);
lambda-calculus (properties and applications);
domains and their construction; domain models.