Introduction to the Theory of Computation (英語) ハードカバー – 2005/5/1
Kindle 端末は必要ありません。無料 Kindle アプリのいずれかをダウンロードすると、スマートフォン、タブレットPCで Kindle 本をお読みいただけます。
This market leading text on computational theory provides a mathematical treatment of computer science theory designed around theorems and proofs.
"This is a model for readability, with a 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.