most recent 30 from http://mathoverflow.net 2013-05-20T16:42:31Z http://mathoverflow.net/feeds/question/51217 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/51217/computer-science-for-mathematicians Spencer 2011-01-05T16:49:19Z 2012-11-03T10:33:35Z

<p>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. </p> <p>I've seen computer scienctists 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.</p> <blockquote> <p>What good books - readable introductions - are there for mathematicians to learn about computer science?</p> </blockquote> <p>By this I really mean the science of <em>how computers work</em>. There are perhaps some books out there which are written in a style which mathematicians can relate to - e.g. not practicality-focussed, 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</p> <blockquote> <p>What good books - readable introductions - are there for mathematicians looking to learn about theoretical computer science, as it is as a subfield of maths?</p> </blockquote> <p>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...</p> <p>It seems quite frustrating that I have made it to grad school and know <em>very</em> little about computers and theoretical CS.</p> <p>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.</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51218#51218 Igor Rivin 2011-01-05T16:54:15Z 2011-01-05T16:54:15Z

<p>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).</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51220#51220 Noah Stein 2011-01-05T17:24:07Z 2011-01-05T17:24:07Z

<p>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".</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51223#51223 Dan Piponi 2011-01-05T17:43:37Z 2011-01-05T17:43:37Z

<p>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.)</p> <p>I mostly learnt from documents available on the web, of which there is no shortage. The exceptions were some parts of <a href="http://www.amazon.com/Computability-Logic-George-S-Boolos/dp/0521701465" rel="nofollow">Boolos and Jeffrey</a> for the theory of recursive functions and computability and <a href="http://www.amazon.com/Category-Computer-Scientists-Foundations-Computing/dp/0262660717" rel="nofollow">Basic Category Theory for Computer Scientists</a> 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, <a href="http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844" rel="nofollow">Cormen et al.</a> really opened my eyes to the kinds of non-obvious algorithms that exist and shouldn't be hard for a mathematician to read.</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51228#51228 Michal Kotowski 2011-01-05T18:05:02Z 2011-01-05T18:05:02Z

<p>"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. </p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51229#51229 John D. Cook 2011-01-05T18:11:00Z 2011-01-05T18:11:00Z

<p>I'm surprised nobody has recommended Knuth's <a href="http://www.amazon.com/gp/product/0321751043?ie=UTF8&amp;tag=theende-20&amp;linkCode=as2&amp;camp=1789&amp;creative=390957&amp;creativeASIN=0321751043" rel="nofollow">The Art of Computer Programming</a>.</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51231#51231 Justin Hilburn 2011-01-05T18:56:10Z 2011-01-06T17:56:14Z

<p>Theory A (Algorithms/Complexity):</p> <ol> <li>Kleinberg, Tardos - Algorithms</li> <li>Easley, Kleinberg - Networks Crowds and Markets</li> <li>Nisan, Tardos, Vazirani - Algorithmic Game Theory</li> <li>Arora, Barak - Computational Complexity: A Modern Approach</li> </ol> <p>Theory B (Logic/Semantics/Automated Reasoning):</p> <ol> <li>Benjamin Pierce - Types and Programming Languages</li> <li>Benjamin Pierce - <a href="http://www.cis.upenn.edu/~bcpierce/sf/" rel="nofollow">Software Foundations in Coq</a> (Really lets you see how to translate theory into practice)</li> <li>The links <a href="http://mathoverflow.net/questions/903/resources-for-learning-practical-category-theory/1954#1954" rel="nofollow">here</a></li> <li>Harrison - Practical Logic and Automated Theorem Proving</li> </ol>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51233#51233 drbobmeister 2011-01-05T19:05:33Z 2011-01-05T19:05:33Z

<p>If you want to know how <em>computers work</em>--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: <em>Computer Architectue, A Quantitative Approach</em> and <em>Computer Organization and Design: The Hardware/Software Interface</em>. They're not terribly mathematical, but they show, structurally, how modern processors organize, process, and move data. </p> <p>If you need the more basic stuff first, there are any number of good introductory texts.</p> <p>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 <em>theory</em> 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.</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51249#51249 Gerhard Paseman 2011-01-05T21:27:17Z 2011-01-05T21:27:17Z

<p>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.</p> <p>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.</p> <p>Gerhard ""Ask Me About System Design" Paseman, 2011.01.05</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51277#51277 grshutt 2011-01-06T04:10:28Z 2011-01-06T04:10:28Z

<p>While I admire both <em>The Art of Computer Programming</em> and <em>Structure and Interpretation of Computer Programs</em>, I thought I'd mention two other books in answer to the first of your two questions. </p> <p>J. Glenn Brookshear's <em>Computer Science: An Overview</em>, 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.</p> <p>David J. Eck's <em>The Most Complex Machine: A Survey of Computers and Computing</em> might be worth looking at. If I remember correctly, Eck received his PhD in mathematics from Brandeis University in 1980. </p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51332#51332 Adam 2011-01-06T19:12:36Z 2011-01-06T19:12:36Z

<p>Well, if you want to know how computers <em>work</em>, the authoritative reference on computer architecture happens to have been written by a <strong>set theorist</strong>!</p> <p><a href="http://en.wikipedia.org/wiki/John_von_Neumann" rel="nofollow">John von Neumann</a>. <a href="http://en.wikipedia.org/wiki/First_Draft_of_a_Report_on_the_EDVAC" rel="nofollow"><em>First Draft of a Report on the EDVAC</em></a> University of Pennsylvania technical report (1945) 101pp.</p> <p>Ah, the good old days: when logicians understood circuit design and computer scientists believed Rice's Theorem...</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51346#51346 Jose Arnaldo Dris 2011-01-06T22:01:50Z 2011-01-06T22:01:50Z

<p><a href="http://authors.phptr.com/tanenbaumcn4/" rel="nofollow">Computer Networks</a> 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 <a href="http://www.upou.edu.ph/academic/programs/dcs.html" rel="nofollow">Computer Science</a> at the UP Open University.</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51349#51349 Kjell Wooding 2011-01-06T22:35:53Z 2011-01-06T22:35:53Z

<p>It's a subset of computer science, certainly, but on the networking front, W.R. Stephens' <a href="http://www.amazon.com/gp/product/0201633469?ie=UTF8&amp;tag=pintdayorg-20&amp;linkCode=as2&amp;camp=1789&amp;creative=9325&amp;creativeASIN=0201633469" rel="nofollow">TCP/IP Illustrated, Vol. 1: The Protocols</a> is a book that deserves a place on <em>everybody's</em> 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.</p> <p>It is certainly the bible for understanding the theory and practice of TCP/IP networking.</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51515#51515 Jérôme JEAN-CHARLES 2011-01-09T02:32:52Z 2011-01-10T02:30:18Z

<p>This question is meaningless if you don't specify the goal(s) you have in mind. Goals are teaching , using , understanding , linking .....<br> 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. </p> <p>As a mathematician try to read some of Wadler below. It is specific but may show you what computing is about. (see <a href="http://homepages.inf.ed.ac.uk/wadler/" rel="nofollow">http://homepages.inf.ed.ac.uk/wadler/</a>) . </p> <p>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.</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/58432#58432 datageist 2011-03-14T15:01:07Z 2011-03-14T15:01:07Z

<p>Although it may not be comprehensive for your purposes, one book that's worth mentioning in this category is <a href="http://www.amazon.com/Modern-Applied-Algebra-Garrett-Birkhoff/dp/0070053812/ref=sr_1_1?ie=UTF8&amp;qid=1300112116&amp;sr=8-1" rel="nofollow">Modern Applied Algebra</a> 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 <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.bams/1183533586" rel="nofollow">this AMS review</a> helpful.</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/58439#58439 Frank 2011-03-14T15:59:02Z 2011-03-14T15:59:02Z

<p>To the latter I suggest <a href="http://books.google.com/books?id=A6uvsks0abgC&amp;printsec=frontcover&amp;dq=%2522computable+functions%2522&amp;source=bl&amp;ots=88WIabGWRw&amp;sig=afAhJNb3qrO9ALlrHo4qvtvWGbU&amp;hl=en&amp;ei=bDp-TaukL8b5sgb9v_XbBw&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=6&amp;ved=0CEAQ6AEwBQ#v=onepage&amp;q&amp;f=false" rel="nofollow">"Computable functions" By Nikolai Konstantinovich Vereshchagin and Alexander Shen</a>. It covers the basic stuff about computability and is approachable to a mathematician.</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/61388#61388 none 2011-04-12T12:15:57Z 2011-04-12T12:15:57Z

<p>You don't give any indication of what types of CS you're interested in.</p> <p>For algorithms, Knuth is classic but old-fashioned; CLRS is pretty standard now I think.</p> <p>For a connection between CS and logic, you might start with "Proofs and Types" by JY Girard (it's online, <a href="http://www.paultaylor.eu/stable/Proofs+Types.html" rel="nofollow">http://www.paultaylor.eu/stable/Proofs+Types.html</a> )</p> <p>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.</p> <p>Quantum computation: Nielsen and Chuang, Quantum computation and quantum information </p> <p>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.</p> <p>Etc...</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/61402#61402 yatima2975 2011-04-12T13:57:06Z 2011-04-12T13:57:06Z

<p>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. </p> <p>The website of the book is <a href="http://www1.idc.ac.il/tecs/" rel="nofollow">here</a>; 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.</p>

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/111360#111360 Julien Puydt 2012-11-03T10:33:35Z 2012-11-03T10:33:35Z

<p>You could also be interested in the <a href="http://en.wikipedia.org/wiki/Compilers%3A_Principles,_Techniques,_and_Tools" rel="nofollow">dragon book</a>: "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.</p>