Introduction to the Theory of Computation (英語) ハードカバー – 2012/6/29
Kindle 端末は必要ありません。無料 Kindle アプリのいずれかをダウンロードすると、スマートフォン、タブレットPCで Kindle 本をお読みいただけます。
Gain a clear understanding of even the most complex, highly theoretical computational theory topics in the approachable presentation found only in the market-leading INTRODUCTION TO THE THEORY OF COMPUTATION, 3E. The number one choice for today's computational theory course, this revision continues the book's well-know, approachable style with timely revisions, additional practice, and more memorable examples in key areas. A new first-of-its-kind theoretical treatment of deterministic context-free languages is ideal for a better understanding of parsing and LR(k) grammars. You gain a solid understanding of the fundamental mathematical properties of computer hardware, software, and applications with a blend of practical and philosophical coverage and mathematical treatments, including advanced theorems and proofs. INTRODUCTION TO THE THEORY OF COMPUTATION, 3E's comprehensive coverage makes this a valuable reference for your continued studies in theoretical computing.
"The text meets my objectives very well. The author presents the material in an appealing manner, making a hard subject accessible and intuitive to the students. He manages to do that while maintaining the rigor and formalism that the subject warrants. The book has a lot of information packed in it, and can serve as a reference book for students interested in research in theoretical CS."
"As one of my students puts it, the book is 'fun to read and helps him learn the subject better'."
"Excellent prose (simple and succinct) with very good diagrams. It is by far the best presentation of automata in the business."
"This is a model for readability, with sensitivity for what students find difficult."
This only dips into the special topics, but introduces many of the important classes, and their relation to other complexity classes. Such classes as L, BPP, IP, Alternating, NC, and of course P, NP, exptime, PSPACE, and more.
It is very well written. It ussually explains the proof ideas before starting, and gives detailed proofs. If you can afford it, this book makes a great intro to complexity theory.
However, this is an intro. This book does not discuss advanced topics in depth, just enough to understand the most common comexity classes and their known relationships.
If you truly wish to understand computation at the axiomatic level, Sipser is undoubtedly the first book you should be picking up.
This book is awesome.
Sipser is a genius and Theory of Computation is an amazing subject with proofs built upon each other until incredible answers to questions that would seem to be a vast journey to figure out are completed in mathematical notation before your eyes.
I suggest reading this book even if you won't understand everything in it just to get a feel for what is going on. It was certainly a help for me to not be in the dark so much for every lecture of my insanely complex college class. This book gives you the math, but starts from where it makes sense so you can follow the thinking along and see the purpose and application of everything as well as understand the main fundamental concepts.
I recommend reading this book spread out before, during and after your theory class as you find it natural.