Models of Computation Exploring the Power of Computing
This book 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.
Publication date: 23 Jul 2008
ISBN-10: 0201895390
ISBN-13: 9780201895391
Paperback: 698 pages
Views: 8,403
Type: N/A
Publisher: Addison-Wesley Publishing
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 United States
Post time: 11 May 2016 12:00:00
Models of Computation Exploring the Power of Computing
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.
About The Author(s)
John E. Savage is An Wang Professor of Computer Science at Brown University. He earned his PhD in Electrical Engineering at MIT in 1965 specializing in coding and communication theory. He joined Bell Laboratories in 1965 and the faculty of the Division of Engineering at Brown University in 1967. In 1979 he co-founded the Department of Computer Science and served as its second chair from 1985 to 1991.
John E. Savage is An Wang Professor of Computer Science at Brown University. He earned his PhD in Electrical Engineering at MIT in 1965 specializing in coding and communication theory. He joined Bell Laboratories in 1965 and the faculty of the Division of Engineering at Brown University in 1967. In 1979 he co-founded the Department of Computer Science and served as its second chair from 1985 to 1991.