translated by Google

Machine-translated page for increased accessibility for English questioners.

IVV issues

Minor study plan

Theoretical foundations of computer science

  1. Propositional logic. Syntax, semantics, derivation system of propositional logic, proofs in propositional logic, truthfulness and provability of logical formulas. ( IB000 )
  2. Functions and recursion. Recursive function definitions, recursive data types (lists, trees), functions over recursive data types. ( IB114 )
  3. Data structures and their implementation. Abstract data types: list, array, stack, queue, binary tree, general tree, search tree. Implementation of binary and search trees and operations on them. ( IB113 , IB114 )
  4. Graphs. Graph types, trees, vertex levels, oriented graphs, graph representations. Graph and depth search algorithms and their use. Context components. ( IB114 )
  5. Sorting. Basic algorithms, heap sorting algorithms, merging, splitting. ( IB114 )
  6. Regular languages. Regular languages, regular grammars, regular expressions, finite automata. Properties of regular languages, relation between finite automata and regular grammars. ( IB110 )
  7. Finite vending machines. Definition, finite state machine construction, finite state machine minimization, conversion of nondeterministic finite state machine to deterministic state machine. ( IB110 )
  8. Computability. Turing machine as a universal computational model. Stop problem. Decidability and partial decidability, indecidability. Diagonalization. ( IB110 )
  9. Complexity. Algorithm complexity versus problem complexity. Complexity classes (P, NP, PSPACE) and relations between them, examples of problems from individual classes. Difficulty and completeness of the problem in a given class, polynomial reduction of problems, NP-complete problems. ( IB110 )
Program, computer and information systems

  1. Computational systems I. Number systems, relations between systems, computer display of integers, arithmetic. Codes, internal, external, detection and correction. Processors, their parameters and architectures. ( PB150 )
  2. Programming. Structured programming in imperative language, data and control structures of programming languages, data types, procedures and functions, block and modular program structure. ( IB113 ).
  3. Operating system. Operating system architectures, operating system interfaces. Processes, process synchronization, deadlocks and deadlock protection methods. Working with memory, logical and physical address space, memory management and methods of its implementation. Planning in operating systems. ( PB153 )
  4. Computer networks. Topology, access methods and architectures of computer networks (Ethernet, Fast Ethernet, Token-ring, ATM, etc.). Wireless communication technology. OSI model. TCP / IP protocol. Computer networking and information routing. ( PB156 )
  5. Database I. Relational model, relational schema, keys of relational schemas, integrity constraints, relational algebra, connection of relations. ( PB168 )
  6. Database II. SQL query language (select statement, relation joins, aggregation functions). Query processing. Basic principles, example. Indexing. Transaction. Transaction processing properties.
  7. Software engineering. Software development. Requirements specification, system analysis and design, testing, verification and validation, system operation. Use of UML in software development. ( PB007 )