Theoretical computer science text for high-school student

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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