Příprava studijního programu Informatika je podporována projektem financovaným z Evropského sociálního fondu a rozpočtu hlavního města Prahy.

Praha & EU: Investujeme do vaší budoucnosti

Table of Contents

The exam based on SFE topics consists from two questions, one is based on SFE topics from compulsory courses of the degree study programme and the second one is based on SFE topics from the branch of study.

The question shall start with a copy of the topics as can be seen here. The question can be extended or clarified by the committee for the SFE.

Column **Subject** refers to the main subject of the topic, but the topic can also be found in other subjects.

# | Label | Topic | Subject |
---|---|---|---|

1. | TO-BIE-SPOL-1 | Propositional logic - truth tables, disjunctive and conjunctive normal forms, universal system of logical connectives, logical consequence and its verification. Boolean algebra (language, properties, ordering, examples). | BIE-MLO |

2. | TO-BIE-SPOL-2 | Predicate logic - language, interpretation, satisfaction of formulas, logical consequence and its verification, theories and models. | BIE-MLO |

3. | TO-BIE-SPOL-3 | Data types in programming languages. Statically and dynamically allocated variables, linked lists. Modular programming, procedures and functions, input and output parameters. Preprocessor, compiler, linker, debugger. | BIE-PA1 |

4. | TO-BIE-SPOL-4 | Time and space complexities of algorithms. Searching algorithms (linear, binary), sorting algorithms (Bubble-sort, Select-sort, Insert-sort, Merge-sort, Quick-sort). | BIE-PA1 |

5. | TO-BIE-SPOL-5 | The decomposition of the problem, recursion. Recursion vs. iteration. | BIE-PA1 |

6. | TO-BIE-SPOL-6 | Limit and derivative of a function (definition and properties, geometric interpretation), application to analysis of a graph of a function. | BIE-ZMA |

7. | TO-BIE-SPOL-7 | Basics of integral calculus (primitive function, indefinite integral, Riemann integral (definition, properties, and geometric interpretation)). | BIE-ZMA |

8. | TO-BIE-SPOL-8 | Numerical series (convergence, convergence tests, integral estimates of partial sums). | BIE-ZMA |

9. | TO-BIE-SPOL-9 | Systems of linear equations and their solvability, Rouché–Capelli-Frobenius theorem and related notions, characterization of a set of solutions, Gaussian elimination. | BIE-LIN |

10. | TO-BIE-SPOL-10 | Matrices: matrix-matrix multiplication, regular matrices, inverse matrices and its calculation, matrix eigenvalues and their calculation, matrix diagonalisation. | BIE-LIN |

11. | TO-BIE-SPOL-11 | Object-oriented programming in C ++, encapsulation, inheritance, attributes (data members) and methods, static attributes and methods, virtual methods, polymorphism, abstract classes, exceptions, templates, operator overloading, shallow and deep copy. | BIE-PA2 |

12. | TO-BIE-SPOL-12 | Abstract data types, specification and implementation. Stack, queue, array, list, table, and set. Implementation using linked structures, trees, and arrays. | BIE-PA2 |

13. | TO-BIE-SPOL-13 | Combinational and sequential logic circuits, their specification, representation and implementation. Logic expression minimisation (using map representation), gate-level implementation. | BIE-SAP |

14. | TO-BIE-SPOL-14 | Structure and architecture of a digital computer, functions of main units. Instruction cycle, instruction set architecture (ISA), structure of an instruction, machine code, assembler, addressing modes. Representation of signed numbers (sign-magnitude, 2’s complement and biased codes). Floating point number representations. | BIE-SAP |

15. | TO-BIE-SPOL-15 | Typical combinational and sequential circuits inside digital computers (adders, registers, shifters, controllers): design and implementation. | BIE-SAP |

16. | TO-BIE-SPOL-16 | Memory hierarchy system, types of memories used. Cache memory properties and implementation possibilities. | BIE-SAP |

17. | TO-BIE-SPOL-17 | Chomsky 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 |

18. | TO-BIE-SPOL-18 | Regular languages: Deterministic and nondeterministic finite automata. Determinization of a finite automaton. Minimization of a deterministic finite automaton. Operations on ﬁnite automata. Regular grammars, expressions, and equations. | BIE-AAG |

19. | TO-BIE-SPOL-19 | Context-free languages, context-free grammars, pushdown automata and its variants. Models of parsing of context-free languages. | BIE-AAG |

20. | TO-BIE-SPOL-20 | Relational database and relational algebra as a query language. The SQL language (SELECT, DDL, DML, DCL, TCL). Declaration of integrity constraints in DDL. | BIE-DBS |

21. | TO-BIE-SPOL-21 | Trasactions and their properties - ACID. | BIE-DBS |

22. | TO-BIE-SPOL-22 | 3 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 |

23. | TO-BIE-SPOL-23 | Methods for solution of recurrent equations, finding and solving recurrent equations for the time complexity analysis of algorithms. | BIE-ZDM |

24. | TO-BIE-SPOL-24 | Modular arithmetics, introduction to number theory, Fermat's Little Theorem, diophantine equations, linear congruences, the Chinese Remainder Theorem. | BIE-ZDM |

25. | TO-BIE-SPOL-25 | Asymmetric cryptosystems (the RSA cipher, the Diffie-Hellman protocol, the RSA digital signature), hash functions (SHA-2, HMAC). | BIE-BEZ |

26. | TO-BIE-SPOL-26 | Symmetric 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 |

27. | TO-BIE-SPOL-27 | Public key infrastructure, key distribution, digital signature. Certificates, certificate authorities. Cryptographically secure pseudorandom number generators. | BIE-BEZ |

28. | TO-BIE-SPOL-28 | Processes and threads, their implementation. Synchronization tools. Classical synchronization problems. Thread scheduling. Allocation of resources, Coffman's conditions, ways to resolve a deadlock. | BIE-OSY |

29. | TO-BIE-SPOL-29 | Principles of translation of logical-to-physical addresses for the virtual paged memory with/without segmentation. Page replacement algorithms in virtual paged memory. | BIE-OSY |

30. | TO-BIE-SPOL-30 | ISO/OSI and TCP/IP network models. Link layer protocols. Forms of acknowledgement. Switching and routing. Principles of internetworking devices. | BIE-PSI |

31. | TO-BIE-SPOL-31 | TCP/IP protocol family (IPv4, IPv6, TCP, UDP, application layer protocols). Data flow control. NAT - principle and usage. DNS system. | BIE-PSI |

32. | TO-BIE-SPOL-32 | Tools 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 |

33. | TO-BIE-SPOL-33 | Analytical domain class model, lifecycle of identified classes (goals, UML class diagram, UML state diagram). | BIE-SI1.2 |

34. | TO-BIE-SPOL-34 | Rules for calculating probabilities, the Bayes' formula. Random variables, common examples of distributons, cumulative distribution function, probability density function, moments. Independence of events and random variables. The central limit theorem, laws of large numbers. | BIE-PST |

35. | TO-BIE-SPOL-35 | Basics of statistical inference, random sampling, point estimates for the mean and variance, interval estimates for the mean, testing statistical hypotheses about the mean. | BIE-PST |