Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi,

I did some browsing around here on MathOverflow, but I feel that my question is different enough from others that it warrants its own question.

Background:

I'm a computer science major, with a math minor, and have been working professionally for a couple years now. When I went through my undergraduate degree, I was basically trying to get out as fast as possible, and suffice it to say that I didn't take the time to fully digest or appreciate what I was learning, especially on the math front. I got the minor mostly because I came in with a lot of math credits, and because it would set me apart from those who just had a CS degree, not because of any particular passion for math.

While in school, I took courses through calc III, diff eq, lin alg, and then moved through analysis, topology, and algebra (one semester each) in a blur. I also got additional exposure to number theory through cryptology-focused courses, as well as some probability and statistics from Natural Language Processing and AI courses.

The Problem:

After working for a couple years, I decided to pursue a part-time master's in computer science, because this time around I genuinely was interested in pursuing material at a deeper level. Additionally, I've come to appreciate the value of math (both pure and applied), since much of computer science is based around mathematical concepts and underlying structures, and much of the "real world" is based on applied math. I know I wasted some of my time as an undergrad (I like to think of it as I wasn't mature enough to appreciate the math I was learning), but now I'd really like to learn more about math in all its abstraction, beauty, frustration, and je ne sais quoi.

The Question:

Can you recommend a roadmap for re-engaging someone with a passion for software engineering, a desire to learn about the hidden beauties in the mathematical world, and the ability to draw connections between the two? I know I can't dedicate myself full-time to this venture, but I want to learn (or re-learn) things that will make me a better mathematician, and engineer.

Thanks!

share|improve this question
2  
You need to be more specific about your objectives to get a meaningful answer. 'Learning the hidden beauties..' is very vague. –  Anon Jun 21 '10 at 5:56
    
I've made the assumption that, as a software engineer, you are probably interested in the hidden beauties in your own field. So my entry includes almost exclusively topics in theoretical computer science. –  supercooldave Jun 21 '10 at 9:55
2  
This question now has a meta thread - tea.mathoverflow.net/discussion/458/… –  François G. Dorais Jun 22 '10 at 1:01
    
I appreciate all the advice here - I'm not sure that there's a place where I would have been able to find this much information this easily. Thanks @supercooldave for the great roadmap, and thanks to everyone else for their two cents. I read through the meta thread, and do understand both sides of the coin. With roadmap in hand now, I believe any future questions of mine will be much more focused. Thanks again! –  awshepard Jun 22 '10 at 19:36
    
I have found some great courses at [Coursera](www.coursera.org), I found that courses like data analysis and machine learning combine math and programming well. They are free to take and can provide a good refresher for undergrad mathematics. –  kleineg Mar 6 at 20:16
add comment

5 Answers

up vote 10 down vote accepted

If you want to learn some of the beautiful things related to computer science, then I recommend the following topics and/or books:

  • Logic: many introductory books exist. Something like Mathematical Logic for Computer Science by Mordechai Ben-Ari focuses on CS-related topics. Learning about modal logic (eg Modal Logic by Patrick Blackburn, Maarten de Rijke, and Yde Venema, though not as a beginning text) is useful for other fields of computer science, including AI and verification and model checking.

  • Formal Languages: Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Elements of the Theory of Computation Harry R. Lewis, Christos H. Papadimitriou, and Computational Complexity by Christos H. Papadimitriou.

  • Programming Language Theory and Type Systems: Types and Programming Languages by BC Pierce

  • Model Checking: Model Checking by EM Clarke and Principles of Model Checking by Christel Baier and Joost-Pieter Katoen

  • Concurrency Theory and Process Algebra: firstly Communicating and Mobile Systems: The Pi Calculus by Robin Milner, then The Pi-Calculus: A Theory of Mobile Processes by Davide Sangiorgi and David Walker. Other possibilities include Communicating Sequential Processes by C.A.R. Hoare and Introduction to Process Algebra by Wan Fokkink. Modelling Distributed Systems by Wan Fokkink models systems using process algebra so they can be checked for correctness using model checking.

  • Verification: Verification of Sequential and Concurrent Programs by Krzysztof R. Apt, Frank S. Boer, and Ernst-Rüdiger Olderog.

  • Category Theory: Basic Category Theory for Computer Scientists by Benjamin C. Pierce or Categories and Computer Science by R. F. C. Walters.

  • Graph Theory: Graph Theory: An Advanced Course by Adrian Bondy and U.S.R. Murty

  • Lattice Theory: Introduction to Lattices and Order by B. A. Davey and H. A. Priestley

  • Semantics, Domain Theory, Abstract Interpretation: Semantics with Applications: An Appetizer by Hanne Riis Nielson and Flemming Nielson provides a rudimentary introduction, also linking denotational semantics to program analysis via abstract interpretation. Plotkin's notes on Domain Theory are excellent, more comprehensive, and more theoretically bent. Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin applies these ideas to program analysis.

Still missing: field theory (for cryptography), combinatorics, and undoubtedly other topics.

share|improve this answer
1  
@awshepard: Dave has already listed some important topics, let me add the whole subject of "discrete mathematics" (graph theory is usually considered to be a part of it). Optimization and numerical analysis both allow you to implement mathematical algorithms (it can be fun to prove that a certain algorithm works and compare that to the results you get from a program that you yourself wrote). Both are a good choice for a master thesis. You already know about cryptology. More specialized topics (but I'm fond of them): Randomized and genetic algorithms. –  Tim van Beek Jun 21 '10 at 9:20
    
@Tim van Beek, thanks for the idea - I did do some discrete math back in the day, and really enjoyed the subject. I'm sure what I got was mostly overview and could use another look through and deeper dives. –  awshepard Jun 22 '10 at 19:37
add comment

supercooldave suggested:

Category Theory: Basic Category Theory for Computer Scientists by Benjamin C. Pierce.

I'm going to anti-recommend this, and I think the reason is worth its own answer. Pierce's book is just a concise list of definitions and basic properties, and so IMO it's absolutely impenetrable unless you already know why need category theory. So if you're trying to read one of Gordon Plotkin's papers, but you only do categories occasionally, it's very useful to have it to hand.

However, basic category theory is very much worth knowing for software engineers, but IMO the best modes of use of it are not the ones emphasized in the CS literature. Theorists use it to do things like give models of the polymorphic lambda calculus, but honestly that's not a day-to-day activity.

The biggest payoff is in using category theory as a systematic view of abstract algebra. Most data types in programming naturally take the shape of algebras of one variety or another -- orders, lattices, monoids, groups, rings, etc -- and the operations to put on them are usually homomorphisms of some kind. Then, the basic concepts of category theory -- functors, natural transformations, and adjoints -- tell you how to structure the APIs between data types.

I don't know a good book exploring this perspective, though. This is not taught well in CS programs, because TCS is mostly focused on complexity and algorithmics, on the one hand, and semantics on the other. The first bunch don't care very much about universal structure (to get the best lower bounds you need to exploit problem-specific structure), and semanticists tend not to care much about particular programs (as opposed to whole programming languages).

share|improve this answer
1  
I added Categories and Computer Science by R. F. C. Walters, which considers automata and data types rather than programming languages, as such. Of course Barr and Wells' book would be good, but it is out of print (or not available from Amazon). –  supercooldave Jun 21 '10 at 10:03
    
+1 for the 'biggest payoff'. I would vote this higher if I could. –  Jacques Carette Jun 21 '10 at 12:04
    
Interesting. I got a lot out of Pierce. But maybe that's because as a mathematician I already had the algebra background but lacked the knowledge that is taught in CS. In which case the main thing wrong with the book is the title. –  Dan Piponi Jun 21 '10 at 14:31
    
@supercooldave Barr and Wells is apparently available from the publisher. There's a local group in San Francisco who've been using it for a regular reading seminar. Here's a link: crm.umontreal.ca/pub/Ventes/CatalogueEng.html –  Dan Piponi Jun 21 '10 at 18:27
    
@sigfpe: Thanks for the link. –  supercooldave Jun 21 '10 at 18:59
add comment

Read Claude Shannon's article "a mathematical theory of communication".

share|improve this answer
add comment

I don't know what languages you program in, but I find Haskell to be a great introduction to (at least parts of) category theory and type theory. It also lends itself well to investigate other parts of mathematics: a mathematical problem is often quite close to the way it's solved in Haskell.

share|improve this answer
2  
Haskell certainly provides a nice way of type checking the statements on makes in a theory. I even used it this morning. –  supercooldave Jun 21 '10 at 10:25
    
Although I find that Haskell tends to force you to un-overload the denser mathematical notations - but that can sometimes make things clearer. By the way, nice to meet you again Daev, fellow coauthor Jan of the Generic Haskell User's guide here! –  yatima2975 Jun 22 '10 at 11:53
    
Hi Jan. In fact, the theory I was prototyping with Haskell involved type-indexed functions, and it wasn't one of the 5 generic functions we'd previously talked about. Who'd have thunk it. –  supercooldave Jun 22 '10 at 18:22
add comment

A few points. It has famously been said that "there is no royal road to geometry" (meaning pure mathematics). Mathematics as currently understood is axiomatic. Moreover, as would be obvious from browsing here, the "pro" approach to mathematical questions is largely dependent on sorting material by topic area, as an initial step. Without the axiomatic framework, the classification framework, and the concepts of formal proof, you are only going to get some sort of "edited highlights". Or you are going to get the view from the angle of applications, which is fine as far as it goes. (But where it doesn't go is deeply into the mathematical tradition of the last couple of centuries).

This site has tagging by area, and I'd recommend some browsing to narrow down on the kind of areas that appeal to you. There is popularising mathematical literature. And there is plenty more online if what you want is information. Given how large a subject it is, you should probably look into one definite area at a time. I find the history of the subject to be revealing, but I think not everyone would.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.