Discrete mathematics: calculations, graphs, random walks - free course from Open Education, training 6 weeks, from 5 to 7 hours per week, Date: December 3, 2023.

Education 2021: Doctor of Physical and Mathematical Sciences: Mathematical Institute named after. IN. A. Steklov Russian Academy of Sciences 2009: Candidate of Physical and Mathematical Sciences: Moscow State University. M.V. Lomonosov, specialty 01.01.06 “Mathematical logic, algebra and number theory”, dissertation topic: Grades weights of perceptrons (polynomial threshold Boolean functions) 2009: Postgraduate course: Moscow State University named after M.V. Lomonosov, Department of Mathematical Logic and Theory of Algorithms, specialty “Algebra, Logic and Number Theory” 2006: Specialty: Moscow State University. M.V. Lomonosov, Department of Mathematical Logic and Theory of Algorithms, specialty “Mathematics”, qualification “Mathematician”

1. Basic calculations

Let's say we need to count some objects. Is there anything better to do than just listing the objects and counting them one by one? Do we need to write out our data in its entirety to see if it is sufficient to train our model? Can we estimate how long the algorithm will run without implementing and running it? All these questions are studied by a branch of mathematics called combinatorics. We will begin to study this area of ​​mathematics, which will allow us to answer the questions listed above in simple cases.

2. Advanced calculations

We have considered several standard formulations of combinatorics, which will already allow us to solve many calculation problems. We have two goals. First, we will discuss in detail more complex formulations in combinatorics. We will discuss combination numbers in detail. We will look at another new standard formulation of combinatorics - combinations with repetitions. Second, we will practice solving calculation problems. To do this, we will, in particular, look at examples of solutions to several problems.

3. Discrete probability

 Let's learn to apply the acquired knowledge to problems about calculating probabilities. Let's discuss a discrete probabilistic model. In addition to just probabilities, we will also discuss the numerical characteristics of random experiments, random variables, as well as their main numerical parameter, the mathematical expectation.

4. Basics of Graph Theory

Graphs are one of the most common combinatorial models. They arise wherever we have some kind of relationship between pairs of objects. On the other hand, graphs have non-trivial general properties, which thus prove useful in a wide variety of practical situations. This week we'll start discussing graphs. We'll discuss basic parameters and model traversals, as well as a special class called bipartite graphs.

5. Trees and directed graphs

Let's discuss all the basic concepts related to graphs. We will also discuss graphs without cycles, directed graphs, which model practical situations in which the relationships between objects are asymmetric.

6. Project: random walks in graphs

Let's learn how to apply the acquired knowledge to build a recommendation system. First, let's discuss the general setting and consider our main tool - random walks on graphs. Then we use random walks to predict connections in graphs taken from practice.