55
$\begingroup$

This is a big-list community question, so I'm sorry in advance if it is deemed too soft but I haven't seen anything similar yet.

I've seen computer scientists post questions looking to learn things from pure maths. This is basically the other way around... My ignorance may prevent me from being as specific as I think I would like to be and so I have separated my main question into two.

What good books - readable introductions - are there for mathematicians to learn about computer science?

By this I really mean the science of how computers work. There are perhaps some books out there which are written in a style which mathematicians can relate to - e.g. not practicality-focused, starting from the more abstract fundamentals and building up (I may be wrong but I'm under the impression that a lot of books in other disciplines shy away from presenting things this way around, whereas mathematicians (for better or worse) are accustomed to it). Partly to illustrate what the first question is not asking, the second question is

What good books - readable introductions - are there for mathematicians looking to learn about theoretical computer science, as it is as a subfield of maths?

Here is where my ignorance prevents me from explaining the question any more because I can only assume these two aren't the same thing...

It seems quite frustrating that I have made it to grad school and know very little about computers and theoretical CS.

Standard "one recommendation per post" is probably appropriate, + a few sentences about what the books did for you. Also, maybe I should say that I'm not looking to ditch my current interests and become a computer scientist, so things being readable is a fairly strong condition. I'm not looking to become an expert, just to deal with my own ignorance. Thanks in advance.

Improve this question
$\endgroup$
16
  • 1
    $\begingroup$ I'm not sure I understand the first question. Is it about software or hardware? $\endgroup$
    – Qiaochu Yuan
    Commented Jan 5, 2011 at 17:02
  • 14
    $\begingroup$ I don't want to sidetrack the discussion too much, but: is it clear that the best CS books for mathematicians would be any different from the best CS books for CS people? By contrast, I well understand the need for physics-for-mathematicians books, because math as viewed and practiced by physicists is not a subset of math as viewed and practiced by mathematicians. But is this the case for CS? [Not rhetorical questions. By the way, I don't know much CS myself and am looking forward to the answers.] $\endgroup$
    – Pete L. Clark
    Commented Jan 5, 2011 at 17:06
  • 9
    $\begingroup$ Knuth's TAOCP are the best CS (not programming!) books for anyone. $\endgroup$
    – Steve Huntsman
    Commented Jan 5, 2011 at 18:01
  • 2
    $\begingroup$ @Suvrit--What I mean is that while on the one hand "Teach Yourself Java" isn't a CS book so much as a programming book, TAOCP is more a CS book, and the reader shouldn't expect these to be the same. Moreover, books about computational complexity or category theory for CS are not the place to learn the basic elements of CS proper. Only after studying actual practical algorithms in some detail can a reader really gain the full benefit of the more abstract views of the subject. $\endgroup$
    – Steve Huntsman
    Commented Jan 5, 2011 at 18:18
  • 1
    $\begingroup$ You may want to check ACM's classification to get a less biased idea about CS: portal.acm.org/ccs.cfm?CFID=12395215&CFTOKEN=59446756 $\endgroup$
    – Kaveh
    Commented Mar 4, 2011 at 5:47

17 Answers 17

Reset to default
28
$\begingroup$

For the second question (theoretical computer science) I strongly recommend Sipser's Introduction to the Theory of Computation. It is a very easy read for someone with a math background, and requires essentially no specific previous knowledge. It is essentially a one-semester first course in the subject of computability and complexity theory. As such, you get all the nice classical results, but not the more recent results which are less complete, polished, or appealing to an outsider who just wants a "taste".

Improve this answer
$\endgroup$
1
23
$\begingroup$

I'm surprised nobody has recommended Knuth's The Art of Computer Programming.

