Jdi na navigaci předmětu

Compulsory Topics (BIE)

topics are valid since SFE in June 2024

update 2. 5. 2024

BIE-SPOL-1Chomsky hierarchy of formal languages and grammars. Turing machines, universal Turing machine, recursive-enumerable and recursive languages. The P, NP, and NP-complete classes of problems.BIE-AAG
BIE-SPOL-2Regular 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
BIE-SPOL-3Context-free languages, context-free grammars, pushdown automata and its variants. Models of parsing of context-free languages.BIE-AAG
BIE-SPOL-4Basic notions of graph theory. Graph algorithms: breadth-first search and depth-first search, connected components, topological sort, distances in graphs, algorithms for minimum spanning tree construction and shortest paths in edge-weighted graphs.BIE-AG1
BIE-SPOL-5Binary heaps, binomial heaps. Search trees and their balancing. Hash tables.BIE-AG1
BIE-SPOL-6Asymmetric cryptosystems (the RSA cipher, the Diffie-Hellman protocol, the RSA digital signature), hash functions (SHA-2, HMAC).BIE-BEZ
BIE-SPOL-7Symmetric block and stream ciphers (AES, 3DES, RC4) – basic parameters, block cipher modes of operation (ECB, CBC, CFB, OFB, CTR, MAC), their basic description and vulnerabilities.BIE-BEZ
BIE-SPOL-8Public key infrastructure, key distribution, digital signature. Certificates, certificate authorities. Cryptographically secure pseudorandom number generators.BIE-BEZ
BIE-SPOL-9Relational database and relational algebra as a query language. The SQL language (SELECT, DDL, DML, DCL, TCL). Declaration of integrity constraints in DDL.BIE-DBS
BIE-SPOL-10Trasactions and their properties – ACID.BIE-DBS
BIE-SPOL-113 layers of data abstraction in databases (conceptual, implementational, physical). Structures for storying data in relational databases for fast access (basic structures, special structures, indexes, etc.).BIE-DBS
BIE-SPOL-12Systems of linear equations and their solvability, Frobenius theorem and related notions, characterization of a set of solutions, Gaussian elimination.BIE-LIN
BIE-SPOL-13Matrices: matrix-matrix multiplication, regular matrices, inverse matrices and its calculation, matrix eigenvalues and their calculation, matrix diagonalisation.BIE-LIN
BIE-SPOL-14Propositional logic: basic laws, complete systems of logical connectives, disjunctive and conjunctive normal forms.BIE-MLO
BIE-SPOL-15Predicate logic: definition of a formula, satisfiable and logically valid formulas, theory and its models, logical consequences of a theory.BIE-MLO
BIE-SPOL-16Processes and threads, their implementation. Synchronization tools. Classical synchronization problems. Thread scheduling. Allocation of resources, Coffman’s conditions, ways to resolve a deadlock.BIE-OSY
BIE-SPOL-17Virtualization of memory using the technique of paging, principles of translation of logical-to-physical addresses, page replacement algorithms.BIE-OSY
BIE-SPOL-18Data 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
BIE-SPOL-19Time and space complexities of algorithms. Searching algorithms (linear, binary), merging and sorting algorithms (BubbleSort, SelectSort, InsertSort, MergeSort, QuickSort). Lower bound of the sorting problem in the comparison model. Linear-time sorting algorithms.BIE-PA1
BIE-SPOL-20Recursive decomposition of a problem to subproblems using the Divide-and-Conquer method. Recursion vs. iteration. Dynamic programming.BIE-PA1
BIE-SPOL-21Object-oriented programming in C ++, encapsulation, inheritance, attributes, and methods, static attributes and methods, virtual methods, polymorphism, abstract classes, exceptions, templates, operator overloading, shallow and deep copy.BIE-PA2
BIE-SPOL-22Abstract data types, specification and implementation. Stack, queue, array, list, table, and set. Implementation using linked structures, trees, and arrays.BIE-PA2
BIE-SPOL-23ISO/OSI and TCP/IP network models. Link layer protocols. Switching and routing. Principles of internetworking devices.BIE-PSI
BIE-SPOL-24The TCP/IP protocol family (IPv4, IPv6, TCP, UDP, application layer protocols). Data flow control. NAT – principle and usage. DNS systems.BIE-PSI
BIE-SPOL-25Rules for calculating probabilities, Bayes’ formula. Random variables, common examples of distributons, cumulative distribution function, probability density function, moments. Independence of events and random variables. Central limit theorem, laws of large numbers.BIE-PST
BIE-SPOL-26Basics of mathematical statistics, random samples, point estimates of the expectation and variance, interval estimates for the expectation, testing statistical hypotheses regarding the expectation.BIE-PST
BIE-SPOL-27Combinational and sequential logic circuits (Mealy, Moore), their specification and implementation at the gate level. Logic function minimisation (using map representations).BIE-SAP
BIE-SPOL-28Architecture of a digital computer, instruction cycle, basic types of the instruction set architectures (ISA). Computer memory subsystem, memory hierarchy, cache memory.BIE-SAP
BIE-SPOL-29Representation of signed numbers and implementation of arithmetic operations (parallel adders/subtractors, arithmetic shifters, decoders, multiplexors, counters). Floating point number representations.BIE-SAP
BIE-SPOL-30Tools supporting the software development process: bug tracking and task management tools (common tools, bug/task life cycle), source code management tools (principles of cooperation, main benefits, common tools).BIE-SI1.2
BIE-SPOL-31Analytical domain class model, lifecycle of identified classes (goals, UML class diagram, UML state diagram).BIE-SI1.2
BIE-SPOL-32Methods for solution of recurrent equations, formulation and solution of recurrent equations for time complexity analysis of algorithms.BIE-ZDM
BIE-SPOL-33Modular arithmetics, introduction to number theory. Fermat’s Little Theorem, diophantine equations, linear congruences, Chineese Remainder Theorem.BIE-ZDM
BIE-SPOL-34Limit and derivative of a function (definition and properties, geometric interpretation), application to analysis of a graph of a function.BIE-ZMA
BIE-SPOL-35Basics of integral calculus (primitive function, indefinite integral, Riemann integral (definition, properties, and geometric interpretation)).BIE-ZMA
BIE-SPOL-36Numerical series (convergence, convergence tests, integral estimates of partial sums).BIE-ZMA

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