Models of Computation: Exploring the Power of Computing

By John E. Savage

This text focuses on finite problems and emphasizes concrete models of machines and programming styles. Using problems defined over infinite domains and abstract machine models as models, emphasis is... This description may be from another edition of this product.

• Format: Hardcover
• Language: English
• ISBN: 0201895390
• ISBN13: 9780201895391
• Release Date: January 1998
• Publisher: Addison Wesley Longman
• Length: 600 Pages
• Weight: 1.15 lbs.
• Dimensions: 1.5" x 7.8" x 9.5"

Customer Reviews

Neat overview

An introduction to complexity theory very different from Hopcroft and Ullman's book, which is more popular in undergraduate computability and complexity classes. It has material on lower-bound methods for circuit complexity, space-time tradeoffs (and VLSI area-time tradeoffs) and memory-hierarchy tradeoffs (which are why the complexity estimates of the algorithms in Donald Knuth's _TAoCP_ are unrealistic), which I didn't know at all before opening this book. It also has a very nice explanation of the efficient parallel prefix circuit.

The Bible of Theoretical Computer Science

Here is a book that has it all: a complete summary of theoretical computer science; well organized, detailed proofs; and quite understandable for the novice. This book should become the standard in its field.