Improve this answer
$\endgroup$
24
  • 3
    $\begingroup$ Knuth's books are on the shelf of almost every serious programmer I have ever met. $\endgroup$
    – drbobmeister
    Commented Jan 5, 2011 at 19:08
  • 7
    $\begingroup$ @Igor: Theoretical Computer Science might as well be thought of as a part of mathematics. I don't find Knuth's books particularly useful for my mathematical work, but I used algorithms from Knuth's books literally hundreds of times in my programs. $\endgroup$
    – Dmitri Pavlov
    Commented Jan 5, 2011 at 20:41
  • 3
    $\begingroup$ @Igor: Well, that's a different matter. I was responding to your statement that Knuth's work had "very little to do with computing". Just on the face of it, that's not true at all. I in fact teach an analysis of algorithms class. I use Cormen et al. And I also point out to my class that the very phrase "analysis of algorithms" was coined by Knuth in his preface to Volume 1. His work is fascinating, both for the wealth of information it contains, and also for the historical insights of someone who was "there at the time." $\endgroup$
    – Carl Offner
    Commented Jan 6, 2011 at 22:28
  • 4
    $\begingroup$ @Igor: CLRS is meant for theorists, not programmers. For example, to learn linked lists from CLRS one needs to possess a very high level of programming culture. And a programmer with such a high level of programming culture almost certainly already knows linked lists. Knuth's books are much better in this respect, because they actually explain how to implement linked lists. And you wouldn't learn from CLRS that Fibanacci heaps are unsuitable for real programming, even though they have better asymptotics. No offense meant, but to claim that CLRS is "vastly superior" is simply ridiculous. $\endgroup$
    – Dmitri Pavlov
    Commented Jan 7, 2011 at 0:22
  • 3
    $\begingroup$ @Igor: It might be the case that the phrase “the students appeared to have learned a lot” characterizes the situation much more accurately than you would like it to be. I really don't see any point in understanding how linked lists work if you cannot implement one yourself efficiently. For me it's much easier and faster to implement an algorithm myself than try to look it up in some library. Also, the implementations of standard algorithms such as linked lists or hash tables in languages like C++, Java, Python, or OCaml are simply way too slow. $\endgroup$
    – Dmitri Pavlov
    Commented Jan 15, 2011 at 4:56
21
$\begingroup$

Theory A (Algorithms/Complexity):

  1. Kleinberg, Tardos - Algorithms
  2. Easley, Kleinberg - Networks Crowds and Markets
  3. Nisan, Tardos, Vazirani - Algorithmic Game Theory
  4. Arora, Barak - Computational Complexity: A Modern Approach

Theory B (Logic/Semantics/Automated Reasoning):

  1. Benjamin Pierce - Types and Programming Languages
  2. Benjamin Pierce - Software Foundations in Coq (Really lets you see how to translate theory into practice)
  3. The links here
  4. Harrison - Practical Logic and Automated Theorem Proving
Improve this answer
$\endgroup$
2
  • $\begingroup$ Basic Category Theory for Computer Scientists (Foundations of Computing) from Benjamin Pierce is probably a first read don't you think so? $\endgroup$
    – Jérôme JEAN-CHARLES
    Commented Jan 10, 2011 at 3:40
  • $\begingroup$ I generally like Pierce's style but I wasn't a huge fan of BCTfCS. I think Awodey is a really good choice for a gentle introduction. $\endgroup$
    – Justin Hilburn
    Commented Jan 10, 2011 at 23:34
19
$\begingroup$

"Computational Complexity" by Christos Papadimitriou - very good introduction to logic/theory of computation (Turing machines etc.) and computational complexity. One of the best textbooks IMHO.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Very dense, though. $\endgroup$
    – Daniel Litt
    Commented Jan 6, 2011 at 0:20
18
$\begingroup$

Abelson and Sussman's Structure and Interpretation of Computer Programs is a great introduction (but not a read-before-going-to-bed book, you must do the exercises. This comment applies no matter what book you are learning the subject from).

Improve this answer
$\endgroup$
15
$\begingroup$

If you want to know how computers work--really work, the the real world--and you have some basic understanding of logic design, so you know how elementary gates and latches are made, and some basic understanding of elementary CPU structure--ALUs, registers, sequencers and crontrollers--then I think the books by Patterson and Hennessy are tops: Computer Architectue, A Quantitative Approach and Computer Organization and Design: The Hardware/Software Interface. They're not terribly mathematical, but they show, structurally, how modern processors organize, process, and move data.

