Discrete structures: matan for IT specialists

You look at any training program in the IT specialty, and then you will see the Discrete Mathematics discipline (possibly 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 institutes from time immemorial by mathematical analysis) are two facets of a single Mathematics, a beautiful, powerful science.

Although there was no such thing as “discrete mathematics” before, this does not mean that there were no discrete problems: Abel, Dirichlet, Fibonacci, Euler, whose names appear in the course of studying discrete mathematics, are by no means our contemporaries! But it was just that in those days, to isolate an independent branch of mathematics, a critical mass of problems and methods had not yet developed, no interconnections between them were visible. And a large number of fruitful interconnections between, at first glance, various concepts, is what mathematicians highly value in their science.

Well, mathematicians are interested in everything mathematical. Why is discrete mathematics for a programmer?

Why is it for IT specialists

Firstly, many ideas that are especially vividly illustrated on discrete tasks are also integral to computer science. Take, for example, 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 equal to one, and each next number is equal to the sum of its two 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 difficult to imagine how functional programming can be studied, and indeed many other areas of computer science, without being comfortable with recursion. A very close process to recursion is induction, a way of proving mathematical statements in which we rely on simpler ones in proving complex cases. The parallels with recursion are obvious, and indeed, a common thing,

Since we are talking about such fundamental things as induction and recursion, I cannot but say that many of the techniques that are very clearly visible on 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 according to the average value, and others.

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

Another archival skill is to accurately calculate and estimate approximately quantities. For example, how to calculate the number of times 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 here's another example. You need to choose 20 from a list of 100 products, so that their total cost is exactly 2,000 rubles (“no change”). This is a variation of the classic backpack problem . Suppose, your colleague, having thought over the night, offered to solve the problem by exhaustive search: sort through all kinds of sets of twenty goods, and, as soon as the necessary set appears during the search, give it out as an answer. By the way, the “brute force” characteristic does not always put a stigma on the algorithm. It all depends on the size of the input. So, how to figure out whether in a reasonable time it will be possible to solve by brute force this problem of choosing 20 objects from 100?

Finally, for the modern "designer of algorithms" the probabilistic method is also required to be understood.. This is a general method for solving many problems in modern combinatorics. Very often, the best solutions to problems known today are obtained by this method. For a practitioner, mastering this method is useful insofar as probabilistic algorithms have firmly taken their place in modern computer science. And when analyzing the operation of such algorithms, the intuition developed during the study of the probabilistic method helps a lot.

Discrete Structures Online Course

With the belief that the listed concepts from discrete mathematics really will not interfere with any programmer, but rather that their ignorance will interfere, I read the corresponding course at the faculty of the Moscow Institute of Physics and Technology . And recently, I had the opportunity to do an online course, which I gladly took advantage of. You can sign up for it at the link . The main thing that I wish to everyone who signed up: without fear of difficulties, take the course to the very end, and get the well-deserved title of Certified Discretion. In general, so that MOOC goes without agony and enriches it with knowledge! And I also have my own self-interest here: the more online students I have, the more I can learn by reading discussions and observing statistics of problem solving. After all, learning to learn is also never too late!

What knowledge will be required

To complete the first two modules, only school knowledge is required. 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 (what are the derivatives of the functions)”. For the last three modules, you need an idea of ​​what probability is, conditional probability, expectation, variance. It would also be nice to know what a basis and dimension of linear space are. If you are not familiar with probability and linear algebra, you can enroll in these introductory courses at the same time . Then just in time for the moment when we need this knowledge, you will have it.

Post scriptum

I could be accused of a conflict of interest, after all, I am a mathematician, and, of course, I want to bring as many Habr regulars to my sect as possible. In my defense, I can refer to this answer on Quora. Under most of the topics listed in this answer, I’m ready to personally subscribe, many of them are included in the online course. I will also refer to a selection of opinions of Yandexoids .