35本有关计算理论的书籍，其中不乏Christos Papadimitriou，Michael Sipser这样的大家的著作。
Algorithms and Theory of Computation Handbook is a comprehensive collection of algorithms and data structures that also covers many theoretical issues. It offers a balanced perspective that reflects the needs of practitioners, including emphasis on applications within discussions on theoretical issues. Chapters include information on finite precision issues as well as discussion of specific algorithms where algorithmic techniques are of special importance, including graph drawing, robotics, forming a VLSI chip, vision and image processing, data compression, and cryptography. The book also presents some advanced topics in combinatorial optimization and parallel/distributed computing. - applications areas where algorithms and data structuring techniques are of special importance - graph drawing - robot algorithms - VLSI layout - vision and image processing algorithms - scheduling - electronic cash - data compression - dynamic graph algorithms - on-line algorithms - multidimensional data structures - cryptography - advanced topics in combinatorial optimization and parallel/distributed computing.
Publisher: Cambridge University Press, 1980.
What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians). Dr Cutland begins with a mathematical characterisation of computable functions using a simple idealised computer (a register machine); after some comparison with other characterisations, he develops the mathematical theory, including a full discussion of non-computability and undecidability, and the theory of recursive and recursively enumerable sets. The later chapters provide an introduction to more advanced topics such as Gildel's incompleteness theorem, degrees of unsolvability, the Recursion theorems and the theory of complexity of computation. Computability is thus a branch of mathematics which is of relevance also to computer scientists and philosophers. Mathematics students with no prior knowledge of the subject and computer science students who wish to supplement their practical expertise with some theoretical background will find this book of use and interest.
Publisher: Cambridge University Press, 2008.
This book offers a comprehensive perspective to modern topics in complexity theory, which is a central field of the theoretical foundations of computer science. It addresses the looming question of what can be achieved within a limited amount of time with or without other limited natural computational resources. Can be used as an introduction for advanced undergraduate and graduate students as either a textbook or for self-study, or to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems.
01. A first Course in Logic An Introduction To Model Theory Proof Theory Computability And Complexity - Shawn Hedman(djvu)
02. Advanced Complexity Theory Lctn - Madhu Sudan(pdf)
03. Algorithm and Complexity Lctn - Herbert S. Wilf(pdf)
04. Algorithms and Theory of Computation Handbook - Mikhail J. Atallah(djvu)
05. An Introduction to Formal Language Theory that Integrates Experimentation and Proof - Allen Stoughton(pdf)
06. An Introduction To Recursive Function Theory -Nigel Cutland(pdf)
07. An Introduction to the Theory of Computation - Eitan Gurari(pdf)
08. CLASSICAL RECURSION THEORY The Theory of Functions and Sets of Natural Numbers - Piergiorgio Odifreddi(djvu)
09. Complexity of Algorithms Lctn - Peter Gacs(pdf)
10. Computation Complexity Lctn - Laszlo Lovasz(pdf)
11. Computational Complexity - Christos Papadimitriou(djvu)
12. Computational Complexity A Conceptual Perspective - Oded Goldreich(pdf)
13. Computational Complexity A Modern Approach - Sanjeev Arora(pdf)
14. Computers And Intractability A Guide To The Theory Of Np-Completeness - Michael Garey(djvu)
15. Elementary Recursion Theory and its Applications to Formal Systems - Saul Kripke(pdf)
16. Elemnts Of The Theory Of Computation 2d ed - Harry Lewis(djvu)
17. Essentials of Theoretical Computer Science - F. D. Lewis(pdf)
18. Goldreich O. Introduction to Complexity Theory (lectures, 1999)(T)(375s)(djvu)
19. Goldreich O. Introduction to complexity theory, lecture notes (1999)(375s)(pdf)
20. Introduction To Automata Theory Languages , and Computation - John Hopcroft(djvu)
21. Introduction to Complexity Theory Lecture Notes - Oded Goldreich(pdf)
22. Introduction To The Theory Of Computation - Michael Sipser(djvu)
23. Kolmogorov Complexity and Computational Complexity - Osamu Watanabe(djvu)
24. Lecture Notes for Introduction to Theory of Computation - Robert Daley(pdf)
25. Lecture Notes On Algorithm Analysis And Computation Complexity 4th ed - Ian Parberry(pdf)
26. Lewis H.R., Papadimitriou C.H. Elements of the Theory of Computation (2ed., PH, 1998)(ISBN 0132624788)(K)(T)(375s)(djvu)
27. Models of Computation - An Introduction to Computability Theory (Undergrad Topics in CS), Springer (2009)(pdf)
28. Oxford University Press - A First Course in Logic - An Introduction to Model, Proof Theory, Computability, and Complexity - 2006(pdf)
29. Parallel Complexity Theory - Ian Parberry(pdf)
30. Recursion Theory for Metamathematics - RAYMOND M. SMULLYAN(djvu)
31. Rothe J. Complexity theory and cryptology.. an introduction to cryptocomplexity (TTCS, Springer, 2005)(ISBN 3540221476)(487s)(pdf)
32. Springer - Computational Probability - Algorithms and Applications in the Mathematical Sciences - 2008(pdf)
33. The Complexity of Boolean Functions - Ingo Wegener(pdf)
34. The Computational Complexity of Machine Learning - Michael J. Kearns(pdf)
35. Theory of Computation Lecture Notes - Abhijat Vichare(pdf)