If you need the more basic stuff first, there are any number of good introductory texts.

On theoretical side, I would have to agree with John D. Cook that Knuth is the place to go. (He gives a link in his answer.) The theory in Knuth is illustrated in terms of realistic machine architecture--Knuth's MIX computer, for which simulators are available online if you want to try it out. The model in Knuth is very much a programmer's model--i.e., Von Neumann architecture, rather than Turing or state-machine based models such as utilized by most theoretical computer scientists, but they show how it really looks in practice. Furthermore, his books are quite sophisticated, mathematically, and certainly propose some problems which at the time of publication were definitely open and/or research level.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Computer architecture (a la Patterson and Hennessey) as interesting and useful and having mathematical underpinnings and relevant to understanding motivations for TCS as it is, is in no way TCS and is not mathematics. $\endgroup$
    – Mitch
    Commented Jan 5, 2011 at 19:30
  • 3
    $\begingroup$ @Mitch: The question was about CS in general, not just TCS. $\endgroup$
    – Dmitri Pavlov
    Commented Jan 5, 2011 at 20:45
  • 1
    $\begingroup$ @Mitch: The OP asked, "By this I really mean the science of how computers work." This is not a purely theoretical issue, as evidenced by our participation in MO! $\endgroup$
    – drbobmeister
    Commented Jan 5, 2011 at 21:50
  • 4
    $\begingroup$ Patterson and Hennessy's Computer Architecture, A Quantitative Approach is great for understanding how computers work. $\endgroup$
    – Beren Sanders
    Commented Jan 7, 2011 at 0:03
11
$\begingroup$

For those who want to go from zero knowledge to substantial breadth quickly, I recommend A. K. Dewdney's The New Turing Omnibus. Once that book is finished, tackling some of the more sophisticated books like Knuth, Aho-Hopcroft-Ullman, and the like seems more reasonable. Further, the classic books will teach CS theory that is, well, classic, and will leave the reader ill-prepared (in my opinion) for the theoretical and technological developments of this millenium. The New Turing Omnibus will prepare the reader for classic CS theory, but will not impede those who wish to learn more recent theory.

The book has influenced my writing style. One project I am working on involves "moving a mountain one pebble at a time", and is inspired by the mountain of a book Dewdney has created.

Gerhard ""Ask Me About System Design" Paseman, 2011.01.05

Improve this answer
$\endgroup$
10
$\begingroup$

