LFU:online

Absolvents should acquire the abilities to understand and express the contents of the course.

1) Elements of asymptotic analysis: Landau's symbols; Hardy’s theorem on exponential-logarithmic class; iterated functions; basic asymptotic expansions.

2) Asymptotic analysis of deterministic recurrences: singular analysis of generating functions, the method of iterative functions.

3) Randomized algorithms: deterministic algorithms with random input; performance functionals; average-, best- and worst-case analaysis).

4) Linear random recurrences, allowing branching: divide-and-conquer principle; general form of linear random recurrences; examples: Quicksort and Quickselect algorithms.

5) Probabilistic metrics: spaces of probability measures; simple and compound probabilistic metrics; minimal and ideal metrics; Zolotarev’s metric and minimal L_p-metric; central limit theorem and its counterparts under various metrics.

6) Fixed points of smoothing transforms: smoothing transforms; theorem on existence of fixed points of smoothing transforms.

7) Contraction principle: Banach's theorem; contractions in spaces of probability measures; contraction method in the case of nondegenerate limit relation; contraction method in the case of degenerate limit relation: Neininger-Rueschendorf theorem)