Saint Petersburg, 199178, Russia, Line 14th (Vasilyevsky Island), 29

(812) 363-68-71, (812) 363-68-72

math-cs@spbu.ru

A prospective student of the Master’s program `Advanced Mathematics’ is expected to have a good knowledge of **at least four topics** from the following list.

Rings, subrings, ideals. Homomorphism theorem. Polynomial ring, Bezout theorem. Factoriality of the polynomial ring over the field. Vector spaces. Linear dependence. The existence of a basis in a vector space. Linear mapping. Rank of a linear map, Kronecker–Capelli theorem. Eigenvalues and the characteristic polynomial. Hamilton–Cayley Theorem. Nilpotent operators. Jordan normal form over complex numbers.

- A.L. Gorodentsev. Algebra I (Textbook for Students of Mathematics). Springer, 2016. [Chapters 2–3, 5–9, 14–15.]

Euclidean spaces, scalar product, distances, angles. Affine and orthogonal transformations, rigid displacements. Curves and surfaces of the second order. Curvature of the planar curve, curvature and torsion of a spatial curve, Frenet formula. Metric and topological spaces, continuous maps of topological spaces. Connectedness and path connectedness, compactness. Homotopy of maps. The fundamental group of a topological space. The fundamental group of a circle.

- M. Berger. Geometry 1. Springer, 1987. [Chapters 2, 8, 9.]
- M.P. do Carmo. Differential Geometry of Curves and Surfaces. Prentice-Hall, 1976. [Chapter 1.]
- C. Kosniowski. A First Course in Algebraic Topology. Cambridge University Press, 1980. [Chapters 1–16.]

Limits. Compactness. Continuity. Uniform convergence. Differential and derivative. Extrema of functions. Taylor series. Riemann Integral. Differentiable mappings. Conditional extrema. Lagrange multipliers method. The Lebesgue Integral. L^p classes. Tonelli’s theorem. Fubini’s Theorem. Convolution of functions. Holomorphic function. Cauchy’s Theorem. Liouville theorem. Residues. Rouché’s Theorem. Fourier series. The Dirichlet and Fejer kernels. Decay of Fourier coefficients. Plancherel’s Theorem.

- V.A. Zorich. Mathematical Analysis I. Springer-Verlag, 2015. [Chapters 6–8.]
- V.A. Zorich. Mathematical Analysis II. Springer-Verlag, 2015. [Chapters 9–13, 16–19.]
- W. Rudin. Real and Complex Analysis. McGraw-Hill, 1986. [Chapters 1–10.]

Existence and uniqueness of solutions. Linear systems of differential equations. Dependence of solutions on initial data and parameters. Lyapunov stability. Basic problems of mathematical physics. Distributional solution of differential equations. The fundamental solution and Cauchy problem.

- G. Teschl. Ordinary Differential Equations and Dynamical Systems. AMS, 2012. [Chapters 2, 3, 6.]
- G.B. Folland. Introduction to Partial Differential Equations. Princeton University Press, 1995. [Chapters 1–4.]

Graphs, directed graphs, trees, connected components in the directed and undirected graph. Matching, the Hall Lemma. Planar graphs, Euler formula. Eulerian paths and cycles. Permutations, cyclic type. Combinations with and without repetitions. Partial permutations.

- J.H. van Lint and R.M. Wilson. A Course in Combinatorics. Cambridge University Press, 1992 (reprinted in 1994 and 1996). [Chapters 1, 2, 10, 13, 14, 15.]
- F. Harary. Graph theory. Addison-Wesley, 1969. [Chapters 1, 2, 4, 5, 11.]

Probability spaces. Distributions of random variables. Criteria for independence of random variables. Numerical characteristics of random variables. Bernoulli tests. Law of Large Numbers. Local and integral limit theorems of de Moivre–Laplace. Central limit theorem for sums of independent random variables. Characteristic functions. Markov chains with finite or countable set of states. Discrete-time martingales.

- A.N. Shiryaev. Probability. 2nd ed. Springer, 1996. [Chapters 1–2.]

The language of propositional classical logic and its two-valued semantics. Disjunctive normal forms (DNF’s) and conjunctive normal forms (CNF’s). The DNF and CNF theorems (on reduction of propositional formulas to DNF’s and CNF’s respectively). A Hilbert-style calculus for propositional classical logic and derivability in it. The deduction theorem for this calculus. Consistent and maximal consistent sets. The strong completeness theorem (including soundness) for the Hilbert-style calculus for propositional classical logic and its most important consequences.

Paradoxes of naive set theory. Zermelo–Fraenkel axioms and the Axiom of Choice. Basic operations on sets and their basic properties. Ordered pairs, triples, etc. Cartesian products. Relations and functions. Equivalence relations and partial orders. Transfinite induction. Well ordered sets and transfinite recursion. Isomorphism of well ordered sets. Comparability of well ordered sets. Equinumerosity and its elementary properties. Cantor–Schröder–Bernstein theorem. The theorem on the comparability of cardinalities. Cantor theorem (on the cardinality of the set of all subsets of a given set). Countable sets and their basic properties. Cardinalities of unions and products of sets.

- J.D. Monk. Mathematical Logic. Springer-Verlag, 1976. [Chapter 8.]
- K. Kuratowski and A. Mostowski. Set Theory. North-Holland Publishing Company, 1968. [Sections I.1–I.6, II.1–II.3.]
- N.K. Vereshchagin and A. Shen. Basic Set Theory. AMS, 2002. [Sections 1.1, 1.2, 2.1, 2.2.]

Time complexity of algorithms and estimation methods. Master theorem. Algorithms for searching in graphs (depth-first search, breadth-first search, Dijkstra’s algorithm). Sorting algorithms (insertion sort, merge sort, quicksort, heapsort). Data structures for sets (linked list, AVL tree or red-black tree, hash table), and operations with them. Finite automata (deterministic and non-deterministic), their equivalence. Computational complexity: complexity class NP, examples of NP-complete problems. Algorithmically intractable problems.

- R. Cormen, C. Leiserson, R. Rivest, C. Stein “Intoduction to Algorithms, 3rd Edition” (The MIT Press) 2009.
- J. Hopcroft, R. Motwani, J. Ullman “Introduction to Automata Theory, Languages, and Computation, 3rd Edition” (Pearson) 2013.

11.12.2019

22.10.2019

22.10.2019

21.12.2018