Models of Computation: Exploring the Power of Computing [Hardcover]

John E. Savage (Author)

Book Description

Publication Date: 1998

The focus of this book is on finite problems and concrete computational models. It covers the traditional topics of formal languages, automata and complexity classes, as well as an introduction to the more modern topics of space-time tradeoffs, memory hierarchies, parallel computation, the VLSI model, and circuit complexity. These topics are integrated throughout the book as illustrated by the early introduction of P-complete and NP-complete problems. Models of Computation provides the first textbook treatment of space-time tradeoffs and memory hierarchies. It gives a comprehensive introduction to computational complexity as well as a brief but modern coverage of circuit complexity. Parallelism is integrated throughout the book.

Editorial Reviews

From the Inside Flap

0201895390P04062001

From the Back Cover

Your book fills the gap which all of us felt existed too long. Congratulations on this excellent contribution to our field."

--Jan van Leeuwen, Utrecht University

"This is an impressive book. The subject has been thoroughly researched and carefully presented. All the machine models central to the modern theory of computation are covered in depth; many for the first time in textbook form. Readers will learn a great deal from the wealth of interesting material presented."

--Andrew C. Yao, Professor of Computer Science, Princeton University "Models of Computation" is an excellent new book that thoroughly covers the theory of computation including significant recent material and presents it all with insightful new approaches. This long-awaited book will serve as a milestone for the theory community."

--Akira Maruoka, Professor of Information Sciences, Tohoku University "This is computer science."
--Elliot Winard, Student, Brown University

In Models of Computation: Exploring the Power of Computing, John Savage re-examines theoretical computer science, offering a fresh approach that gives priority to resource tradeoffs and complexity classifications over the structure of machines and their relationships to languages. This viewpoint reflects a pedagogy motivated by the growing importance of computational models that are more realistic than the abstract ones studied in the 1950s, '60s and early '70s.

Assuming only some background in computer organization, Models of Computation uses circuits to simulate machines with memory, thereby making possible an early discussion of P-complete and NP-complete problems. Circuits are also used to demonstrate that tradeoffs between parameters of computation, such as space and time, regulate all computations by machines with memory. Full coverage of formal languages and automata is included along with a substantive treatment of computability. Topics such as space-time tradeoffs, memory hierarchies, parallel computation, and circuit complexity, are integrated throughout the text with an emphasis on finite problems and concrete computational models FEATURES: Includes introductory material for a first course on theoretical computer science. Builds on computer organization to provide an early introduction to P-complete and NP-complete problems. Includes a concise, modern presentation of regular, context-free and phrase-structure grammars, parsing, finite automata, pushdown automata, and computability. Includes an extensive, modern coverage of complexity classes. Provides an introduction to the advanced topics of space-time tradeoffs, memory hierarchies, parallel computation, the VLSI model, and circuit complexity, with parallelism integrated throughout. Contains over 200 figures and over 400 exercises along with an extensive bibliography.

** Instructor's materials are available from your sales rep.0201895390B04062001

See all Editorial Reviews

Product Details

• Hardcover: 672 pages
• Publisher: Addison-Wesley Pub (Sd) (1998)
• Language: English
• ISBN-10: 0201895390
• ISBN-13: 978-0201895391
• Product Dimensions: 9.3 x 7.3 x 1.6 inches
• Shipping Weight: 2.8 pounds
• Average Customer Review: 3.7 out of 5 stars  See all reviews (3 customer reviews)
• Amazon Best Sellers Rank: #1,515,794 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

6 of 7 people found the following review helpful:

2.0 out of 5 stars Too many errors and too dense, September 13, 2001

By A Customer

This review is from: Models of Computation: Exploring the Power of Computing (Hardcover)

I get unceasing complaints about this text. The explanations are too shallow, the topics are too dense, and the author presents wonderful proofs with no explanation of what it is he is really trying to prove, or why the proof is important. To make matters worse, there are material errors in the text that impact the dicussion he presents. These errors make it nearly impossible to understand the underlying points he wants to make, and unfortunately there are many errors (for example, his whole discussion of CNF in Chapter 2. There are many others).
I think that when the author corrects these errors, and rewrites uncomprenhensible parts, this could be a good text. For now it is average at best, and I do not think it is ready to be used for classes, at least not at an undergraduate level.

4.0 out of 5 stars Nice introduction to computability and complexity, January 14, 2007

By 

Ilya (Redmond, WA) - See all my reviews

Amazon Verified Purchase

This review is from: Models of Computation: Exploring the Power of Computing (Hardcover)

This an introduction to complexity theory very different from Hopcroft and Ullman's book. It has material on lower-bound methods for circuit complexity, space-time tradeoffs (and VLSI area-time tradeoffs) and memory-hierarchy tradeoffs, which I didn't know at all before opening this book. It also has a very nice explanation of the efficient parallel prefix circuit."

3 of 7 people found the following review helpful:

5.0 out of 5 stars The Bible of Theoretical Computer Science, November 3, 1997

By 

T. Duffy (San Francisco, CA) - See all my reviews
(REAL NAME)   

This review is from: Models of Computation: Exploring the Power of Computing (Hardcover)

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.