Answers.Body: <p>The Semantics of Programming Languages is an important and very mathematical subject. Great strides have been made in the past 20 or so years. One book that stands out is <a href="http://rads.stackoverflow.com/amzn/click/0387947752" rel="nofollow noreferrer">A Theory of Objects</a> by <a href="https://en.wikipedia.org/wiki/Luca_Cardelli" rel="nofollow noreferrer">Luca Cardelli</a> and <a href="https://en.wikipedia.org/wiki/Mart%C3%ADn_Abadi" rel="nofollow noreferrer">Martín Abadi</a></p>
  
  <p>Luca, especially, is an expert in operational semantics. He presents a generalized operational calculus for analyzing all aspects of object-oriented languages. The book is deep, but essential for those wanting a deep understanding of the underlying principles of OO languages and, perhaps, wanting to design future languages. </p>
  
  <p>Language is more than syntax. It is the semantics that lets the student form proper hypotheses about programs and programming.  </p>
  
  <p>Most compilers are still "syntax directed" but <a href="https://www.microsoft.com/en-us/research/people/petelee/" rel="nofollow noreferrer">Peter Lee</a>, in his doctoral dissertation (U of Michigan). shows how a compiler can be built from the semantics instead. </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-29T13:58:20.770Z
Answers.LastActivityDate: 2017-07-29T14:29:25.830Z
Answers.LastEditDate: 2017-07-29T14:29:25.830Z
Answers.UserDisplayName: Buffy
Answers.Body: <p>Another classic is <a href="http://rads.stackoverflow.com/amzn/click/0716710455" rel="nofollow noreferrer"><em>Computers and Intractability: A Guide to the Theory of NP-Completeness</em></a> by Garey and Johnson. As you may know, <a href="https://en.wikipedia.org/wiki/NP_(complexity)" rel="nofollow noreferrer">NP</a> (which stands for "nondeterministic polynomial time") refers to a set of problems that are computationally very difficult but whose answers can be checked in polynomial time relative to the size of their input. Whether all such problems can be solved in polynomial time (<a href="https://en.wikipedia.org/wiki/P_versus_NP_problem" rel="nofollow noreferrer">P=NP</a>?) is one of the greatest unsolved questions in computer science. </p>
  
  <p>Garey and Johnson (as the book is referred to) is about <a href="https://en.wikipedia.org/wiki/P_versus_NP_problem" rel="nofollow noreferrer">NP-Complete</a> problems, members of NP to which all other members of NP could be reduced. The book catalogs problems known to be NP-complete, including proofs that they are members, usually reductions from other NP-complete problems.</p>
  
  <p>Published in 1979, the book is somewhat outdated but is still regarded as a classic<a href="https://en.wikipedia.org/wiki/Computers_and_Intractability" rel="nofollow noreferrer"> [3]</a>. (<a href="https://scholar.google.com/scholar?cites=56570571081301115&amp;as_sdt=2005&amp;sciodt=0,5&amp;hl=en" rel="nofollow noreferrer">Google Scholar</a> lists about 60,000 citations.) The introduction (available <a href="https://pdfs.semanticscholar.org/fa33/c3a89a423f0eb00134fd291894949bf9d54e.pdf" rel="nofollow noreferrer">online</a>), in which an employee explains to their boss why they can't provide a simple solution to a problem, is also classic.</p>
  
  <p>Disclaimer: I am not a theoretical computer scientist. I welcome comments from any.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-30T23:10:39.997Z
Answers.LastActivityDate: 2017-07-30T23:20:34.947Z
Answers.LastEditDate: 2017-07-30T23:20:34.947Z
Answers.UserDisplayName: Ellen Spertus
Answers.Body: <p><a href="http://rads.stackoverflow.com/amzn/click/0321751043" rel="nofollow noreferrer">The Art of Computer Programming</a> in four volumes by Knuth is an obvious choice. </p>
  
  <p>The first chapter of the first volume is a pretty solid course in discrete mathematics all by itself. If you can do all of the problems in that chapter you can earn a PhD in CS. (Some of the problems remain unsolved, I think - at least they were when the book was first published.)</p>
  
  <p>Knuth is a Mathematician turned Computer Scientist and gives the mathematician's view of the field about as well as anyone can. You can depend on the accuracy of the book as the author has induced the community to drive out all inaccuracies using bounties. </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-29T17:52:34.190Z
Answers.Text: ob xkcd: https://xkcd.com/163/
Answers.UserDisplayName: Ellen Spertus
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-29T17:52:59.723Z
Answers.Text: Someone without your mathematical background might start with Knuth's *Concrete Mathematics*.
Answers.UserDisplayName: Ellen Spertus
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-04T08:15:45.563Z
Answers.Text: While those are excellent books, they are nigh impossible to read cover-to-cover, even for seasoned academics, yet alone students. If using this, be sure you pick small, self-contained sections and make sure beforehand that the students have all the preliminary knowledge required for understanding the chapters. Knuth is excellent if you want to go really deep, but the amount of time you need to spend on each single page to properly understand it is *very* high.
Answers.UserDisplayName: ComicSansMS
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-10T11:31:33.707Z
Answers.Text: @Ellen Spertus: "Someone without your mathematical background" The OP is a mathematician.
Answers.UserDisplayName: beroal
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-10T14:40:05.200Z
Answers.Text: @beroal I know. I was saying that the OP could skip Concrete Mathematics but others might find it useful background.
Answers.UserDisplayName: Ellen Spertus
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-10T14:41:50.587Z
Answers.Text: @EllenSpertus Thanks for the vote of confidence, but I'd probably find it an interesting read.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-10T14:43:07.977Z
Answers.Text: You're not the OP.
Answers.UserDisplayName: Ellen Spertus
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-10T14:44:20.103Z
Answers.Text: @EllenSpertus, thought you meant for the answer. Oh well. Back to our regularly scheduled programming.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-29T13:07:18.963Z
Answers.LastActivityDate: 2017-07-29T17:36:25.687Z
Answers.LastEditDate: 2017-07-29T17:36:25.687Z
Answers.UserDisplayName: Buffy
Answers.Body: <p>In addition to Knuth, I would recommend the classic <a href="https://mitpress.mit.edu/sicp/" rel="nofollow noreferrer">Structure and Interpretation of Computer Programming</a> by Abelson and Sussman. It covers such topics as:</p>
  
  <ul>
  <li>Writing simple programs that do powerful things,</li>
  <li>Blurring the lines between data and code, including functions as first-class objects,</li>
  <li>Creating little languages to solve problems,</li>
  <li>Writing an interpreter,</li>
  </ul>
  
  <p>and much more.</p>
  
  <p>It is one of the most loved and respected CS books. See also:</p>
  
  <ul>
  <li><a href="https://people.eecs.berkeley.edu/~bh/sicp.html" rel="nofollow noreferrer">Why <em>Structure and Interpretation of Computer Programs</em> matters</a>, by Brian Harvey</li>
  <li><a href="https://www.quora.com/Is-Structure-and-Interpretation-of-Computer-Programs-SICP-worth-reading" rel="nofollow noreferrer">Is "Structure and Interpretation of Computer Programs" (SICP) worth reading?</a> (Quora)</li>
  </ul>
  
  <p>Note that the text, in various formats (<a href="https://mitpress.mit.edu/sicp/full-text/book/book.html" rel="nofollow noreferrer">original HTML</a>, <a href="http://sarabander.github.io/sicp/" rel="nofollow noreferrer">HTML5</a>, <a href="https://github.com/sarabander/sicp-pdf/raw/master/sicp.pdf" rel="nofollow noreferrer">PDF</a>), is available for free online, as are <a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/video-lectures/" rel="nofollow noreferrer">video lectures by the authors</a>.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-10T11:42:56.157Z
Answers.Text: IMHO, this book is not rigorous enough for a mathematician. There are no theorems, no proofs.
Answers.UserDisplayName: beroal
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-10T14:49:20.950Z
Answers.Text: @beroal it depends what the OP wants to learn. Not all of computer science is theorems and proofs. SICP is considered the deepest introduction to programming, which is part of computer science.
Answers.UserDisplayName: Ellen Spertus
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-29T17:52:07.933Z
Answers.LastActivityDate: 2017-07-30T23:37:37.060Z
Answers.LastEditDate: 2017-07-30T23:37:37.060Z
Answers.UserDisplayName: Ellen Spertus
Body: <p>I am a mathematician but I would like to learn basics of computer science. I have seen many books that are fine but has some mistakes. For example, <code>Introduction to algorithms</code> even says that one should use $f(n)\in O(g(n))$ but still uses the notation $f(n)= O(g(n))$.</p>
  
  <p>Is there university level computer science books that are suitable for person who wants to study computer science on very rigorous books, or that are aimed to mathematician?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-29T09:31:01.360Z
Comments.Text: welcome to [cseducators.se]! A very nice question. I advise you use the [tag:resource-request] tag.
Comments.UserDisplayName: ItamarG3
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-29T12:50:06.720Z
Comments.Text: Those answering are encouraged to do more than name a book. Say why you believe the book is a good fit, and describe it to some extent. One book per answer is likely better than a single long list.
Comments.UserDisplayName: Buffy
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-29T21:29:59.977Z
Comments.Text: I already gave one answer (SICP), but, if I could give a second, I might suggest *Computers and Intractability*. https://en.wikipedia.org/wiki/Computers_and_Intractability
Comments.UserDisplayName: Ellen Spertus
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-30T01:12:49.553Z
Comments.Text: @EllenSpertus As I understand it, in situations like this, the limit is one "resource" per answer, with appropriate supporting text to clarify why it's recommended and how it fits the question. I don't recall anything limiting it to one answer per user, however. Even on non-list questions a second answer is acceptable, as long as it is distinct from the first one, as they must be, by definition, in this case. Write up the answer supporting _Computers and Intractability_.
Comments.UserDisplayName: Gypsy Spellweaver
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-30T22:53:59.547Z
Comments.Text: @GypsySpellweaver I had not realized I could give multiple answers. I'll do so.
Comments.UserDisplayName: Ellen Spertus
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-09-10T11:42:14.510Z
Comments.Text: I am afraid that your requirements "basics" and "rigor" are incompatible. Introductory books are intended for programmers, and programmers on average have weaker mathematical background and demands. Hence I recommend to pick a book for each topic in Computer Science. As you can see, some answers ("A Theory of Objects", "Computers and Intractability: A Guide to the Theory of NP-Completeness") are already narrow.
Comments.UserDisplayName: beroal
Tags: <self-learning><resource-request>
Title: Book recommendations for rigorous CS books
ThreadText: # Book recommendations for rigorous CS books
  
  (Asked by: username_0 on 2017-07-29)
  
  I am a mathematician but I would like to learn basics of computer science. I have seen many books that are fine but has some mistakes. For example, `Introduction to algorithms` even says that one should use $f(n)\in O(g(n))$ but still uses the notation $f(n)= O(g(n))$.
  
  Is there university level computer science books that are suitable for person who wants to study computer science on very rigorous books, or that are aimed to mathematician?
  
  **Tags:** self-learning, resource-request
  
  > **Comments:**
  > **username_1**: welcome to [cseducators.se]! A very nice question. I advise you use the [tag:resource-request] tag.  
  > **username_2**: Those answering are encouraged to do more than name a book. Say why you believe the book is a good fit, and describe it to some extent. One book per answer is likely better than a single long list.  
  > **username_3**: I already gave one answer (SICP), but, if I could give a second, I might suggest *Computers and Intractability*. https://en.wikipedia.org/wiki/Computers_and_Intractability  
  > **username_4**: @username_3 As I understand it, in situations like this, the limit is one "resource" per answer, with appropriate supporting text to clarify why it's recommended and how it fits the question. I don't recall anything limiting it to one answer per user, however. Even on non-list questions a second answer is acceptable, as long as it is distinct from the first one, as they must be, by definition, in this case. Write up the answer supporting _Computers and Intractability_.  
  > **username_3**: @username_4 I had not realized I could give multiple answers. I'll do so.  
  > **username_5**: I am afraid that your requirements "basics" and "rigor" are incompatible. Introductory books are intended for programmers, and programmers on average have weaker mathematical background and demands. Hence I recommend to pick a book for each topic in Computer Science. As you can see, some answers ("A Theory of Objects", "Computers and Intractability: A Guide to the Theory of NP-Completeness") are already narrow.  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_2 on 2017-07-29. Score: 7
  
  [The Art of Computer Programming](http://rads.stackoverflow.com/amzn/click/0321751043) in four volumes by Knuth is an obvious choice.
  
  The first chapter of the first volume is a pretty solid course in discrete mathematics all by itself. If you can do all of the problems in that chapter you can earn a PhD in CS. (Some of the problems remain unsolved, I think - at least they were when the book was first published.)
  
  Knuth is a Mathematician turned Computer Scientist and gives the mathematician's view of the field about as well as anyone can. You can depend on the accuracy of the book as the author has induced the community to drive out all inaccuracies using bounties.
  
  > **Comments:**
  > **username_3**: ob xkcd: https://xkcd.com/163/  
  > **username_3**: Someone without your mathematical background might start with Knuth's *Concrete Mathematics*.  
  > **username_6**: While those are excellent books, they are nigh impossible to read cover-to-cover, even for seasoned academics, yet alone students. If using this, be sure you pick small, self-contained sections and make sure beforehand that the students have all the preliminary knowledge required for understanding the chapters. Knuth is excellent if you want to go really deep, but the amount of time you need to spend on each single page to properly understand it is *very* high.  
  > **username_5**: @username_3: "Someone without your mathematical background" The OP is a mathematician.  
  > **username_3**: @username_5 I know. I was saying that the OP could skip Concrete Mathematics but others might find it useful background.  
  > **username_2**: @username_3 Thanks for the vote of confidence, but I'd probably find it an interesting read.  
  > **username_3**: You're not the OP.  
  > **username_2**: @username_3, thought you meant for the answer. Oh well. Back to our regularly scheduled programming.  
  
  ---
  
  ### Answer by username_3 on 2017-07-29. Score: 4
  
  In addition to Knuth, I would recommend the classic [Structure and Interpretation of Computer Programming](https://mitpress.mit.edu/sicp/) by Abelson and Sussman. It covers such topics as:
  
  * Writing simple programs that do powerful things,
  * Blurring the lines between data and code, including functions as first-class objects,
  * Creating little languages to solve problems,
  * Writing an interpreter,
  
  and much more.
  
  It is one of the most loved and respected CS books. See also:
  
  * [Why *Structure and Interpretation of Computer Programs* matters](https://people.eecs.berkeley.edu/~bh/sicp.html), by Brian Harvey
  * [Is "Structure and Interpretation of Computer Programs" (SICP) worth reading?](https://www.quora.com/Is-Structure-and-Interpretation-of-Computer-Programs-SICP-worth-reading) (Quora)
  
  Note that the text, in various formats ([original HTML](https://mitpress.mit.edu/sicp/full-text/book/book.html), [HTML5](http://sarabander.github.io/sicp/), [PDF](https://github.com/sarabander/sicp-pdf/raw/master/sicp.pdf)), is available for free online, as are [video lectures by the authors](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/video-lectures/).
  
  > **Comments:**
  > **username_5**: IMHO, this book is not rigorous enough for a mathematician. There are no theorems, no proofs.  
  > **username_3**: @username_5 it depends what the OP wants to learn. Not all of computer science is theorems and proofs. SICP is considered the deepest introduction to programming, which is part of computer science.  
  
  ---
  
  ### Answer by username_2 on 2017-07-29. Score: 2
  
  The Semantics of Programming Languages is an important and very mathematical subject. Great strides have been made in the past 20 or so years. One book that stands out is [A Theory of Objects](http://rads.stackoverflow.com/amzn/click/0387947752) by [Luca Cardelli](https://en.wikipedia.org/wiki/Luca_Cardelli) and [Martín Abadi](https://en.wikipedia.org/wiki/Mart%C3%ADn_Abadi)
  
  Luca, especially, is an expert in operational semantics. He presents a generalized operational calculus for analyzing all aspects of object-oriented languages. The book is deep, but essential for those wanting a deep understanding of the underlying principles of OO languages and, perhaps, wanting to design future languages.
  
  Language is more than syntax. It is the semantics that lets the student form proper hypotheses about programs and programming.
  
  Most compilers are still "syntax directed" but [Peter Lee](https://www.microsoft.com/en-us/research/people/petelee/), in his doctoral dissertation (U of Michigan). shows how a compiler can be built from the semantics instead.
  
  
  ---
  
  ### Answer by username_3 on 2017-07-30. Score: 0
  
  Another classic is [*Computers and Intractability: A Guide to the Theory of NP-Completeness*](http://rads.stackoverflow.com/amzn/click/0716710455) by Garey and Johnson. As you may know, [NP](https://en.wikipedia.org/wiki/NP_(complexity)) (which stands for "nondeterministic polynomial time") refers to a set of problems that are computationally very difficult but whose answers can be checked in polynomial time relative to the size of their input. Whether all such problems can be solved in polynomial time ([P=NP](https://en.wikipedia.org/wiki/P_versus_NP_problem)?) is one of the greatest unsolved questions in computer science.
  
  Garey and Johnson (as the book is referred to) is about [NP-Complete](https://en.wikipedia.org/wiki/P_versus_NP_problem) problems, members of NP to which all other members of NP could be reduced. The book catalogs problems known to be NP-complete, including proofs that they are members, usually reductions from other NP-complete problems.
  
  Published in 1979, the book is somewhat outdated but is still regarded as a classic [[3]](https://en.wikipedia.org/wiki/Computers_and_Intractability). ([Google Scholar](https://scholar.google.com/scholar?cites=56570571081301115&as_sdt=2005&sciodt=0,5&hl=en) lists about 60,000 citations.) The introduction (available [online](https://pdfs.semanticscholar.org/fa33/c3a89a423f0eb00134fd291894949bf9d54e.pdf)), in which an employee explains to their boss why they can't provide a simple solution to a problem, is also classic.
  
  Disclaimer: I am not a theoretical computer scientist. I welcome comments from any.
  
  
  ---
  
  