Discrete structures: matan for IT professionals

You look at any program of training in an IT specialty, and right there you will see the discipline “Discrete Mathematics” (perhaps under a different name), usually for first- or second-year students. And its presence is quite reasonable, since discrete mathematics and continuous mathematics (represented in the first year of the institutes from time immemorial by mathematical analysis) are two facets of the unified Mathematics, a beautiful, powerful science.

Although there was no such thing as “discrete mathematics” at all, this does not mean that there were no discrete tasks: Abel, Dirichlet, Fibonacci, Euler, whose names arise during the course of studying discrete mathematics - not our contemporaries! But just at that time, to isolate an independent branch of mathematics, there was still no critical mass of tasks and techniques, no interrelations between them were visible. And a large number of fruitful interrelations between, at first glance, various concepts, is that mathematicians value their science very much.
')
Well, all mathematicians are interested in mathematics. Why discrete mathematics programmer?

Why is it IT

First, many ideas, which are especially vividly illustrated on discrete problems, are also integral to informatics. Take, at least, the fundamental concepts of recursion and induction .

Recursion is literally a return, an appeal to oneself. The well-known ubiquitous Fibonacci numbers are most easily determined recursively: the first two Fibonacci numbers are one, and each following number is the sum of two of its predecessors: 1,1,2,3,5,8, ... Thus, to calculate the next number, we turn to already calculated numbers of the same kind. It is hard to imagine how functional programming can be studied, and indeed much of other computer science fields, without being familiar with recursion. A very close process to recursion is induction, a way of proving mathematical statements, in which we use the simpler ones in proof of complex cases. The parallels with recursion are obvious, and indeed, a common thing, when the inductive proof of the existence of an object can be reformulated into a description of the recursive method of constructing this object.

Since we are talking about such fundamental things as induction and recursion, I can not say that many techniques that are very well seen in examples from discrete mathematics are effective in mathematics as a whole. This is not only induction, but also the Dirichlet principle, the principle of choice by the mean value and others.

The next element, without which informatics cannot be imagined, is graphs. The simplest algorithms on graphs are necessarily included in any, even the most introductory, course on algorithms. For example, one of the classical computer science problems, the traveling salesman problem , is associated with the concept of the Hamiltonian cycle.

Another crucial skill is to count accurately and estimate approximately quantities. For example, how to calculate the number of times that a comparison operation is performed in a loop:

for i ≔ 1 to n do for j ≔ i to n do for k ≔ i to j do if a[i] > a[k] then … 

Or another example. It is necessary to choose 20 from a list of 100 products, so that their total cost is exactly 2000 rubles (“without change”). This is a variant of the classic backpack problem . Let's say your colleague, after thinking the night, suggested solving the problem of brute force: sort through all sorts of sets of twenty products, and as soon as the required set appears in the brute force, give it as an answer. By the way, the “pre-selection” characteristic does not always put a stigma on the algorithm. It all depends on the size of the input data. So, how to estimate, will it be possible in a reasonable time to solve this task of choosing 20 objects out of 100 in a reasonable way?

Finally, for the modern “algorithm designer”, the probabilistic method is obligatory for understanding. This is a general method that allows solving many problems in modern combinatorics. Very often, the best solutions of problems known today are obtained by this method. For the practice, mastering this method is useful insofar as probabilistic algorithms have firmly taken their place in modern computer science. And when analyzing the work of such algorithms, the intuition developed during the study of the probabilistic method helps a lot.

Online course "Discrete structures"

With the belief that the listed concepts from discrete mathematics really will not interfere with any programmer, but rather their ignorance will prevent them, I read the corresponding course at the Faculty of FIVT MIPT . And recently I had the opportunity to make an online course, which I gladly took advantage of. Sign up for it at the link . The main thing that I wish to all enrolled: not being afraid of difficulties, to complete the course until the very end, and get the deserved title of Graduated Discrete. In general, to MOOC passed without agony and enriched with knowledge! Yes, and I also have my own self-interest: the more online students I will have, the more I can learn by reading discussions and observing problem solving statistics. After all, learning to learn is also never too late!

What knowledge will be required

For the passage of the first two modules will require only school knowledge. The third module will require knowledge of the fundamentals of mathematical analysis at the level of “what is the limit” and “which of the functions x ²⁰ or 2 ^x grows faster (to which the derivatives of the functions are equal)”. For the last three modules, you need an idea of ​​what is probability, conditional probability, expectation, variance. It would also be nice to know what the basis and dimension of the linear space is. If you are not familiar with probability and linear algebra, you can sign up for these introductory courses as well . Then just, by the time when we need this knowledge, you will have it.

Post scriptum

I could be blamed for the conflict of interests, after all I am a mathematician, and, naturally, I want to introduce as many Habr regulars as possible to my sect. In my defense, I can refer to this answer to Quora. For most of the topics listed in this answer, I am ready to subscribe personally, many of them have entered the online course. I will also refer to the compilation of the opinions of the Yandex .