This repository contains the flashcards and other material used to prepare for the BSc. Computer Science final exam.
- Sequences, series, funcions, limits and continuity
- Convergence of sequences of real and complex numbers and vectors
- Monotonic sequences
- Notion and convergence of infinite numerical series
- Positive series
- The root and the ratio test
- Alternating (Leibniz type) series
- Power series
- The Cauchy–Hadamard theorem
- Limits and continuity of vector–vector functions
- Properties of functions on a compact set: Theorems of Heine
- Properties of functions on a compact set: Weierstrass
- Continuity of the inverse function
- The Bolzano theorem
- Differential and integral calculus and applications
- Differentiation and integration of functions of one real variable
- Rules of differentiation
- Theorems of Rolle, Cauchyand Lagrange
- Extrema, concavity, discussion of functions
- The Riemannian integral
- Integration by parts, integration with substitution
- The fundamental theorem of calculus (The Newton–Leibniz formula)
- Area, arc length, volume, surface
- Differentiation of vector–vector functions
- Jacobi matrix, gradient, partial derivative
- Systems of differential equations
- The initial value problem
- Linear systems of differential equations
- Linear equations of higher-order
- Methods of interpolation
- Lagrange interpolation
- Hermite interpolation
- Spline in-terpolation Extra: [ ] 3rd degree spline interpolation (cubic)
- Numerical solution of linear systems of equations
- Gaussian elimination
- Methods based on product decomposition
- Iterative methods
- Least-squares methods
- Sets, relations and enumeration problems
- Basic operations on sets and their properties
- Binary relations and their properties (transitivity, etc.)
- Partial orderings and equivalence relations
- Permutations, variations, combinations
- Inclusion-exclusion principle
- Pigeonhole principle
- Binomial theorem
- Undirected and directed graphs
- Basic concepts in graph theory: vertex, edge, degree, walk, trail, path, cycle, connectivity, component
- Trees and their characterizations
- Eulerian and Hamiltonian graphs
- Labeling and coloring, Kruskal’s algorithms on minimal spanning trees
- Basics of linear algebra
- Matrices
- Determinants
- Basis and dimension in vector spaces
- Eigenvalues and eigenvectors of matrices, diagonalization
- Orthogonal and orthonormal systems in Euclidean spaces
- Basics of probability and statistics
- Discrete and continuous random variables
- Law of large numbers
- Central limit theorem
- Statistical estimates
- Classical statistical tests
- Artificial intelligence
- Path-finding problems and their modelling with directed graph(state-space model, problem decomposition model)
- Heuristic path-finding algorithms (their outcomes and computational cost): local searches, backtracking algorithms, graph searches (A, A∗, AC, Balgorithm)
- Two-player games (game tree, existence of winning strategy, minimax algorithm, alpha-beta pruning)
- Programming theorems
- Usage of programming theorems in programming
- Summation, counting, maximum search, conditional maximum search (conditional maximum search is missing)
- Sequential search
- Binary search
- Software development models
- Development stages of large scale systems (ambiguous)
- The concept of object-oriented programming, type inheritance
- Views of object-oriented modeling, UML tools (wtf is views?)
- The notion of software design patterns
- Static and dynamic models
- Static model (class diagram, object diagram)
- Usecase diagrams
- Compilation and execution of programs
- Compilers and interpreters, bytecode
- Pre-processor, compiler, linker
- Make
- Compilation units, libraries
- Syntactic and semantic rules
- Static and dynamic type checking
- Parallel programming
- Data, operators and control structures
- Representation of numbers, basic data types
- User defined types
- Operators, expression evaluation
- Statements, control structures,recursion, exception handling
- Data abstraction
- Class, inheritance, static and dy-namic binding, subtype polymorphism
- Generics
- Program structure
- Block, visibility, scope
- Automatic, static and dynamic variables,garbage collection
- Constructor, destructor
- Cloning and comparing objects
- Programmodules, namespaces
- Subroutines, parameter passing
- Overloading
- Compilers
- Structure of compilers, the tasks of the components
- Lexical analyzer and its functions, implementation
- Classification and comparison of syntactic analyzers, overview of their creation and functioning
- The notion and use of ATGs
- Code generation in assembly for basic imperative constructs
- Logic
- The syntax and semantics of propositional and predicate calculus
- The notion of logical consequence
- Basic methods for proving logical consequences in propositional calculus: truth tables, the method of semantic tableaux, and the resolution
- Theory of computation
- The Church–Turing thesis
- Variants of Turing machines (one tape – multi tape, deterministic – non-deterministic)
- Recursive and recursively enumerable languages
- Undecidable problems
- Reducibility
- The time complexity classes P and NP
- Polinomial time reducibility
- NP-complete problems
- The space complexityclasses PSPACE and NPSPACE
- Savitch’s theorem
- PSPACE-complete problems
- Data structures
- Representations and operations of basic data structures—array, stack, queue, priority queue, list, binary tree, graph
- Basic algorithms
- Representations of search data structures (binary search tree, AVLtree, 2-3 tree, B tree, hashing with chaining and open addressing)
- Sorting algorithms and their efficiency (bubble, insert, maximum selection, tournament, heap, quick and merge sort algorithms)
- Sorting in linear time: bucket sorts, radix sorts
- Formal languages
- Generative grammars, the Chomsky hierarchy
- Basic properties and application of regular and context-free grammars and languages
- Finite automata and pushdown automata
- Operating systems—parallel processes
- The notion and implementation of process and thread
- Interactive, batch and real-time processes, scheduling algorithms
- Types of parallelism, race conditions, critical sections
- Shared memory and messaging
- Semafors and monitors
- Deadlocks: description, avoidance, prevention, recognition
- Operating systems—storage handling
- Hierarchy of storages
- Memory handling: fixed and dynamic partitions, virtual memory
- Paging and segmentation
- Page re-placement algorithms, working set
- Scheduling input and output, reducing serving time
- Organizing disk storage, physical and logical formatting, partitions
- Redundant arrays, array handling systems
- File systems and their implementation
- Block reservation strategies, registering free storage space, journaled file systems
- Computer networks
- Physical layer, data link layer, MAC, network layer, transport layer—services, methods, protocols
- Distributed systems
- Definition
- Design goals
- Distribution transparency
- Typesof distributed systems
- Architectures
- Middleware
- Processes
- Threads
- Virtualization
- Clients-servers
- Code migration
- Types of communication (transient, persistent,message-oriented, RPC, multicasting, data dissemination)
- Naming (flat, structured,attributed)
- Coordination
- Clock synchronization
- Logical clocks
- Vector clocks
- Mutual exclusion
- Election algorithms
- Location systems
- Consistency and replication
- Databases—query languages
- Relational model, entity–relationship model, transformation from ER to relational model
- Relational algebra, SQL, Datalog
- Recursion inquery languages
- Procedural elements in query langauges (variables, control structures, subprograms, cursors, exceptions)
- Databases—query execution
- Index structures, sparse and dense index, B+ tree, bitmap index, dynamic hashing
- One-pass and two-pass algorithms, sort based and hash-based algorithms
- Join methods
- Cost of operations
- Query execution plans