How Much Maths?

Let's start with a couple of cartoons. First up, one from AbstruseGoose. And secondly, one from xkcd.

Now, I'd characterize the craft of computer programming as using a machine to animate digital representations of mathematical structures. So, when Bennedsen and Caspersen say that learning to program is not simply a matter of learning a programming language, but is a matter of acquiring a new range of conceptual patterns which are then expressed in a specific language, they point to a key skill requirement for programmers.

I believe that vital abilities for a programmer are being able to work with different layers of abstraction, and being able to visualize and manipulate mental representations of the data structures used to represent the problem. Read Scott Hanselman's blog post Please Learn to Think About Abstractions for some insight into these matters.

So, How Much Maths?

Oh, yes. Well, that partly depends on what kind of programming you want to specialize in. However, I reckon every programmer needs some exposure to the main areas of discrete mathematics. Specifically:

  1. Boolean algebra
  2. Set theory
  3. First-order logic
  4. Graph and lattice theory
  5. Automata and formal language theory
  6. Complexity and computability theory

And this is probably a fairly good order in which to try and tackle them.

Boolean Algebra

So many aspects of computing build on this discipline that it's impossible to overstate its fundamental importance. When applied specifically to designing logic circuits it is sometimes called combinatorial logic. When applied to analysing simple logical expressions it is sometimes called propositional calculus. Unfortunately, the wide range of applications has given rise to an equally wide range of different notations. What's particularly striking is that the foundations of the topic were discovered in the 19th century, by George Boole, long before the invention of the digital computer. The Wiki article gives a good overview of the topic.

Set Theory

There's a lot of heavy mathematics in set theory, but I don't think you need all of that - the basic concepts and its connection to Boolean algebra are the most important elements for a programmer, particularly if you're interested in database programming. Like Boolean algebra, the study really takes off in the 19th century. And, again, the Wiki article gives a good introduction.

First-Order Logic

You could see this topic as a combination of propositional logic and set theory. Sometimes called Predicate Calculus or Quantification Theory, understanding this is a useful prerequisite to getting your head around logic programming and the Prolog language. A good source on logic and computing is this Wiki book which also includes some applications to describe aspects of database programming.

Graph and Lattice Theory

A lot of programming involves defining and working with data structures. A good data structure can help you understand the nature of the problem, and graph and lattice theories describe a large range of the kinds of structures that can be represented in computer languages. Further, many kinds of problem solving involve searching data structures. Once again, there are good Wiki pages on graph theory and lattice theory which give good starting points.

Automata and Formal Language Theory

Programming languages are formal languages, and a computer is an automaton. Understanding the relationship between the complexity of a formal language and the complexity of the automaton that is needed to process that language can give useful insights into how programming languages are analyzed by the computer. Again, the Wiki pages on automata and formal languages are a good starting point.

Complexity and Computability Theory

If you want to understand how difficult different kinds of problem are to solve with a computer, why some types of problem are inherently more difficult to solve than others, and why some kinds of problems can never be solved by computer, then this is what you need to study. The Wiki pages on complexity theory and computability theory get quite hairy and technical, but it's the basic concepts that are most important to grasp.

And Also...

More specialized areas of computing each bring their own mathematical requirements.

If you want to get into the nitty gritty of cryptography, you'll need a good understanding a basic number theory. There is an overview from the Department of Mathematics at the University of Massachusetts here (PDF). There is also a more technical introduction on the NRICH site.

If what you're really interested in is games programming, then you'll also need to have a solid knowledge of geometry (2D and 3D), vectors, matrix maths, and physics. You can find a good overview of these topics on the NRICH site.

And, of course, more specialized forms of scientific computing such as weather and climate modeling, nuclear and high-energy physics, and engineering simulation all bring their own mathematics prerequisites.

Do I Really Need to Know All This Stuff?

Um, well, perhaps not. Unless you want to enter a more specialized sub-field of computing, that is.

It's certainly possible to learn to write programs without knowing all this mathematical stuff. But, that said, I do think knowing some of it will make you a better programmer in the long run. And there does seem to be some evidence (Caspersen et al) indicating that good mathematical ability correlates strongly with good programming skills.