I guess I've managed to take some of the path you want. My training was as a mathematician but over the last few years I've learnt a lot about theoretical computer science. (I've programmed for many years, but had limited awareness of the existence of theoretical computer science as a field in its own right.)

I mostly learnt from documents available on the web, of which there is no shortage. The exceptions were some parts of Boolos and Jeffrey for the theory of recursive functions and computability and Basic Category Theory for Computer Scientists to help with grasping some of the beautiful connections with category theory. (I know it says "for computer scientists" but I've never met a computer scientist who liked it. On the other hand, I found it very useful as a mathematician.) Years ago, Cormen et al. really opened my eyes to the kinds of non-obvious algorithms that exist and shouldn't be hard for a mathematician to read.

Improve this answer
$\endgroup$
8
$\begingroup$

While I admire both The Art of Computer Programming and Structure and Interpretation of Computer Programs, I thought I'd mention two other books in answer to the first of your two questions.

J. Glenn Brookshear's Computer Science: An Overview, 10th ed. is intelligently organized and quite well written. It also has worthwhile chapter review problems and useful bibliographies at the end of each chapter.

David J. Eck's The Most Complex Machine: A Survey of Computers and Computing might be worth looking at. If I remember correctly, Eck received his PhD in mathematics from Brandeis University in 1980.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ I'd like to strongly second the recommendation of David Eck's Most Complex Machine. It is a great way for a mathematician to learn what CS is all about. David is not only a first-rate expositor, but he has one foot firmly in Math and the other just as firmly in CS; e.g., he is chair of the Dept. of math and CS at Hobart & Wm. Smith, and while his thesis "Gauge-natural Bundles and Generalized Gauge Theories" was very pure math, it was the first math thesis written in TeX---and in those days you had to be a programmer to use TeX. (And BTW, Eck also has a great book on how to program with Java.) $\endgroup$
    – Dick Palais
    Commented Jan 9, 2011 at 20:12
4
$\begingroup$

Computer Networks by Andrew S. Tanenbaum is the ideal introduction to computer networks.  We used that book for a one-semester self-study,  distance education course in Computer Science at the UP Open University.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The same author has written Structured Computer Operation, which is a very easy-to-read introduction to the actual mechanics of how computers work. It begins with boolean algebra and transistor-transistor logic, and moves step by step to high level programming languages like Java. This seems to be what Spencer was concerned about, perhaps more than learning how to program. I would have included a link, but I couldn't figure out how $\endgroup$
    – David White
    Commented Apr 12, 2011 at 13:23
  • $\begingroup$ @David, +1 for sharing! :) Thank YOU! $\endgroup$
    – Jose Arnaldo Bebita
    Commented Apr 13, 2011 at 2:54
3
$\begingroup$

You could also be interested in the dragon book: "Compilers: principles, techniques, and tools", by Aho, Lam, Sethi and Ullman, which is considered a classic in computer science, from the angle of compilation theory and practice.

Improve this answer
$\endgroup$
3
$\begingroup$

This question is meaningless if you don't specify the goal(s) you have in mind. Goals are teaching , using , understanding , linking .....
Some people like me think that Knuth is bad from a certain point of view: his writings are interesting, of high quality and contains precise and accurate facts yet it is "not functional" and it is misleading in a way.

As a mathematician try to read some of Wadler below. It is specific but may show you what computing is about. (see https://homepages.inf.ed.ac.uk/wadler/) .

Computing is about neatly describing parts of the real world, it is not about encoding in zeroes and ones. This confusion is akin to someone saying he 'understood maths' when he has mastered calculus.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ "Not functional" = not in the spirit of functional programming, or not written with usability in mind? $\endgroup$
    – darij grinberg
    Commented Jan 9, 2011 at 13:34
  • $\begingroup$ The second mainly but also in a sense of describing the world.I believe the first meaning (FP programming) is also concerned,but not knowledgeable enough to say so, In fact I'd be interested to know if FP think like this. Note also that I take Knuth as a serious( academically and intellectually), interesting person and mathematician too. $\endgroup$
    – Jérôme JEAN-CHARLES
    Commented Jan 10, 2011 at 2:27
2
$\begingroup$

For your first question, you could have a look at The Elements of Computing Systems, by Nisan and Schocken. It covers the workings of a computer from logic gates, via the CPU to programming languages and the OS.

The website of the book is here; via the 'Study Plan' link you can even find most of the book online, and some presentations based on it - those could be useful to get a quick idea of whether the book is right for you.

Improve this answer
$\endgroup$
2
$\begingroup$

Well, if you want to know how computers work, the authoritative reference on computer architecture happens to have been written by a set theorist!

John von Neumann. First Draft of a Report on the EDVAC University of Pennsylvania technical report (1945) 101pp.

Ah, the good old days: when logicians understood circuit design and computer scientists believed Rice's Theorem...

Improve this answer
$\endgroup$
9
  • 4
    $\begingroup$ Sort of a (bad) joke. There are entire conferences dedicated to approximating various decision procedures which Rice's Theorem shows cannot exist, under the name "static analysis". It's a thriving field (at least measured by volume of publications) with quite a lot of interest and activity, which is something I think would surprise the recursion theorists of the 30's-50's -- advances in computer hardware notwithstanding. $\endgroup$
    – Adam
    Commented Jan 7, 2011 at 18:59
  • 7
    $\begingroup$ John von Neumann a set theorist?????????? $\endgroup$
    – Igor Rivin
    Commented Jan 9, 2011 at 4:02
  • 6
    $\begingroup$ John von Neumann was pretty much an universalist. Whoever calls John von Neumann a something theorist is probably one himself. $\endgroup$
    – darij grinberg
    Commented Jan 9, 2011 at 13:36
  • 9
    $\begingroup$ Igor, Darij, the topic of von Neumann's doctoral thesis was a novel axiomatization of set theory. $\endgroup$
    – Adam
    Commented Jan 9, 2011 at 19:19
  • 2
    $\begingroup$ I don't know much about computer science, but I'd have guessed that "approximating various decision procedures which Rice's Theorem shows cannot exist" would be pretty serious business, done on a large scale, because, to name just one example, isn't that what you're doing when you write a program intended to detect computer viruses? $\endgroup$
    – Michael Hardy
    Commented Apr 12, 2011 at 12:45
1
$\begingroup$

You don't give any indication of what types of CS you're interested in.

For algorithms, Knuth is classic but old-fashioned; CLRS is pretty standard now I think.

For a connection between CS and logic, you might start with "Proofs and Types" by JY Girard (it's online, http://www.paultaylor.eu/stable/Proofs+Types.html )

Oded Goldreich (http://www.wisdom.weizmann.ac.il/~oded/) has a few books online too. Lots of good stuff on his site, browse around. He has some complexity books and an old draft of his "Foundations of Cryptography" that you might like.

Quantum computation: Nielsen and Chuang, Quantum computation and quantum information

Hang out on some CS blogs, like Scott Aaronson's (which has quieted down lately...). Look at some of the papers (http://scottaaronson.com/papers/) and articles (http://scottaaronson.com/blog) on his site.

Etc...

Improve this answer
$\endgroup$
1
$\begingroup$

Although it may not be comprehensive for your purposes, one book that's worth mentioning in this category is Modern Applied Algebra by Garrett Birkhoff and Thomas Bartee. It's mainly interesting because the theory it presents has a much more algebraic "flavor" than a typical Computer Science treatment of the same material. There doesn't seem to be a decent preview of the book online, so you may find this AMS review helpful.

Improve this answer
$\endgroup$
0
$\begingroup$

It's a subset of computer science, certainly, but on the networking front, W.R. Stephens' TCP/IP Illustrated, Vol. 1: The Protocols is a book that deserves a place on everybody's shelf. It's a very hands-on book, including the sources used to actually implement various parts of the TCP/IP stack (from a variety of Unix systems). It also has Fantastically useful diagrams, and makes extensive use of command-line tools to actually test the theory being discussed.

It is certainly the bible for understanding the theory and practice of TCP/IP networking.

Improve this answer
$\endgroup$
5
  • 4
    $\begingroup$ Despite being an element of the set "everybody", I rather doubt that this book belongs on my shelf... $\endgroup$
    – Andy Putman
    Commented Jan 6, 2011 at 22:59
  • 1
    $\begingroup$ "Belongs" perhaps not, but it does deserve it. ;) $\endgroup$
    – Kjell Wooding
    Commented Jan 7, 2011 at 1:46
  • 2
    $\begingroup$ I always thought that the Dodge Dart repair manual was very lucid, and yet I am not sure it belongs on every physicists' bookshelf... $\endgroup$
    – Igor Rivin
    Commented Jan 9, 2011 at 4:05
  • 1
    $\begingroup$ Unless the physicist in question was asking about learning auto repair. Let me phrase the question backwards. If I were to ask "What is a good book for a computer scientist to learn about mathematics," would it make sense for someone to recommend Hardy & Wright to me? Number theory is a merely a subset of mathematics. Computer Networking is a subset of computer science, but greatly contributes to an understanding of software architectures - in particular layered design. This is the best book I know of for understanding this very significant component of "the science of how computers work." $\endgroup$
    – Kjell Wooding
    Commented Jan 11, 2011 at 19:08
  • 1
    $\begingroup$ @Kjell: I was unnecessarily facetious. Networking is engineering, not science of any kind. Just as a civil engineer learns physics before he learns about bridges, so should someone start learning about computers from something much more abstract than the TCP stack. $\endgroup$
    – Igor Rivin
    Commented Jan 27, 2011 at 5:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .