Recently, at one online forum, the question was asked: how much is mathematics needed in the working conditions of a real programmer, how often does he use it, and in what areas? And here is my answer.
First of all, I, like almost all programmers, use
Boolean logic , from the analysis of logical expressions for conditional operators and exit criteria, to bringing such expressions into conformity, for example,
with de Morgan's laws . Most of our work is bordered by
first-order predicate calculus and other predicate logic in the form of an analysis of preconditions, invariants, and another (although it may seem that we are doing some other tasks).
Further, I often do analysis of the complexity of the algorithms. The size of the data sets being processed today is simply enormous. In 2010, at the
Techonomy conference
, Eric Schmidt said that the amount of data created today by mankind in just two days is equal to the volume of all data existing in the world as of 2003. It is important for me to be able to handle large segments of these volumes and derive benefits from them. And in this sense, understanding
the spatiotemporal complexity of the operations we apply to the data is the key to determining whether certain calculations are possible in principle. Unlike the more traditional types of
O-analysis or
theta-analysis, the constant factors on such scales have a significant impact: factor 2 does not change the asymptotic time complexity of the algorithm, but will require an increase in the number of processors from 10 thousand to 20 thousand, and this difference in consumption resources will be palpable. As a result, the calculations become more sophisticated. Examples: can I take a kind of linear calculation and reduce it to logarithmic? Is it possible to reduce memory consumption by three times? And so on.
Often I need to calculate the most unfavorable variant of the upper limit, say, the size of a certain data set. In many cases, such calculations can be non-trivial. Or it may be necessary to analyze some
recurrent formula to check how it changes as the depth of recursion increases. To do this, I, among other things, should know the
basic theorem on recurrence relations and how the principles of the analysis of
numerical series should be understood. And, probably, it will seem improbable, but sometimes it means that I need to calculate the
integral (although mostly only the
Riemann integrals). Or can I just solve the recursive relation and get a
finite number of solutions ? Will I have to resort to
linear algebra ? This leads to such things as
generating functions ,
Stirling numbers ,
matrix calculations. If you are curious about what is included in the set of fundamental mathematical concepts needed to understand computer science, refer to the first volume of Donald Knuth's “The Art of Programming”, or Knut, Ronald Graham, and Oren Patashnik's “Concrete Mathematics”.
I perform a lot of basic calculations in terms of aggregation, combination and transformation of data, and this is mainly
combinatorics that helps me (counting numbers, searching for symmetries in different dimensions, and more). I think examples from this area are obvious.
I use a lot of
discrete mathematics , in particular, to search for algebraic systems in operations on especially large data sets. Is it possible to display this or that structure with the help of a
homomorphism as a certain
group or
ring , which will be clearer to me? Is there a less tightly coupled option? Can I apply
a group action to a certain set to create a speculative transformation model that simplifies reasoning? Can I define some kind of topology for data analysis? You would be surprised if you knew how many things can be described using
discrete topologies . And no less surprise would have caused the demand for
triangle inequality .
I work a lot with
graph theory . “Creating websites” - requires not only the ability to place cute images of cats on the page. This process also involves inserting nodes into the global
hyperlink graph. Adding a single page leads to a potential increase in the number of edges of the graph, and this in turn may have an obvious at first glance impact on performance, analysis, ranking in search results and other characteristics. Understanding the consequences of such changes can help to obtain interesting information, such as how a graph grows. It turns out that this
dynamic is painfully similar to a
power law : the world wide web is a
scale-free network . What is the
shortest path between two nodes of this graph? How will such a network look like if you try to represent it as a
planar or
bipartite graph? When is it possible to comply with these properties, if of course at all possible? And what if we consider, in the form of a graph, not the world wide web, but the entire road network of North America, Europe or Asia?
There are other implications of this knowledge. Often, people do not understand that modern web pages are not just
HTML documents with links and other resources, but
tree data
structures linked together in a
graph . These trees are often crawled, processed, and dynamically updated due to the interaction between the user's web browser and some server (thanks to technologies such as
AJAX ).
An excellent and suitable example is
MathJax . Or
Gmail . Understanding how they work involves some level of knowledge of
symbolic calculations and
semantic analysis of page elements. The authors of MathJax needed to write a program capable of traversing a tree generated on the basis of
the document object model , find mathematical elements, “
parse ” them and dynamically replace them with new drawn elements. Perhaps some users who just see how it works, it is not very impressive, but under the hood there are quite complex things. I usually don't have to do something like this (I don't work with the front end), but I do things like
Lisp all the time. Please note that Lisp was originally sharpened by the mathematical processing of symbolic information: its macros completely cover the issues of processing symbolic expressions.
I work a lot with
time series . How does traffic or resource consumption change? What trends can be identified? Does one or another jump manifest itself in the delay in responding to requests or in memory consumption
seasonally ? How does the
rate of change of something react as the input data varies in different dimensions? Is there a
correlation with some external event?
I work a lot with statistical data analysis, not only to determine performance characteristics, but also to understand the data as such. In addition to searching the above-mentioned DOM semantic metadata tree (for example,
microdata and
microformats ,
RDF , other
XML data with some specific
schema ), I'm also trying to comprehend
unstructured data . What is the probability that this text is a street address? Or what is the
graphic coordinates ? In what context does it appear? Is it
spam ? Does it even make sense? Does it look like the result of a text generator based on
Markov chains? Perhaps this is a series of quotes from a well-known literary work? Or a piece of literary discussion? Or perhaps it is a discussion of spam containing a literary fragment? I still grin every time I remember a spam letter advertising drugs, wrapped in a fragment from the “Master and Margarita” Bulgakov.
Category theory .
Types in computer programming languages roughly correspond to categories, and
monads and
functors can be used to seriously and elegantly simplify some constructions. For example, in the Haskell
functional programming language, monads are used for
I / O and for
state modeling. Dealing with simplified programs makes it easier for them to work. It is easier to talk about them, they are easier to understand, change, and so on. Types can often be defined on the basis of logical reasoning, which leads to the emergence of
special cases (which can also be used in general problems of reasoning). Consider what happens if you use
inferences to apply logical functions, like those used in
prolog , to
convert graphs in
distributed systems .
Distributed systems return us to graph theory. On a real-world scale, systems fail, excavators tear fiber, earthquakes and volcanic eruptions occur, and fishing trawlers damage sea cables. To understand the consequences of such events and determine the best ways to respond to them, it is necessary to understand the characteristics of the network graph. Routing algorithms and network analysis are closely related to such things as
finding the shortest path between nodes in a graph. This will help you
Dijkstra algorithm .
And yet, how can you distribute the load from a large computation between data centers located in different parts of the world? Here you will also need some knowledge of physics: on the scale of the Internet, the
speed of light turns into a bottleneck.
Heat dissipation ,
current density per unit area, and more are examples of what programmers have to consider when working with real-world tasks. Should I place a data center in Iceland? Cheap cooling and geothermal energy sources create attractive conditions, but what about the minimum delay to users who may be interested in renting equipment in such a data center? What is the distance along a
wide circle between, for example, Iceland and London, or Berlin and Amsterdam? It is quite simple to calculate all this, but for this you need to have certain mathematical knowledge. Can we put fiber from Iceland to some other center? What is the average delay? What is the probability of rupture of the submarine cable in the North Sea within 12 months of operation? And for 48 months?
Of course, the
theory of algorithms , the
theory of automata ,
syntactic analysis ,
formal grammar ,
regular languages are all areas of knowledge that programmers constantly deal with. I often work with parsing and
pattern matching . In working with real-world data, even sets of not very large size can contain elements that can cause
pathologically bad behavior when using, for example,
backtracking techniques . Using
regular expressions to match data, I should be careful and make sure that these expressions are
really regular .
Using
a store-based automaton to parse
context-free grammar (which, by the way, happens every time you send a request to an
HTTP server), I need to make sure that I have limited the recursion depth to avoid exhausting the procedural
stack of processor
calls , which requires understanding underlying principles of computation and the mathematics on which they are based.
If I need to write my
recursive descent algorithm for some unusual grammar and it cannot match
LALR (1) (so I can't just use
yacc or
bison ), I need to be careful or keep the state stack separate from procedural recursion. This understanding is also necessary if I bypass the DOM tree (or any recursively-defined data structure).
Some programming languages consider this a difficulty in the work of the programmer and bypass it by using
segmented stacks . Of course, it would be great if I could define my collection of some analyzed resources as a
function (in the mathematical sense). And how would it be great if it came down to just some
linear programming optimization problem?
Please note that none of the above does not have any esoteric knowledge. All this is based on the experience of working with real-world tasks and data. Of course, I do not do all this every day, but I apply most of this knowledge regularly, and only some of it from time to time. Probably, observation, experience and heuristics have more influence on the process than they should (heuristic models are often incomplete and inaccurate). Do I have enough mathematical knowledge to calculate the average
error between reality and my heuristic model?
This is the essence of computer science, as well as how they interact with programming and the realities of modern computing. Being an IT professional is not the same thing as being a specialist in the theory of computing systems, and as many rightly say, such a specialist is much closer to applied mathematics than to a craftsman. I do not in any way want to detract from the importance of such professionals, since they are useful and enjoy universal respect, but just want to note that computer science is something else.
(By the way, I myself am not a computer science specialist. I studied in pure mathematics, and my professional field is much closer to engineering.)
