Essentials of Theoretical Computer Science

Covers the basics of the theory of computation and provides some of the tools used in program verification, translation and compiling, and the analysis of algorithms.

**Tag(s):**
Theory of Computation

**Publication date**: 31 Dec 1996

**ISBN-10**:
n/a

**ISBN-13**:
n/a

**Paperback**:
306 pages

**Views**: 27,786

**Type**: Textbook

**Publisher**:
n/a

**License**:
n/a

**Post time**: 30 Sep 2006 04:44:37

Essentials of Theoretical Computer Science

Covers the basics of the theory of computation and provides some of the tools used in program verification, translation and compiling, and the analysis of algorithms.

Suggested by: John Pinto

Update 02/07/2017:

Personal homepage of F.D. Lewis in the Department of Computer Science at the University of Kentucky College of Engineering is no longer available. I changed the book's original URL to its mirror at the University of Colorado Denver.

Book Excerpts:

This book contains the essentials of theoretical computer science. There might be a bit more, but this is a broad introduction to the field. And, it is presented from a computer science viewpoint for computer scientists. It does not come from one of the strongholds of mathematics even though a great deal of mathematical logic lurks within.

This book covers some definitions of computing since readers must know what it is they are studying. So, several models of computation are presented including a RISC machine. And, the theory that ties it together is not omitted. Quickly following is a portion concerning things which are not computable (the unsolvability chapter) since readers also must know what they are not studying. In addition, the material on unsolvability is important for historic reasons as well as a being a mechanism for introducing concepts which aid in precise analytical thought. Besides, some of these concepts form an important portion of algorithm complexity.

At this point this book will get specific and looks at classes of machines that execute set recognition algorithms. As a counterpoint, this book also examines classes of grammars which generate these sets of strings. Pointers to applications such as circuit design, compiling, and translation are provided. These are very practical chapters since even though the material is presented as theory, applications abound.

The final fling is a study of how difficult it all was. This ties into algorithm analysis and is very central to many of our endeavors in computer science. The concepts here (in particular NP-completeness) intrude upon much of the practical work in business, government, and industry. This material is essentialif one is to know when to apply heuristics to problems.

Intended Audience:

This book was designed to be used in a one-semester course for senior computer science majors or first year masters students. (But there is enough material here for two quarters.) It covers the basics of the theory of computation and should provide some of the tools used in program verification, translation and compiling, and the analysis of algorithms. An effort was made to provide precise, logical, mathematical arguments with a minimum of pain. Whenever points could be made in the language of computer science, they were. Whenever something could be computed, the procedure was presented in algorithmic language. This is a text for computer scientists though all that will are welcome to indulge.

Update 02/07/2017:

Personal homepage of F.D. Lewis in the Department of Computer Science at the University of Kentucky College of Engineering is no longer available. I changed the book's original URL to its mirror at the University of Colorado Denver.

Book Excerpts:

This book contains the essentials of theoretical computer science. There might be a bit more, but this is a broad introduction to the field. And, it is presented from a computer science viewpoint for computer scientists. It does not come from one of the strongholds of mathematics even though a great deal of mathematical logic lurks within.

This book covers some definitions of computing since readers must know what it is they are studying. So, several models of computation are presented including a RISC machine. And, the theory that ties it together is not omitted. Quickly following is a portion concerning things which are not computable (the unsolvability chapter) since readers also must know what they are not studying. In addition, the material on unsolvability is important for historic reasons as well as a being a mechanism for introducing concepts which aid in precise analytical thought. Besides, some of these concepts form an important portion of algorithm complexity.

At this point this book will get specific and looks at classes of machines that execute set recognition algorithms. As a counterpoint, this book also examines classes of grammars which generate these sets of strings. Pointers to applications such as circuit design, compiling, and translation are provided. These are very practical chapters since even though the material is presented as theory, applications abound.

The final fling is a study of how difficult it all was. This ties into algorithm analysis and is very central to many of our endeavors in computer science. The concepts here (in particular NP-completeness) intrude upon much of the practical work in business, government, and industry. This material is essentialif one is to know when to apply heuristics to problems.

Intended Audience:

This book was designed to be used in a one-semester course for senior computer science majors or first year masters students. (But there is enough material here for two quarters.) It covers the basics of the theory of computation and should provide some of the tools used in program verification, translation and compiling, and the analysis of algorithms. An effort was made to provide precise, logical, mathematical arguments with a minimum of pain. Whenever points could be made in the language of computer science, they were. Whenever something could be computed, the procedure was presented in algorithmic language. This is a text for computer scientists though all that will are welcome to indulge.

Tweet

About The Author(s)

No information is available for this author.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Rexx
Microsoft .NET
Perl
PHP
R
Python
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors