6
$\begingroup$

I am a high school student, I know some basic programming in java,python and visual basic. I love combinatorics and I have encountered various cases in which I have found some problems are really hard, and that's that. Sometimes I am told the problem is NP-complete or #P hard or something like that, and apparently that means there's nothing we can do about it.

I have also heard about things like Turing machines, Oracle machines and busy beavers and Halting problem, This sounds like it is very interesting but I don't get it. I would like some textbooks which explain all of these concepts to a mathematician, the less it has to do with actual computers (like the one I'm typing in right now) the better, I want to learn from a mathematicians point of view. An ideal book would be one which assumes I don't know much about computers but have a decent understanding of math.

Note I want to learn these things properly, I don't want a book that vaguely explains it. I would like a proper book.

Thank you very much

Regards.

$\endgroup$
3
$\begingroup$

Two standard books are Introduction to the Theory of Computation by Michael Sipser and Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft et al. Both follow the standard format of definition, theorem and example. You can't go wrong with either of them.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, I trust both of them cover them from a mathematical point of view? $\endgroup$ – Jorge Fernández Hidalgo Jul 17 '14 at 21:20
  • $\begingroup$ @Bananarama Yes, both are books of Mathematics. Have a look at the previews available to see if you like the style. $\endgroup$ – Ayman Hourieh Jul 17 '14 at 21:26
  • $\begingroup$ @TheEmperorofIceCream: If by "mathematical point of view" you mean rigorous proofs that would satisfy a mathematician, then the answer is yes. If you mean something else by that expression, you need to clarify what. Both texts recommended by Hourieh are regarded as upper undegraduate or beginner graduate student TCS texts. Sipser's book tends to be favored in recent times (in my experience). $\endgroup$ – Fizz Apr 11 '15 at 3:05
  • $\begingroup$ @TheEmperorofIceCream: Also, if you'd rather watch (undergraduate) lectures based on Sipser's book there's youtube.com/… by Daniel Gusfield. He has more video lectures (from related courses) at web.cs.ucdavis.edu/~gusfield $\endgroup$ – Fizz Apr 11 '15 at 10:07
2
$\begingroup$

Donald Knuth is a mathematician who defined modern computer science. You are looking for his book "The Art of Computer Programming." Be warned though, it is a very challenging book to read.

Another book that covers combinatorics and has a chapter on algorithms and algorithmic complexity would be Miklós Bóna's "A Walk through Combinatorics," if you want something lighter.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, but I don't actually want to learn to program, I want to see it from the math point of view. $\endgroup$ – Jorge Fernández Hidalgo Jul 17 '14 at 21:17
  • $\begingroup$ This is actually the mathematical point of view. The theoretical foundations of computer science can be found in this book. Knuth is extremely rigorous. $\endgroup$ – Joel Jul 17 '14 at 21:27
  • 1
    $\begingroup$ You wont learn to program with this book, you will learn how to write algorithms. $\endgroup$ – Joel Jul 17 '14 at 21:28
  • $\begingroup$ The second author's name is spelled Miklós Bóna. $\endgroup$ – Yuval Filmus Apr 11 '15 at 6:38
  • $\begingroup$ @YuvalFilmus You are right of course. Typo on my part. I took his combinatorics class in my undergrad years. $\endgroup$ – Joel Apr 13 '15 at 13:58
1
$\begingroup$

The volumes of Knuth, "The art of computer programming", are all very interesting.

Nevertheless it is also worthy to note E. Dijkstra's book, "A Discipline of Programming", in which he illustrates many important issues and algorithms and methods. It is a beautiful book for a programmer to understand a more disciplined style of programming incorporating algorithms etc., and also to determine the correctness of programs.

Also read Dijkstra's article:

Programming as a discipline of mathematical nature http://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD361.html

| cite | improve this answer | |
$\endgroup$

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