Jdi na navigaci předmětu

Compulsory Topics (BIE21)

topics are valid since SFE in June 2024

BIE-SPOL.21-1Regular languages: Deterministic and nondeterministic finite automata. Determinization of a finite automaton. Minimization of a deterministic finite automaton. Operations on finite automata. Regular grammars, expressions, and equations.BIE-AAG.21
BIE-SPOL.21-2Context-free languages, context-free grammars, pushdown automata and its variants. Models of parsing of context-free languages.BIE-AAG.21
BIE-SPOL.21-3Basic notions of graph theory. Graph algorithms: breadth-first search, connected components, topological sort, distances in graphs, and algorithms for minimum spanning tree construction and shortest paths in edge-weighted graphs.BIE-AG1.21
BIE-SPOL.21-4Binary heaps, binomial heaps. Binary search trees and their balancing. Hashing.BIE-AG1.21
BIE-SPOL.21-5Relational databases and relational algebra as a query language. The SQL language (SELECT, DDL, DML, DCL, TCL). Declaration of integrity constraints in DDL.BIE-DBS.21
BIE-SPOL.21-6Trasactions and their properties – ACID.BIE-DBS.21
BIE-SPOL.21-7Propositional logic, formulas and their satisfiability, logical equivalence and consequence. Universal systems of connectives, disjunctive and conjunctive normal forms, full forms.BIE-DML.21
BIE-SPOL.21-8Fundamentals of number theory, divisibility, EEA and Diophantine equations, prime numbers. Modular arithmetic, Fermat’s little theorem, Euler’s theorem. Linear congruences, Chinese remainder theorem.BIE-DML.21
BIE-SPOL.21-9Asymmetric cryptosystems (RSA encryption, Diffie-Hellman, RSA digital signature), hash functions (SHA2, HMAC), digital signature. Certificates, certification authorities.BIE-KAB.21
BIE-SPOL.21-10Symmetric ciphers - block and stream, basic properties, operation modes of block ciphers (description and vulnerabilities).BIE-KAB.21
BIE-SPOL.21-11Systems of linear equations: Frobenius theorem and related notions, properies and characterization of sets of solutions, Gauss elimination method.BIE-LA1.21
BIE-SPOL.21-12Matrices: matrix-matrix multiplication, regular matrices, inverse matrices and their calculation, matrix eigenvalues and their calculation, matrix diagonalisation.BIE-LA1.21
BIE-SPOL.21-13Limit of a sequence, limit and continuity of a real-valued functions of one real variable, methods of computation of a limits, asymptotic behavior of functions and sequences (lower, upper, and tight asymptotic bounds, asymptotic equivalence).BIE-MA1.21
BIE-SPOL.21-14Differential calculus of a real-valued functions of one real variable: derivative and its geometric meaning, relation of derivatives and monotonicity and convexity, local extrema of real-valued functions of one real variable, asymptotes of a function.BIE-MA1.21
BIE-SPOL.21-15Integral calculus of real-valued functions of one real variable (indefinite integral, Riemann definite integral, methods of integration by parts and substitution), real number series and criteria of their convergence.BIE-MA2.21
BIE-SPOL.21-16Multivariate functions: differential calculus of multivariate functions (limit, partial derivative, total derivative, gradient, Hessian matrix), types of definitiness of a matrix, necessary conditions and sufficient conditions for existence of local extrema of multivariate functions (without constraints).BIE-MA2.21
BIE-SPOL.21-17Processes and threads, their implementation, mechanisms for thead synchronization. Classical synchronization problems. Thread deadlocks, allocation of resources, Coffman’s conditions, strategies of handling deadlocks.BIE-OSY.21
BIE-SPOL.21-18Virtualization of main memory by paging, principles of logical-to-physical address translation, structure of page tables, page replacement algorithms.BIE-OSY.21
BIE-SPOL.21-19Data types in programming languages. Statically and dynamically allocated variables, linked lists. Modular programming, procedures and functions, input and output parameters. Compiler, linker, debugger.BIE-PA1.21
BIE-SPOL.21-20Time and space complexity. Algorithms for searching in number sequences (sequential, interval halving), merging and sorting (BubbleSort, SelectSort, InsertSort, MergeSort, QuickSort). Lower bound for sorting in the comparison model. Sorting in linear time.BIE-PA1.21 + BIE-AG1.21
BIE-SPOL.21-21Recursive decomposition of a problem to subproblems using the Divide-and-Conquer method. Recursion vs. iteration. Dynamic programming.BIE-PA1.21 + BIE-AG1.21
BIE-SPOL.21-22Object-oriented programming in C ++, encapsulation, inheritance, instance and static attributes and methods, virtual methods, polymorphism, abstract classes, exceptions, templates, operator overloading, shallow and deep copy.BIE-PA2.21
BIE-SPOL.21-23Abstract data types, specification and implementation. Stack, queue, array, list, table, and set. Implementation using linked structures, trees, and arrays.BIE-PA2.21
BIE-SPOL.21-24ISO/OSI model, data encapsulation and decapsulation, IP addressing principle. Link layer, sublayers LLC and MAC, devices, switching principle. Virtual networks (VLANs). Network layer, routers, routing principle, protocols IPv4 and IPv6, static and dynamic routing.BIE-PSI.21
BIE-SPOL.21-25Transport layer, protocol TCP, packet delivery reliability, congestion, comparison with protocol UDP. Network address translation (NAT) at the network layer and at the transport layer. Domain Name System (DNS).BIE-PSI.21
BIE-SPOL.21-26Rules for calculating probabilities, Bayes' formula. Random variables, common examples of distributions, cumulative distribution function, probability density function, moments. Independence of events and random variables. Central limit theorem, laws of large numbers.BIE-PST.21
BIE-SPOL.21-27Basics of mathematical statistics, random samples, point estimates of the expectation and variance, interval estimates for the expectation, testing of statistical hypotheses regarding the expectation.BIE-PST.21
BIE-SPOL.21-28Combinational and sequential logic circuits (Mealy, Moore), their specification and implementation at the gate level. Logic function minimisation using map representations.BIE-SAP.21
BIE-SPOL.21-29Architecture of a digital computer, instruction cycle, basic types of the instruction set architectures (ISA). Computer memory subsystem, memory hierarchy, cache memory.BIE-SAP.21
BIE-SPOL.21-30Representation of signed numbers and implementation of arithmetic operations (parallel adders/subtractors, arithmetic shifters, decoders, multiplexors, counters). Floating point number representations.BIE-SAP.21

📄 The table is available also in CSV (semicolon-separated values). 🔙 History of changes is on GitLab.