Steve Yegge wrote a blog entry a few years back called "Math for Programmers", as I previously mentioned I had a few other entries that parallel it, and this is one of those. I consider this an extension of his list hence the title.
One of the "themes" of my blog is math for programmers, for example see: "Math You Can Use", "Monoid for the Masses", and "The Combinatorial and Other Math of the Java Collections API". And here I am going to give some of my opinions and what I feel is a more comprehensive list than is provided in Steve Yegge’s original post, not that it’s not a good post in fact I recommend reading it. In it he recommends using a technique I like to call Wiki Surfing, which has a nice Hawaiian/Polynesian ring to it, where you surf Wikipedia to learn about Math, I am hoping that this post can in part serve as a giant "root node" to start from.
In my blog "The Math Debate" I talked about my future what and how blogs, this is the "what", I often see questions on various sites like Reddit from people who want to improve their math skills and asking how and what to learn. I wanted to talk about what I feel is important. Remember I am neither a mathematician nor do I play one on TV, although I do hope to play one on TV someday, also remember I am still learning about all of these areas so take my advice with a kosher sized grain of salt, and if you see errors please point them out.
In my opinion you can mostly, not worry, for the moment, about things like Calculus and lot of the continuous math, don’t get me wrong you do eventually want to learn or relearn these things but for CS and programming the Discrete Math is more immediately relevant. I definitely think that if you really want to successfully use math in programming you need to be something of a math generalist, which is really the "breadth first" approach that Steve Yegge mentions.
So the real question, problem if you will, is what to study, this is of course subjective and dependant on your goals. My motivation is multifaceted with two primary motivations, one is pure curiosity coupled with wanting to have a higher understanding of Life, The Universe, and Everything, the other is wanting to do more interesting computer work and to do it better. Fortunately I mostly do not find these motivations contradictory.
Math is a huge field and it is intimately intertwined which becomes more evident the deeper you dig, it seems to me that a broad perspective is helpful, of course I am laying out quite a bit here, my recommendation is to try to glean a feel for the various disciplines, also as I mentioned once you start digging sometimes you end up reading about areas that previously seemed unrelated.
If you wish to only focus on a smaller set of areas I would recommend the following for programming:
Set Theory, Logic, Graph Theory with some Combinatorics, and some basic Abstract Algebra like Groups and Monoids. Then go on to Linear Algebra, more Combinatorics, Probability and Statistics and some type of intro to Formal Language Theory and Automata Theory. Pretty much stuff you might have taken for a B.S. in CS How and what you learn is really up to you, here is a more comprehensive list:
Set Theory is in many respects the "arithmetic" of doing advanced and CS related Math it is essential and should be something that you should plan on committing the basics to memory, do you know the following concepts: union, intersection, symmetric difference, set difference, disjoint, cardinality and the power set? Many of the following disciplines rely on Set Theory, learning these basics can save you a lot of time in the sense that you may need to stop and think about them or look them up as you are learning other areas.
Another discipline which could be thought of as an "arithmetic" of Math and CS is Propositional Logic, in fact it really is the "arithmetic" of your computer at the hardware level. Also Set Theory and Logic have a number of parallels and actually the two are somewhat intertwined. Here you should ask yourself do you know the truth tables for and, or, nand, nor, and xor off the top of your head? The general relevance of Propositional Logic is enhanced by the added abstraction of Predicate Logic. Also there are Combinitory Logics like Lambda Calculus which will help you better understand functional programming among other things.
The next topic which probably needs no introduction is Graph Theory. This is another area you should really plan committing the basics to memory also you might want to consider extensive study here if you motivation is advanced programming and software architecture. Also it’s really cool and there’s tons of cool stuff happening in this field both mathematically and in our industry, like Social Network Theory. Also I think Graph Theory is one of the best maths to study, I find it fascinating and extremely relevant to IT, also it’s what I call a gateway math, once you get hooked on it, it leads to other maths.
Another area which could be considered foundational in an arithmetic sense is Combinatorics, which is science of counting. I admit that this is a math that I love and fits with being a programmer. A good programmer is always looking at things from the perspective of what are all the possible outcomes and contingencies; Combinatorics gives you a methodology to do that. I have written a programmer intro here.
While we are talking about possible outcomes the natural extension is Probability and Statistics which build in part on Combinatorics and are now pretty much in the forefront of hot "maths" for IT because of areas like Bayesian Statistics, Machine Learning and Data Science. Also if you delve deep into these then you need to be looking at both differential and integral calculus.
An increasingly important area is Abstract Algebra which includes our old friend the Monoid and Groups, Rings and Fields. I confess that there are still quite a few things here that I am trying to wrap my head around, especially the intuitively understanding whole Polynomial thing but I feel you can’t go wrong studying this and that it is central to fundamentally understanding what we do.
One math that I may have implied that you could initially skip is Trigonometry, that really isn’t true, but I think you can get away with just focusing on getting Sine and Cosine under your belt at first and then you have enough to fall back on if you need more and those two will help you with things like Linear Algebra and if you have the inclination: Fourier Transforms.
Linear Algebra is pretty crucial it’s like the Swiss Army Knife of math and to use another weak analogy it’s a little like a Collections API of math. This is definitely worth studying and is used in a lot of areas including Statistics, Machine Learning and Search Technologies which can involve things likeVector Spaces.
Relations, Functions, Posets, etc., there are some "basic" concepts that you usually get hit with during an introductory CS math course it might be part of a Discrete Math or some type of Introduction to "Advanced" or "Abstract" Math class and it will usually follow pretty close to Set Theory. These things are pretty essential, and I don’t think I was ever exposed to Posets in my curriculum which I think was one of several deficiencies. A couple of concepts that you want to know backwards and forwards, pun intended, are Injection, Surjection, and Bijection. Also it seems like the Ordering/Posets related concept of Infimum aka Greatest Lower Bound and Supremum aka Least Upper Bound come up a lot, at least in the stuff I look at.
Number Theory is actually pretty cool. Prime Numbers for example fascinate many people including me, and it has some direct but perhaps more specialized applications to CS like Hash Functions and Encryption.
Proofs – This is one area that is important and in which I am severely lacking actually with the exception of a few algebraic combinatorial proofs I’ve been proof free since `93, but it’s definitely on my todo list. I mention it separately because it can be treated as it as its own discipline even though it’s ubiquitous in Math.
CS Stuff
The following areas I would consider to be very Computer Science related and may generally be somewhat outside of main stream Math.
Algorithms, this is a no brainer, and includes the obvious Big O aka Landau Notation, it’s not only O you know. Also there are Complexity Classes, and really things that overlap with other areas like Graph Algorithms and Computability in general which involve:
Formal Language Theory and Automata Theory, go hand in hand and are needed to really understand Regular Expressions, Parsers and Compilers. Not to mention that the Von Neumann architecture is based on the Turing Machine. I am, however, a little dismayed by the number of developers including CS majors that I have encountered that have minimal or no knowledge of these, and not to be a rude but if you do not have some basic knowledge about these you don’t know jack about computers and software. I mean this in the most positive encouraging way, so get on it! Do it now! Click the links and get started! Also for Formal Language Theory it helps to understand the String Monoid.
Relational Algebra is the underlying Algebra to how SQL works, yes I know SQL is not cool right now, but learning this underlying math gives you insights that extend beyond SQL. Actually Relational Algebra relates to Set Theory and Abstract Algebra and some pretty heavy other maths like Category Theory, Topos Theory, and Fibrations, most of these are beyond my understanding at the moment.
Queuing Theory is pretty relevant to things that we do and is an area which I want to improve on so I don’t have a lot to say here, it does of course relate pretty heavily to Probability Theory and things like Markov Chains.
Information Theory (Shannon) and Algorithmic Information Theory (Kolmogorov, et al)1 both relate to a few areas one of course is Probability Theory. Compression and Encryption are related to these in a number of ways. Put simply, Shannon’s Information Theory relates representing and transmitting information, where as Algorithmic Information Theory is concerned with what is the smallest algorithm to generate strings. This is definitely interesting and relevant stuff that you want to look at.
Taking it up a notch
With Math it can be infinite and there are always more advanced things to learn, now realize that this is a broad list and while you probably want to have a general view of things, you will undoubtedly have areas that you want to focus on. Actually to do anything with math, unless you are genius, you will have make choices about what you study.
If you want to go to the next "level" whatever that means to you, you will probably want to look at the some of the above areas in more detail and here’s a list of some areas to ponder as well:
Calculus – At this point you may be thinking, hey wait I had to take this as a freshman in college or like me you took it in high school, how can this be next level stuff, isn’t it basic? Well yes and no, actually when was the last time you needed to use a Derivative or Integral when programming? Calculus, specifically Differential Calculus is often cited in arguments against math in programming. Now don’t get me wrong it’s important and relevant especially as your level of other areas increases and it may be more relevant more quickly, especially Integral Calculus if you go the Statistics/Machine Learning route.
Graph Theory is pretty huge and if you are interested in math in regards to programming work, I don’t think you can go wrong learning more about it, and after you’ve got a lot the "basic" concepts like Coloring, Planarity, Walks, and Cycles ideas, you can look into areas like Spectral Graph Theory and Expander Graphs. I just found out about these two recently and they look pretty interesting.
Other Logic topics like Multi-Valued Logics, extend the ideas of logic creating possibilities that fall outside of traditional two values of true and false. Fuzzy Logic and Probabilistic Logic add numeric values and probability to the interpretation of logic values. Modal Logics add additional semantics to traditional Logic to describe additional types of attributes like necessity and temporal characteristics. Additionally there is Metalogic and don't forget Gödel's incompleteness theorems.
Order Theory and Lattice Theory take Partially Ordered Sets to a higher level. These seem to be pretty intertwined, especially lattices, with a bunch of other areas like Algebra, Logic, and Probability. I have to wonder if Lattices should be introduced more formally earlier.
Model Theory is in some senses a convergence Abstract Algebra and Logic, so if those two maths get you jazzed you probably want to be looking here at some point.
I think an understanding of Topology is going to be critical in doing many math related tasks with computers, in a sense it already is, after all Graphs are topological concepts, in fact Euler’s solution of the "Seven Bridges of Konigsberg" problem is often cited as both the inception of Graph Theory and Topology and Euler went on to create a formula which describes the "planarity" of graphs on Topological surfaces of varying genus, additionally I have seen a number of interesting books and papers involving Topology and Computing, more on those later.
Measure Theory put simply deals with the idea of measuring sets. It is built on top a structure called a Sigma Algebra which has some similar properties to a Topological Space actually the two can be combined to create a Borel Set, most of this stuff is beyond my current level. It also relates to probablity theory in that probablity theory can be described in terms of measures especially the relationship of Event Spaces to Measure Spaces.
Analysis - I still have a lot to learn in this area but it seems to be a kind of nexus of continuous math and is a very important area for understanding advanced concepts also I have heard it described as the study of change. One branch of it is Functional Analysis. Analysis ties a lot of pretty heavy areas together including but not limited to Calculus, Measure Theory, Hilbert Spaces and an important, interesting and pretty cool area of Topology called Metric Spaces. This is another area that has a lot of the groundwork for things like Machine Learning.
Algebraic Topology is the combination of concepts of Abstract Algebra and Topology and surprisingly this may be one of the most central maths for Computer Science, one of my goals it to have some decent working knowledge of this field and I recommend that anyone seriously considering attempting to acquire a deeper understanding of Software and Computing consider studying this. Now you may not want to jump right in and there are some related areas that are more immediately relevant like Category Theory, which I have read might be better described as "Abstract Function Theory", it’s sort of the Math of Math, and it is showing up more and more in CS related areas I’m looking at you Monads! Category Theory seems to have a lot of relevance to functional programming which is more intuitive if you think "Abstract Function Theory". This also gets you back to that whole Relational Algebra area with things like Topos Theory, and Fibrations.
Game Theory is perhaps a "Penny Stock" in CS, in that it is probably not on a lot of people’s radar, but it has some very interesting possible applications, especially in terms of algorithms. It applies heavily to social sciences and considering how prominent Social Networking and the concepts like the Social Graph are becoming it seems like it might be pretty relevant. It also has applications in general management, perhaps Software Process will benefit from it as well someday.
Complex Numbers, it has always struck me how alien complex numbers seem. I am confused by the fact that they seem to be a way to represent two dimensions, so should we just always use them for that instead of two dimensional vectors? And you can take it to higher dimensions with Hypercomplex Numbers like Quarternions and Octonions. I know that complex numbers are a key to understanding Hilbert Spaces and:
Fourier Theory has many applications to natural phenomena related to Signals and Signal Processing, it is also used in Image Processing. This is an area that I still don’t know a lot about but it seems that Euler’s Formula is pretty important here.
Fractal Geometry: "All of Nature talks to me, if I could just figure what it was trying to tell me." Fractal Geometry and its sister discipline Chaos Theory describe perhaps all natural phenomena from the clustering of galaxies to the pattern of capillaries in your fingers to the Brownian Motion in your hot beverage, these patterns even apply to social phenomena and computer phenomena such as stock market patterns and network traffic and more. I feel that there are a multitude of areas in which we have only scratched the surface on this, and I think that these will become equally commonplace in computing. There are even constructs called L-Systems, invented/discovered by Aristid Lindenmayer, a botanist, to model plant growth, these structures also generate "pure" fractals like the Koch Curve. A very compelling thing about L-Systems is their similarity to the structures in the Chomsky Hierarchy. Benoit Mandelbrot, who sadly, recently passed away, coined the term Fractal and described them as "a set for which the Hausdorff-Besicovitch Dimension strictly exceeds the Topological Dimension." These are both topological concepts so in a sense Fractals are also steeped in Topology.
Now this list might seem a bit crazy and overly ambitious and this is mostly my crazy list but ironically, it partially jibes with, and was partially influenced by a book called Comprehensive Math for Computer Scientists
One last and critical point is that this is a pretty broad and probably intimidating list, I know writing it made my brain hurt, if it’s any consolation my knowledge on the above topics ranges from a decent understanding to a vague idea what the topic is about. If you develop a passion for any or all of these areas you will always feel like there is not enough time to learn what you want to learn, but remember don’t look at it as being intimidating or frustrating, look at it as an opportunity to never be bored with life.
1This is also attributed to Chaitin and Solomonoff
No comments:
Post a Comment