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**: 1,803

**Type**: N/A

**Publisher**:
Addison-Wesley Publishing

**License**:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 United States

**Post time**: 10 May 2016 11:00:00

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.

You are free to:

Share — copy and redistribute the material in any medium or format

The licensor cannot revoke these freedoms as long as you follow the license terms.

Click**here** to read the full license.

Share — copy and redistribute the material in any medium or format

The licensor cannot revoke these freedoms as long as you follow the license terms.

Click

From the Book webpage:

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.

Tweet

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.

Book Categories

Computer Science
16
Introduction to Computer Science
32
Introduction to Computer Programming
52
Algorithms and Data Structures
25
Artificial Intelligence
24
Computer Vision
31
Machine Learning
6
Neural Networks
22
Game Development and Multimedia
25
Data Communication and Networks
5
Coding Theory
16
Computer Security
9
Information Security
35
Cryptography
3
Information Theory
17
Computer Organization and Architecture
22
Operating Systems
2
Image Processing
11
Parallel Computing
4
Concurrent Programming
24
Relational Database
3
Document-oriented Database
14
Data Mining
17
Big Data
18
Data Science
23
Digital Libraries
22
Compiler Design and Construction
26
Functional Programming
13
Logic Programming
27
Object Oriented Programming
22
Formal Methods
71
Software Engineering
3
Agile Software Development
7
Information Systems
5
Geographic Information System (GIS)

Mathematics
68
Mathematics
14
Algebra
1
Abstract Algebra
27
Linear Algebra
3
Number Theory
8
Numerical Methods
2
Precalculus
10
Calculus
3
Differential Equations
5
Category Theory
11
Proofs
20
Discrete Mathematics
24
Theory of Computation
15
Graph Theory
2
Real Analysis
1
Complex Analysis
15
Probability
48
Statistics
7
Game Theory
5
Queueing Theory
13
Operations Research
16
Computer Aided Mathematics

Supporting Fields
21
Web Design and Development
1
Mobile App Design and Development
28
System Administration
2
Cloud Computing
12
Electric Circuits
7
Embedded System
28
Signal Processing
4
Network Science
3
Project Management

Operating System
Programming/Scripting
6
Ada
13
Assembly
34
C / C++
8
Common Lisp
2
Forth
35
Java
13
JavaScript
1
Lua
15
Microsoft .NET
1
Rexx
12
Perl
6
PHP
69
Python
12
R
1
Rebol
13
Ruby
2
Scheme
3
Tcl/Tk

Miscellaneous