Master Program "Applied Mathematics and Stochastics"
Numerical Statistical Modelling
This is a 2-year English-taught programme at the Master level. It is aimed at training and developing research skills in Numerical Modelling, Monte Carlo Methods and in their applications.
The Programme is research-oriented. Each semester a student is supposed to devote a half of time to a research project, to be done at Institute of Computational Mathematics and Mathematical Geophysics. Results of this research project must be presented in a form of a Master Dissertation at the end of 2nd year of studies.
Topics of lectures and research includes, but are not limited to
– numerical modelling of random values and processes,
– solution of ordinary and stochastic differential equations,
– theory of radiation transfer,
– stochastic simulation methods in applied mathematics, physics, meteorology, economics (including financial mathematics),
– discrete-stochastic numerical methods,
– modern computer technologies in stochastic simulation, etc.
Lecture courses and research supervision are provided by professors of the Novosibirsk State University and leading researchers from institutes of the Russian Academy of Sciences. They all are members of the worldwide known scientific school on numerical stochastic simulation headed by Professor G.A.Mikhailov.
Advanced Stochastic Simulation Methods in Applied Mathematics and Physics — Karl Sabelfeld, Professor
Course Title: Advanced Stochastic Simulation Methods in Applied Mathematics and Physics
Aims of the Course:
The aim of the course is to present modern stochastic models and numerical methods for solution of various actual applied stochastic problems.
Recommended prerequisites for attendance:
Basic knowledge of probability theory, mathematical physics and the theory of Monte Carlo methods.
Contents:
The course presents the modern stochastic models and randomization based numerical methods and algorithms for solving large scale problems of computational mathematics with applications in physics, chemistry, biology and different fields of scientific computing. Mainly two basic approaches are given: (1) direct stochastic simulation of the processes in question which approximately mimics the physics and reflects properly the main features, e.g., diffusional and ballistic transport of particles in random porous media, annihilation of electrons and holes in semiconductors, growth of nanowires, coalescence of growing islands of adatoms, simulation of random turbulent velocity fields, x-ray diffraction analysis of dislocations in crystals, luminescence in nanowires, and many others, and (2) development of stochastic models and simulation methods for solving boundary value problems, both in deterministic and probabilistic formulation, e.g., random walk based methods for solving the diffusion and electrostatic problems, the elastostatics problems with random boundary conditions, Darcy equation with random hydraulic conductivity, nonlinear Smoluchowski equation governing the coagulation, diffusion, trapping and annihilation, and many others, as well as solution of direct and inverse problems based on randomization of large matrices and a randomized SVD (singular value decomposition) and stochastic projection methods.
Discrete-Stochastic Numerical Methods — Anton Voytishek, Professor
Course Title: Discrete-Stochastic Numerical Methods
Aims of the Course:
The aim of the course is to acquaint students with effective combined numerical techniques which include advantages of “deterministic” (difference) schemes and Monte Carlo methods.
Recommended prerequisites for attendance:
Basics knowledge of probability theory, numerical mathematics and the theory of Monte Carlo methods.
Contents:
1. Discrete-stochastic numerical methods for modelling of random variables.
2. Discrete-stochastic methods of numerical integration.
3. Functional estimators of the Monte Carlo method.
4. Randomization of difference numerical schemes.
5. Stochastic numerical algorithms for self-organizing procedures.
6. Usage of applied terminated Markov chains.
Investigation and Error Reduction of the Weighted Monte Carlo Methods — Ilya Medvedev, Doctor
Course Title: Investigation and Error Reduction of the Weighted Monte Carlo Methods
Aims of the Course:
The aim of the course is to present the advanced mathematical technique for error reduction of the weighted estimators of Monte Carlo methods.
Recommended prerequisites for attendance:
Basics knowledge of probability theory, statistics, mathematical analysis and numerical mathematics.
Contents:
The main object of study in this course is the development and justification of the efficient weight Monte Carlo method for estimating the linear functionals of the solution of integral equation of the second kind. This course presents the main methods of research and decrease probability error. Among these are partial importance-based algorithms, non-linear optimization of the probability density of certain transition elements, minimax global estimators of histogram type. In addition, some problems of the construction weight estimators for non-linear kinetic equation and additive functionals of the diffusion process trajectories are considered.
Methods of Statistical Modelling for Solution of Nonlinear Kinetic Equations — Sergey Rogazinsky, Professor
Course Title: Methods of Statistical Modelling for Solution of Nonlinear Kinetic Equations
Aims of the Course:
The aims of the course are:
to give to students basic knowledge in the modern theory of methods of statistical modelling for solution of nonlinear kinetic equations;
to teach students to analyze the modern numerical schemes of statistical modelling for solution of nonlinear kinetic equations.
Recommended prerequisites for attendance:
Basic knowledge of probability theory, mathematical physics and the theory of Monte Carlo methods.
Contents:
1. The Bird method for statistical simulation of rarefied gas dynamics
2. Direct statistical simulation of kinetic processes based on using the Kolmogorov equations
3. Method of local weights for statistical modelling of homogeneous gas relaxation
4. Weighted Monte Carlo methods for solution of nonlinear kinetic Boltzmann equation
5. Solution of nonlinear kinetic Smoluchovsky equation by Monte Carlo simulation
6. Solution of nonlinear kinetic Boltzmann equation in spatially inhomogeneous case by statistical simulation.
Monte Carlo Methods (Basic Course) — Anton Voytishek, Professor
Course Title: Monte Carlo Methods (Basic Course)
Aims of the Course:
The aims of the course are:
to acquaint students with theory and applications of methods for numerical statistical modelling and simulation;
to teach students to analyze the algorithms of the Monte Carlo method in terms of their efficiency and possibility of their use in numerical solution of actual applied problems;
to teach students to construct economical numerical algorithms for modelling of random variables (one-dimensional or multi-dimensional) and to use technologies of optimization for Monte Carlo numerical schemes.
Recommended prerequisites for attendance:
Basics knowledge of probability theory and statistics, mathematical analysis, numerical mathematics.
Contents:
The course presents detailed descriptions for approaches to computer simulation of standard random numbers, for algorithms of numerical modelling of random variables and vectors, for methods of construction of Monte Carlo estimates (estimators) for numerical integration (including the approximation of special indefinite sums of integrals). The introduction and final lectures of the course include presentations of modern applied problems which imply the using of corresponding effective methods of numerical statistical modelling and simulation. The extensive seminar and individual student’s work, together with the fulfillment of substantial semester task, are also planned within the course.
Monte Carlo Methods for Solving Boundary Value Problems of Mathematical Physics — Irina Shalimova, Doctor
Course Title: Monte Carlo Methods for Solving Boundary Value Problems of Mathematical Physics
Aims of the Course:
The aims of the course are to expand basic educational knowledge of the undergraduate students, namely, to study the non-deterministic approaches for solving the boundary value problems.
Recommended prerequisites for attendance:
Basic knowledge of probability theory, mathematical physics and the theory of Monte Carlo methods.
Contents:
This course is devoted to algorithms of statistical modelling for solving the boundary value problems of mathematical physics in classic and stochastic forms. Such problems arise in different branches of science, for example, in crystallography (modelling of dislocations), bioinformatics, financial mathematics, elasticity theory. The statistical approach is the essence of the studied methods, in general. This means that a solution of a boundary value problem is constructed as the expectation of random estimator defined in a functional space of trajectories. In this approach either the probabilistic representations for original boundary problem or the equivalent integral representations are used.
Numerical Modelling of Discrete Random Processes and Fields — Vasiliy Ogorodnikov, Professor
Course Title: Numerical Modelling of Discrete Random Processes and Fields
Aims of the Course:
The aim of the course is to give students basic knowledge in the theory and applications of methods for numerical simulation of discrete random processes and fields.
Recommended prerequisites for attendance:
Basic knowledge of probability theory, statistics and numerical mathematics.
Contents:
Some questions connected with the construction and study of algorithms for simulation of Gaussian processes and fields of discrete argument based on the method of conditional distributions are considered in the given course. For the given Toeplitz and block-Toeplitz covariance matrices some special recursive algorithms for simulation of scalar and vector stationary processes and homogeneous fields on uniform grids are considered. Some questions of regularization and estimation the accuracy of the simulation are explored. The application of these algorithms for scalar and vector autoregression process with a given correlation structure is considered, the conditions of their stationarity are studied. Special attention is paid to the modelling of non-Gaussian random processes and fields of discrete argument and also to the problems of numerical simulation of periodically correlated processes and conditional random fields.
Numerical Modelling of Random Variables — Natalia Tracheva, Doctor
Course Title: Numerical Modelling of Random Variables
Aims of the Course:
To give students the detailed view on standard and special techniques of numerical modelling of random variables and vectors.
Recommended prerequisites for attendance:
Basic knowledge of probability theory and numerical mathematics.
Contents:
Simulation of pseudorandom numbers. Numerical modelling of discrete and continuous random variables (standard and special methods). Numerical modelling of random vectors. Superposition method and its applications. Majorant rejection method and its modifications. Approximate discrete-stochastic methods for numerical modelling of random elements. Modelling of gamma- and beta-distributions. Modelling of Gaussian and multi-dimensional isotropic random vectors.
Random Process Simulation and Continuous Stochastic Models — Sergey Prigarin, Professor
Course Title: Random Process Simulation and Continuous Stochastic Models
Aims of the Course:
The aim of the course is to present the basic concepts and methods of the random process simulation and their modern applications.
Recommended prerequisites for attendance:
Basic knowledge of probability theory, statistics and numerical mathematics.
Contents:
The course deals with the development and investigation of numerical methods for simulation of random processes and fields. Basic concepts and methods are considered concerning construction of numerical algorithms for various types of stochastic objects. A significant part of the course is concentrated on the so-called “spectral” models. The spectral models belong to a class of continuous stochastic models. They were developed in the 70-s years of the 20th century, and have appeared to be considerably promising for various applications. In Russia, the papers by Prof. G.A. Mikhailov have given impetus to a large number of investigations on spectral models of random fields. Nowadays the spectral models are extensively used for stochastic simulation in the atmosphere and ocean optics, turbulence theory, analysis of pollution transport for porous media, astrophysics, and other fields of science. Moreover, great attention in the course is given to general and some specific aspects of numerical simulation of non-Gaussian models, including the problem of compatibility of marginal distributions and covariances and the method of nonlinear transformation of Gaussian functions. Up-to-date application areas of the random process modelling such as simulation of the sea surface undulation and stochastic structure of clouds are presented in the course briefly.
Seminar on History and Advanced Problems of Numerical Statistical Modelling — Anton Voytishek, Professor; Nina Kargapolova, Doctor
Course Title: Seminar on History and Advanced Problems of Numerical Statistical Modelling
Seminar on Modern Problems of Numerical Statistical Modelling — Anton Voytishek, Professor; Nina Kargapolova, Doctor
Course Title: Seminar on Modern Problems of Numerical Statistical Modelling
Stochastic Models of Meteorological Processes — Nina Kargapolova, Doctor
Course Title: Stochastic Models of Meteorological Processes
Vector Algorithms of the Monte Carlo Methods — Sergey Ukhinov, Professor
Course Title: Vector Algorithms of the Monte Carlo Methods
Aims of the Course:
To present fundamental concepts, theoretical principles of vector algorithms of the Monte-Carlo method, their practical importance and applications.
Recommended prerequisites for attendance:
Basic knowledge of probability theory, mathematical physics and the theory of Monte Carlo methods.
Contents:
The course provides detailed exposition of the theory, concepts and algorithms for solving the vector integral equations by the method of numerical statistical modelling (Monte Carlo method). The course includes the latest research results on the use of statistical modelling to solve applied problems, described by systems of multidimensional integral equations of the second kind and by the system of integro-differential equations in the theory of polarized radiation. The course presents up-to-date methods and algorithms for solving direct and inverse problems of atmospheric optics on the basis of simulation of physical experiments, including the use of technology of high-performance distributed computing.
Inverse and Ill-Posed Problems: Theory, Numerics and Applications
The main purpose and characteristic feature of this program is the accessibility of presentation and an attempt to cover the rapidly developing areas of the theory, numerical methods and applications of inverse and ill-posed problems as completely as possible.
In direct problems of mathematical physics, researchers try to find exact or approximate functions that describe various physical phenomena such as the propagation of sound, heat, seismic waves, electromagnetic waves, etc. In these problems, the media properties (expressed by the equation coefficients) and the initial state of the process under study (in the nonstationary case) or its properties on the boundary (in the case of a bounded domain and/or in the stationary case) are assumed to be known. However, it is precisely the media properties that are often unknown. This leads to inverse problems, in which it is required to determine the equation coefficients from the information about the solution of the direct problem. Most of these problems are ill-posed (unstable with respect to measurement errors). At the same time, the unknown equation coefficients usually represent important media properties such as density, electrical conductivity, heat conductivity, etc. Solving inverse problems can also help to determine the location, shape, and structure of intrusions, defects, sources (of heat, waves, potential difference, pollution), and so on. Given such a wide variety of applications, it is no surprise that the theory and numerical methods of inverse and ill-posed problems has become one of the most rapidly developing areas of modern science. Today it is almost impossible to estimate the total number of scientific publications that directly or indirectly deal with inverse and ill-posed problems. However, since the theory, numerical methods are relatively young, there are many terms are still not well-established, many important results are still being discussed and attempts are being made to improve them. New approaches, concepts, theorems, methods, algorithms and practical problems are constantly emerging.
Main topics:
- Ill-Posed problem concept
- Inverse problems classification
- Regularization methods
- Applications: Geophysics, Medicine, Biology, Finance, Social sciences, Big Data, Data Mining, Machine Learning, Image Processing.
Basic Concepts and Examples of Inverse and Ill-Posed Problems — Sergey Kabanikhin, Professor, Russian Academy of Sciences (Corresponding Member); Nikita Novikov, Doctor
Course Title: Basic Concepts and Examples of Inverse and Ill-Posed Problems
Aims of the Course:
The aims of the course are:
to give students basic knowledge in the modern theory of inverse problems and its applications;
to teach students to analyze the modern difference numerical schemes for solution of inverse problem in terms of their well-posedness, convergence degree and conditional stability.
Recommended prerequisites for attendance:
Basics knowledge of mathematical analysis and mathematical physics.
Contents:
Well-posed, ill-posed, and conditionally well-posed problems. Regularization methods. Direct and inverse problem for the string fluctuation equation. Inverse acoustic problem and methods of its solution. Cauchy problem for the thermal conductivity equation with inverse time. Strong convergence for the gradient descent method. Linearization method. Newton — Kantorovich method. Gelfand — Levitan — Krein method.
Continuation Problems of the Physical Fields — Maxim Shishlenin, Doctor
Course Title: Continuation Problems of the Physical Fields
Data Assimilation Algorithms and Inverse Problems for Convection-Diffusion-Reaction Models — Alexey Penenko, Doctor
Course Title: Data Assimilation Algorithms and Inverse Problems for Convection-Diffusion-Reaction Models
Aims of the Course: Data assimilation algorithms are developed to forecast behavior of dynamic systems that are subject to rapid changes. The forecast is based both on the system's model and measurement data available for the system state-function. A data assimilation problem is considered as a sequence of connected inverse problems with different sets of measurements data.
Convection-diffusion-reaction models are used to describe various processes in meteorology, chemistry, biology etc. Our main example will be transport and transformation processes in the atmosphere.
Our main focus will be on the variational approach to data assimilation, including 3DVAR and 4DVAR methods. Short introduction will be given on the stochastic data assimilation methods like Kalman and particle filters.
Data Mining Tools and Languages. Team Management — Evgeniy Pavlovskiy, Doctor; Vyatcheslav Muhortov
Course Title: Data Mining Tools and Languages. Team Management
High-Performance Computing Technologies in Inverse Problem Applications — Igor Kulikov, Doctor; Maxim Shishlenin, Doctor
Course Title: High-Performance Computing Technologies in Inverse Problem Applications
Ill-Posed Problems. Advanced — Sergey Kabanikhin, Professor, Russian Academy of Sciences (Corresponding Member); Nikita Novikov, Doctor
Course Title: Ill-Posed Problems. Advanced
Image Processing — Ivan Kazantsev, Professor
Course Title: Image Processing
Aims of the Course: This course deals with the theory of digital image processing. The focus of the course is the basics of processing and analysis of digital data obtained in the imaging environment, including sampling and quantization, perception and modeling, restoration and reconstruction, segmentation and recognition. The students will learn mathematical techniques and numerical algorithms of improving a picture quality, image sharpening, contrast enhancement, edge detection, texture analysis, smoothing and noise removal as well as image transforms involved in the representation of an image in orthogonal basis. They are useful in image feature extraction, classification and understanding. Applications in remote sensing, medical imaging and computer tomography will be studied.
Introduction to Pharmacokinetics, Pharmacodynamics, Immunology and Epidemiology — Olga Krivorotko, Doctor; Dmitriy Voronov, Doctor
Course Title: Introduction to Pharmacokinetics, Pharmacodynamics, Immunology and Epidemiology
Aims of the Course:
The aims of the course are:
to give students basic knowledge in the modern theory of inverse problems in immunology and epidemiology;
to teach students to analyze the modern numerical methods for solution of inverse problems for nonlinear ordinary differential equations (mathematical models of immunology and epidemiology) in terms of their well-posedness, convergence degree and conditional stability.
Recommended prerequisites for attendance:
Basics knowledge of mathematical analysis and mathematical physics.
Contents:
Cauchy problems for nonlinear ordinary differential equations (ODEs): stability analysis, uniqueness.
Basic examples of mathematical models of immunology and epidemiology described by ODEs.
Inverse problems of immunology and epidemiology: degree of ill-posedness.
Direct and iterative regularization methods: deternministic and stohastic methods.
Linearization method.
Direct and inverse problem for simple mathematical model of infectious disease proposed by G.I. Marchuk: qualitative analysis, numerical experiments for artificial data.
Direct and inverse problem for Tuberculosis epidemiology.
Verification of the mathematical model for real statistic data.
Direct and inverse problem for HIV infection dynamics model.
Parallel algorithms for modeling big systems of ODEs.
Machine Learning and Data Mining — Vladimir Berikov, Professor
Course Title: Machine Learning and Data Mining
Aims of the Course:
The aims and objectives of the course “Machine learning and data mining” are:
giving students basic knowledge in the theory, methods and applications of intellectual data analysis;
teaching students to apply the studied methods and algorithms for the solution of applied data analysis problems;
training students to realize data analysis algorithms on computer.
Recommended prerequisites for attendance:
The basics of calculus, algebra and programming.
Contents:
The purpose of the course «Machine learning and data mining» is to provide students with basic theoretical knowledge and practical skills necessary for successful professional activity in various fields related to data analysis. The content of the course includes the main directions in modern data analysis theory: pattern recognition, prediction of quantitative variables, cluster analysis, feature selection.
Modern Numerical Modeling in Inverse Problem Applications — Igor Kulikov, Doctor; Maxim Shishlenin, Doctor
Course Title: Modern Numerical Modeling in Inverse Problem Applications
Numerical Deterministic and Stochastic Methods of Solving Nonlinear Inverse Problems — Dmitriy Voronov, Doctor; Olga Krivorotko, Doctor
Course Title: Numerical Deterministic and Stochastic Methods of Solving Nonlinear Inverse Problems
Aims of the Course:
The aims of the course are:
to give students knowledge in the modern numerical methods for solution of inverse and ill-posed problems and its applications;
to teach students to analyze and investigate the algorithms for solution of inverse problems for ODE and PDE;
to teach students to develop methods for solving inverse and ill-posed problems, using existing algorithms and the standard library, taking into account the physical statement of the problem, errors in the data and a priori information.
Recommended prerequisites for attendance:
Basics knowledge of mathematical physics, mathematical modeling, calculus and programming.
Optimization Methods in Inverse and Iill-Posed Problems — Sergey Kabanikhin, Professor, Russian Academy of Sciences (Corresponding Member); Nikita Novikov, Doctor
Course Title: Optimization Methods in Inverse and Iill-Posed Problems
Regularization Methods for Nonlinear Inverse Problems — Maxim Shishlenin, Doctor
Course Title: Regularization Methods for Nonlinear Inverse Problems
Regularization of Integral Equations — Sergey Kabanikhin, Professor, Russian Academy of Sciences (Corresponding Member); Nikita Novikov, Doctor
Course Title: Regularization of Integral Equations
Software Tools for PK/PD Models — Dmitriy Voronov, Doctor; Olga Krivorotko, Doctor
Course Title: Software Tools for PK/PD Models
Stability Analysis of Mathematical Models in Immunology and Pharmacokinetics — Dmitriy Voronov, Doctor; Olga Krivorotko, Doctor
Course Title: Stability Analysis of Mathematical Models in Immunology and Pharmacokinetics
Discrete Mathematics and Combinatorial Optimization
During the last century the discrete and computational mathematics got
boosting development which is connected mainly with the widespread involvement of
computers and computer technologies into the everyday life. This required the
development of new methods of studying, processing, transmitting, storing,
protecting and analyzing the large volumes of information and also training
the specialists knowing all these methods. A modern specialist in discrete
mathematics and combinatorial optimization has to possess a deep knowledge
of graph theory, scheduling theory, coding theory, cryptography, operations
research, data analysis methods, mathematical modeling, linear, convex and
integer programming, complexity theory, algorithms development and analysis,
etc.
The purpose of the Master Educational Programme "Discrete Mathematics and Combinatorial
Optimization" is training highly qualified specialists in the following areas:
– Operations research
– Optimization methods
– Discrete analysis
– Graph theory
– Scheduling theory
– Coding theory
– Algorithms
– Data analysis.
Such specialists should be capable of working in research institutes, universities, programming firms, engineering companies, etc.
The training is based on requirements of the State Educational Standard 01.04.02.
Approximation Algorithms — Alexander Kononov, Doctor
Course Title: Approximation Algorithms
Aims of the Course:
As the result of study of the course `Approximation algorithms’ the student should be able: to determine the combinatorial complexity of new combinatorial problems; to apply the methods of combinatorial optimization for solving NP-hard; to analyze the worst-case performance of algorithms; to construct new approximation algorithms for NP-hard optimization problems.
Recommended prerequisites for attendance:
The course `Combinatorial Optimization’.
Contents:
The course presents basic algorithmic techniques for designing approximation algorithms: greedy and local search algorithms, dynamic programming, linear programming, and randomization. There are a huge number of optimization problems that need to be solved, and most of these are NP-hard. Thus unless P=NP, there are no efficient algorithms to find optimal solutions to such problem. The course presents how to design efficient approximation algorithms that find provably near-optimal solutions in the worst case.
Coding Theory — Faina Solovyova, Professor
Course Title: Coding Theory
Aims of the Course:
The aims and objectives of the course «Coding theory» are the following:
give the basic knowledge of the theory of error-correcting codes and applications of the methods for practical implementations;
teach students to learn the main theory of cyclic codes, the methods of coding and decoding;
train students to construct codes having parameters close to optimal ones and good for transmission the information into communication symmetric channels with errors, understand the main practical implementations of coding theory to cryptography.
Recommended prerequisites for attendance:
Basic knowledge of algebra, combinatorics, and probability theory
Contents:
In the course “Coding theory” the classical and modern results from the theory of error-correcting codes in the binary and the q-ary symmetric channels are presented. The main topics are the following: the classical coding and decoding systems, the general theory of cyclic codes, concatenation and switching methods to construct codes, nontrivial properties of the most important classes of codes such as BCH-codes, Red-Solomon codes, Reed-Muller codes. The practical implementations of coding theory to transmit the information using communication channels with errors, implementations to cryptography are also considered in the course. To make the course self-contained the essential fundamentals concerning the presented coding theory results of the Galois field, linear algebra, combinatorics and probability are given.
Combinatorial Designs — Ivan Mogilnikh, Doctor
Course Title: Combinatorial Designs
Combinatorial Optimization — Ivan Davydov, Doctor
Course Title: Combinatorial Optimization
Aims of the Course:
There are many reasons for studying algorithms. The primary one is to enable students to use computer efficiently. A novice programmer, without basic knowledge of algorithms, may prove to be a disaster to his company where he works. The study of algorithms is the main objective of this course.
Contents:
One of the most important problems of modern society is the processing of vast amounts of data to make the best decision. One of the promises of the information technology era is that many decisions can now be made rapidly by computers. The science of how to make decisions in order to achieve some best possible goal has created the field of combinatorial or discrete optimization. Combinatorial optimization is one of the most active areas of discrete mathematics. It has been the subject of extensive research for over fifty years. Combinatorial optimization has its roots in combinatorics, theoretical computer science and operations research. A main motivation is that hundreds or thousands of real-life problems and phenomena can be considered as combinatorial optimization problems. Therefore, the design of combinatorial algorithms now is a vast area containing many strong techniques for various applied problems. The course `Combinatorial Optimization’ includes the fundamentals of graph theory, linear and integer programming, and complexity theory. The course covers classical topics in combinatorial optimization as well as very recent results. It consists of two big parts. Most of the problems considered in the first part have efficient algorithms. Optimal solutions of these problems can be found in time polynomial in the size of the input. While most of the problems studied in the second part of the course are NP-hard. A polynomial-time algorithm for NP-hard problems is unlikely to exist. However, in many cases one can at least find approximation algorithms with provably good performance.
Combinatorial Problems on Cayley Graphs — Elena Konstantinova, Doctor
Course Title: Combinatorial Problems on Cayley Graphs
Aims of the Course:
The aims and objectives of the course «Combinatorial Problems on Cayley Graphs» are:
to give the basic knowledge of the Cayley graphs theory;
to study theoretical approaches for proving group-theoretical and graph-theoretical results on Cayley graphs;
to investigate algorithmic approaches for getting theoretical results on Cayley graphs;
to show the interdisciplinary matter in solving problems on Cayley graphs;
to show the main applications of Cayley graphs.
Recommended prerequisites for attendance:
Basic knowledge of combinatorics, algebra, group theory and graph theory.
Contents:
The course “Combinatorial Problems on Cayley Graphs” consists of selected combinatorial problems on Cayley graphs. It presents detailed descriptions of the main theoretic and algorithmic approaches in investigations of Cayley graphs. It shows connections of Cayley graphs with applied problems arising in computer sciences and bioinformatics. In the frame of this course the fundamentals of graph theory, group theory, algebraic graph theory, combinatorics are also given. The introductory lecture of the course gives the historical perspective on the development of Cayley graphs. The final lecture of the course gives the list of open problems in the theory of Cayley graphs.
Electronic source: http://www.hippocampus.si/ISBN/978-961-6832-51-9/index.html
Cryptography and Сryptanalysis — Natalia Tokareva, Doctor
Course Title: Cryptography and Сryptanalysis
Aims of the Course:
At the end of the course «Cryptography and cryptanalysis» the student should be able:
to analyze the methods of ciphering in terms of their resistance to basic methods of cryptanalysis;
to analyze the properties of Boolean functions used in the ciphers;
to choose acceptable parameters for applications of the widespread cryptographic schemes.
Recommended prerequisites for attendance:
Basic knowledge of combinatorics, discrete mathematics, and coding theory
Contents:
This course covers the foundations of the modern cryptography and cryptanalysis. It is supposed that students are familiar with main results of information theory. In this course we study:
foundations of information theory (processing of continuous information; discretization methods; information measurement; message complexity; data sources);
problems of information storage (reliability and fail-safety, RAID-arrays; security problems);
cryptography (Shannon secrecy theory; mathematical foundations of cipher constructing; block and stream ciphers; Boolean functions in cryptography; asymmetric cryptographic systems; cryptographic protocols);
cryptanalysis (theoretical and practical results; statistical and analytic methods of cryptanalysis; cryptanalysis of asymmetric systems; etc);
pseudorandom sequences and statistical methods of their analysis;
practical aspects: secure data transmission in mobile systems and network protocols.
The course contains theoretical part (lectures) and the practical one (seminars, laboratory works). We discuss also several open problems in cryptography.
Graph Theory — Artem Pyatkin, Professor
Course Title: Graph Theory
Aims of the Course:
The aims and objectives of the course «Graph Theory» are:
providing students with the basic knowledge of graphs and their properties;
studying the main techniques of the proofs used in graph theory;
showing the applications of graphs and graph theory methods.
Recommended prerequisites for attendance:
Basic knowledge of combinatorics, discrete mathematics, and probability theory
Contents:
The course «Graph Theory» presents the most important theoretical concepts of the graph theory including matching, coloring, hamiltonicity, subgraphs and minors, random graphs, etc. The course contains the proofs of the main theorems from these fields. The knowledge of these concepts is basic for further study of discrete mathematics and combinatorial optimization. Note that although almost all proofs met in the course are constructive (i.e. they can be transformed into corresponding algorithms), the algorithmic aspects of the graph theory are beyond this course.
Machine Learning and Data Mining — Vladimir Berikov, Professor
Course Title: Machine Learning and Data Mining
Aims of the Course:
The aims and objectives of the course “Machine learning and data mining” are:
giving students basic knowledge in the theory, methods and applications of intellectual data analysis;
teaching students to apply the studied methods and algorithms for the solution of applied data analysis problems;
training students to realize data analysis algorithms on computer.
Recommended prerequisites for attendance:
The basics of calculus, algebra and programming.
Contents:
The purpose of the course «Machine learning and data mining» is to provide students with basic theoretical knowledge and practical skills necessary for successful professional activity in various fields related to data analysis. The content of the course includes the main directions in modern data analysis theory: pattern recognition, prediction of quantitative variables, cluster analysis, feature selection.
Mathematical Models in Logistics — Yury Kochetov, Professor
Course Title: Mathematical Models in Logistics
Aims of the Course:
The course `Mathematical Models in Logistics’ is devoted to the fundamental discrete combinatorial problems which have the applicability in transportation and distribution logistics, production scheduling, telecommunication, information, and other areas of industry. It presents the mathematical programming models of basic problems, such as the traveling salesman, bin-packing, vehicle routing, facility location, lot sizing and inventory problems. The course provides state-of-the-art exact and approximate algorithms, and some optimization packages to solve these problems.
Recommended prerequisites for attendance:
Basic knowledge of combinatorics, programming, and optimization methods
Contents:
This course describes the exciting challenges of the field of mathematical models in logistics and shows the results of the progress in modelling and solving these problems. Furthermore students will be explained the aspect of modelling and solving real-world logistics problems using advanced modelling systems and software. The efficiency of algorithm used depends on the several aspects such as the size of a problem, the structure of data, mathematical model, algorithm implementation and others. By the end of the course students have the feeling of these aspects by considering logistics problems and the knowledge of how to manage with them. This knowledge provides a bridge between practitioners and researchers working on supply chain management.
Operations Research — Ivan Takhonov, Doctor
Course Title: Operations Research
Aims of the Course:
At the end of the study the students should possess skills in formalizing and modelling a variety of decision-making processes; skills in investigating discrete and continuous optimization problems; skills in algorithm development and analysis.
Recommended prerequisites for attendance:
Basic knowledge of algebra and combinatorics.
Contents:
The course is designed to introduce students to basic models, concepts, and methods of Operations Research (OR). The course starts with brief introduction to computational complexity and description of some basic OR models. Some common methods to deal with optimization problems are observed (such as dynamic programming, enumeration methods) and several important graph optimization problems are considered (network flow problems, matching and assignment problems). Some `non-optimization’ models, such as project planning and analysis, game-theoretic models, are considered as well. The course concludes with brief observation of some approximation and heuristics techniques. `Operations Research’ course provides basic knowledge for more advanced courses of this Master Programme.
Parametrized Algorithms — René van BevernDr. rer. nat.
Course Title: Parametrized Algorithms
Aims of the Course:
Graduates of this course are able
to design and analyze fixed-parameter algorithms,
to design polynomial-time data reduction algorithms and to analyze their effectivity, and
to use complexity-theoretic methods to detect problems to which fixed-parameter algorithms are presumably inapplicable.
Recommended prerequisites for attendance:
Basic knowledge of combinatorics, discrete mathematics, and graph theory.
Contents:
Fixed-parameter algorithms are a recent approach for optimally solving NP-hard problems. NP-hard problems presumably cannot be solved optimally in polynomial time. Yet it is often possible to optimally and efficiently solve them using so-called fixed-parameter algorithms: their running time grows polynomially in the input size and exponentially only with respect to other problem parameters, which can be small in applications. The course teaches various fixed-parameter algorithm design techniques, including the concept of problem kernelization - a form of provably effective polynomial-time data reduction. Moreover, it teaches the complexity-theoretic techniques required to show that problems presumably do not allow for fixed-parameter algorithms.
Randomized Algorithms — René van BevernDr. rer. nat.
Course Title: Randomized Algorithms
Aims of the Course:
Graduates of this course are able
to design randomized algorithms and to apply a wide spectrum of probabilistic tools in their analysis,
to derive deterministic algorithms from randomized ones using derandomization, and
to use complexity-theoretic methods to detect problems for which randomization presumably does not help.
Recommended prerequisites for attendance:
Basic knowledge of combinatorics, discrete mathematics, graph theory, analysis, probability theory.
Contents:
Randomized algorithms base their behavior on random choice. They can be classified into two main types: Monte Carlo algorithms have a guaranteed worst-case running time but may give wrong results (with a preferably small probability), whereas Las Vegas algorithms always give a correct answer, but their running time is a random variable (with a preferably small expected value). The course teaches randomized algorithm design techniques and presents randomized algorithms for problems, deterministic (non-randomized) algorithms for which are not known, significantly more complicated, or less efficient. Moreover, it presents various techniques to derandomize algorithms. Finally, it teaches the complexity-theoretic techniques to show the limits of randomized algorithms.
Routing and Scheduling — Ilya Chernykh, Doctor
Course Title: Routing and Scheduling
Aims of the Course:
The objectives of the course «Routing and Scheduling» are:
to give students knowledge on algorithmic complexity and approximability of classic shop scheduling problems and their respective routing versions;
to teach students to develop approximation algorithms for scheduling problems and perform their worst-case analysis.
Recommended prerequisites for attendance:
The course `Scheduling Theory’
Contents:
The course «Routing and Scheduling» concerns the combination of shop scheduling problems with classic metric Traveling Salesman Problem. It contains basic information on classic shop scheduling models (open shop and flow shop) as well as recent results on the routing shop scheduling problems. The aim of the course is to introduce modern techniques and ideas for researching of shop scheduling problems and designing of efficient algorithms on the example of routing scheduling problems.
Seminar on Discrete mathematics and Combinatorial Optimization — Elena Konstantinova, Doctor; Artem Pyatkin, Professor
Course Title: Seminar on Discrete mathematics and Combinatorial Optimization