Machine learning — entry exam scope

Distribution of exam questions will be close to the following one (though discrepancies may happen):

• Probability theory and statistics:17%
• Linear algebra: 13%
• Discrete mathematics: 13%
• Python: 10%
• Mathematical analysis: 7%
• Foundations of mathematics: 7%
• Numerical methods: 7%
• Algorithms and data structures: 7%
• Databases: 7%
• Concurrent programming: 7%
• Computer Networks: 3%
• Operating systems: 3%

Mathematical analysis

• Sketch of the axiomatic theory of real numbers: suprema and infima, mathematical induction, decimal system, rational numbers, powers with real exponents.
• Sequences: limits (finite and infinite) and convergence, elementary properties of limits, monotone sequences, subsequences and the Bolzano-Weierstrass Theorem, Cauchy’s condition and completeness, information on some further results on limits (e.g., Cesaro-Stolz theorem).
• Series: the concept of a series and its sum, convergence and absolute convergence, tests of convergence: comparison test, asymptotic test, Cauchy’s condensation test, tests of d’Alembert, Cauchy and Dirichlet. Changing the order of summation, Cauchy’s product of series.
• Limits of functions and continuity: condensation points, limits of functions (Heine and Cauchy definitions), properties of limits, continuity, Darboux intermediate value property, Weierstrass extreme value theorem, uniform continuity, power series - the set of convergence and continuity of the sum; examples and properties of elementary functions (power and exponential, logarithmic, trigonometric).
• Differential calculus of one variable: the derivative and its geometric interpretation, algebraic properties of the derivative, differentiation of elementary functions, local extrema, Mean Value Theorems of Rolle, Lagrange and Cauchy, monotonicity of a function vs its derivative,  Rachunek różniczkowy funkcji jednej zmiennej: pochodna i jej sens geometryczny, de l’Hospital’s Rule, higher derivatives, convexity, Taylor series.
• Sequences and series of functions: pointwise, uniform and almost uniform convergence, supremum norm of functions, necessary and sufficient conditions for uniform convergence of series of functions (Cauchy’s condition, Weierstrass’ test), continuity and differentiability of limits, information on uniform approximation with polynomials.
• Integral calculus of one variable: Indefinite and definite integral, integration by parts and by substitution, integration of rational functions, knowledge of standard substitutions. Riemann integral, integrability and convergence of Riemann sums for continuous functions. Elementary properties of Riemann functions, Fundamental Theorem of Calculus and First mean value theorem for definite integrals. Improper integrals.
• Metric spaces and continuity of functions of multiple variables: examples of metrics, norms, open and closed sets, convergence of sequences in metric spaces, compactness in Rn and Bolzano-Weierstrass’ Theorem, limits and continuity of functions of multiple variables, continuity of a function in terms of openness/closedness of sets, Weierstrass’ extreme value theorem for functions of multiple variables.
• Differential calculus in multiple variables: derivative of a vector-valued function of one variable, partial derivatives, C1 functions, local extrema of real-valued functions, directional derivatives. Derivative and the Jacobi matrix,  continuity of differentiable functions and differentiability of C1 functions, chain rule in multiple variables, conditional extrema and Lagrange multipliers, second order partial derivatives and sufficient conditions for local extrema.

Linear algebra

• Groups and fields. Complex numbers and their trigonometric form, de Moivre’s formula, roots of unity, roots of a complex number.
• Polynomials, information on the fundamental theorem of algebra.
• Matrices with entries in a field. Algebraic operations on matrices.
• Linear spaces over a field, linear subspace, linear independence, basis, dimension. Examples of bases. Intersection, sum and direct sum of linear subspaces.
• Image, kernel and rank of a matrix. Invertible matrices.
• Systems of linear equations. Kronecker-Capelli Theorem. The set of solutions of a system. Gauss’ elimination.
• Determinants and their properties. Cramer’s rule.
• Linear maps and functionals. The matrix of a linear map. Rank, image and kernel of a linear map. Isomorphisms of linear spaces.
• Dual spaces and dual bases. Matrix of base change, relations to linear maps.  
• Matrix similarity. Eigenvalues and eigenvectors, spectrum of a matrix and of a linear map. The characteristic polynomial. Diagonalization of a matrix / linear map. Information on Jordan’s theorem.
• Euclidean and unitary spaces. Scalar product, euclidean norm, the concept of an angle. Orthogonal and orthonormal bases, Parseval’s rule. Gram-Schmidt orthogonalization. Orthogonal complement and orthogonal decomposition of a space; orthogonal projections. Isometries, orthogonal / unitary matrices. Hermitian and symmetric forms. Conjugate matrices. Diagonalization of symmetric / hermitian matrices. Sylvester’s test.

Foundations of mathematics

• Propositional calculus and its properties. Introduction to predicate logic.
Finite and infinite set-theoretic operations.
• Relations, functions, and their basic properties.
• Equivalence relations, the principle of abstraction.
• Natural numbers, the principle of induction.
• Equipotent sets. Finite and infinite, enumerable and non-enumerable sets.
• Cantor Theorem and Cantor-Bernstein Theorem.
• Partial and total ordering relations. Suprema and infima. Applications of Kuratowski-Zorn Lemma.
• Well-ordered and well-founded sets. Structural induction.
• The notion of a formal proof. Proof systems for propositional logic, the completeness theorem.
• Relational structures and first order logic: semantics, Gödel's completeness theorem.

Discrete mathematics

• Mathematical induction and recursion.
• Finite sums
• Binomial coefficients
• Permutations and partitions.
• Generating functions and their applications
• Counting methods: enumerators, inclusion-exclusion principle
• Asymptotics: notation (O,Omega, Theta, o, omega), master theorem for recurrences
• Elementary number theory: divisibility, prime numbers, prime number factorization, greatest common divisor and Euclid’s algorithm.
• Modular arithmetics: Fermat’s little theorem, Euler’s theorem, Chinese remainder theorem, solving modular equations
• Elements of cryptography: Miller-Rabin primality and RSA system
• Graphs: paths, trees, cycles, Euler and Hamilton cycles, bipartite graphs, transversals and Hall’s marriage theorem, planarity, graph coloring

Probability theory and statistics

• Probability space: axioms of probability; properties of probability spaces; classical definition of probability; geometric probability; probability measures.
• Conditional probability and independence: definition of conditional probability, Law of Total Probability, Bayes' Theorem, independence of events.
• Discrete random variables: definition, properties, basic probability distributions - two-point, binomial, Poisson, geometric.
• Parameters of probability distributions: expected value, variance, higher moments; probability generating functions, their properties and applications to probability distributions.
• Tail estimates: Markov inequality, Chebyshev inequality, Chernoff bounds, Law of Large Numbers.
• Continuous random variables: definition, properties, exponential and normal distributions, Central Limit Theorem.
• Markov chains: definition and basic properties, hitting probabilities and expected hitting times, periodicity, ergodicity, applications.
• Descriptive statistics: features and their scales, raw and cumulative data, graphical presentation, measures of central tendency and dispersion
• Statistical reasoning: samples, statistics and estimators, parametric vs nonparametric estimation, maximum likelihood method.
• Hypothesis testing and confidence intervals: confidence intervals for the mean, confidence levels and p-values, methodology of a statistical test.

Numerical methods

• Nonlinear equations: basic notions (radius of convergence, order of convergence), Newton’s method for systems of equations and its variants, stopping criteria.
• Floating point arithmetics: number representation, computer arithmetics and rounding error.
• Errors in computations: conditioning of a computational problem, backward and forward stability of an algorithm.
• Linear systems of equations: condition number, direct methods (Gaussian elimination, Householder reflections, Cholesky factorization, block methods), iterative refinement, iterative methods (based on matrix splitting, conjugate gradients), preconditioning.
• Linear least squares: full rank and rank deficient.
• Eigenvalue problem: power and inverse power methods, orthogonal tridiagonalization of a symmetric matrix, QR method.
• Polynomial interpolation: Lagrange and Hermite interpolation, Newton’s basis, divided differences, interpolation error formula.
• Spline interpolation: Hermite representation of cubic splines, Holladay’s theorem, B-splines, B-spline representation of an interpolating cubic spline, Schoenberg-Whitney theorem.
• Trigonometric interpolation: discrete Fourier transform, FFT algorithm.
• Best approximation: uniform: Chebyshev polynomials and nodes, alternant, uniform spline approximation, least squares approximation: orthogonal polynomials.
• Quadratures: interpolatory rules, Gaussian quadratures, composite rules, Richardson’s extrapolation, Romberg method.
• Selected environments and software libraries for numerical computation.

Algorithms and data structures

• Basic principles of analysis of algorithms.
• Methods for designing efficient algorithms.
• Sorting.
• Selection.
• Priority queues.
• Searching and dictionaries.
• Find-Union problem and its applications.
• Graph algorithms.
• Text pattern matching.
• Data structures for text processing.

Databases

• Relational data model.
• Basic programming constructs of SQL and their implementation.
• Kinds of metadata and their roles.
• Redundancy and database normal forms.
• Transition from conceptual to logical model.
• Physical data representation.

Languages, automata and computations

• Elements of formal languages: words, languages, regular expressions.
• Finite automata and the Kleene theorem on effective equivalence of finite automata and regular expressions.
• Automata optimisation constructions - determinisation, minimisation.
• Context-free languages: grammars and their normal forms.
• Equivalence of context-free grammars and nondeterministic pushdown automata.
• Necessary conditions for regular and context-free languages: pumping lemmas.
• Algorithmic questions: emptiness and membership for automata and grammars.
• Example applications of automata and grammars.
• Universal computation models: Turing machines and variants.
• Limits of computability: undecidability of the halting problem, examples of practical undecidable problems.
• Conclusion: classification of grammars and computation models in the Chomsky hierarchy.
Introduction to complexity theory: P and NP.
• The Cook-Levin theorem on NP-completeness of SAT.
• The P=/=NP conjecture and its practical implications, information on positive applications of hard computational problems, e.g. in cryptography.

Concurrent programming

• Methods of synchronisation in concurrent computations model: shared variables (co-algorithms of mutual exclusion), semaphores, monitors.
• Correctness analysis of concurrent algorithms (without LTL).
• Methods of synchronisation in distributed computations model: synchronous communication, asynchronous communication (tuplespace).
• Consistency and models of consistency: linearizability (or atomicity), sequential consistency, causal consistency, eventual consistency.
• Efficiency in concurrent model: work, span, speed-up, parallelization - illustrated and estimated with help of programs in CILK.
• Methods of concurrent programming: POSIX threads, concurrency in Java (classical, java.util.concurrency), concurrency in C++.

Computer networks

• Network layers.
• Protocols TCP, UDP, IP, ICMP, Ethernet.
• Internet addresses, routing tables, routing algorithms, NAT.
• Domain name system.
• Sockets API.

Python

• Control flow
• Containers (arrays, lists, dictionaries etc.)
• Classes, objects and inheritance
• Modules
• Reflection mechanisms
• Metaprogramming

Operating systems

• Hardware support required for implementation of multi-user, multitasking operating systems.
• Basics of low-level programming, assembler.
• Process scheduling algorithms.
• Virtual memory. Characteristics of its different implementation methods.
• User-space system calls for handling of files (operating system actions, data structures).