- Paperback: 361 pages
- Publisher: Prentice Hall; 2 edition (7 Aug 1997)
- Language English
- ISBN-10: 0132624788
- ISBN-13: 978-0132624787
- Product Dimensions: 24.3 x 18.4 x 1.9 cm
- Average Customer Review: 5.0 out of 5 stars See all reviews (1 customer review)
-
Amazon Bestsellers Rank:
434,710 in Books (See Top 100 in Books)
- #69 in Books > Science & Nature > Mathematics > Discrete Mathematics
- See Complete Table of Contents
| ||||||||||||||||||
Did you know you can trade in your old books for an Amazon.co.uk Gift Card to spend on the things you want? Plus, get an extra £5 Gift Certificate when you trade in books worth £10 or more before June 30, 2012. Visit the Books Trade-In Store for more details. |
Product details |
More About the Authors
Discover books, learn about writers, and more.
Product Description
Product Description
Appropriate for senior and graduate level courses in Computer Science Theory, Automata, and Theory of Computation.
This is the long awaited Second Edition of Lewis and Papadimitriou's best-selling theory of computation text. In this substantially modified edition, the authors have enhanced the clarity of their presentation by making the material more accessible to a broader undergraduate audience with no special mathematical experience.
Suggested Tags from Similar Products(What's this?)Be the first one to add a relevant tag (keyword that's strongly related to this product)
|
Sell a Digital Version of This Book in the Kindle Store
If you are a publisher or author and hold the digital rights to a book, you can sell a digital version of it in our Kindle Store.
Learn more
What Other Items Do Customers Buy After Viewing This Item?
Customer Reviews
Most Helpful Customer Reviews
8 of 9 people found the following review helpful
Format:Paperback
I'm an University student at Portugal (University of Algarve), and my Infinitesimal Math 3 course was replaced with the Theoretical Foundations of Computer Science course.
One of the advised books was this "Elements of the Theory of Computation" by H. R. Lewis e C. H. Papadimitriou, which isn't an easy book to the ones that don't like "abstractions". This book is about Math/Computer Science, with an high level of formalism, due to all the theorems and proofs, so it implies that you have some mathematical background and interest. This isn't a Programming book.
One of the advised books was this "Elements of the Theory of Computation" by H. R. Lewis e C. H. Papadimitriou, which isn't an easy book to the ones that don't like "abstractions". This book is about Math/Computer Science, with an high level of formalism, due to all the theorems and proofs, so it implies that you have some mathematical background and interest. This isn't a Programming book.
Some people say that this is an advanced book, not be given to undergraduate students, but the fact is that this is a course lectured in the 2nd year of my Computer Science - Teaching Branch degree, here in my University.
This book covers an introduction to Discrete Mathematics (sets, relations, strings, ...), Finite Automata ( regular expressions and languages ), Context-free Languages, Turing Machines, Uncomputability and the Halting Problem (undecidable problems), Computational Complexity and NP-Completeness.
One of the major problems of this book is the lack of suficient solved examples, precious to self learners like myself. Most authors forget this crucial aspect. I'm one of the persons that prefers to learn by example.
Other good alternatives to this book (they cover most of the same topics) are:
- "Automata and Formal Language" by Dean Kelley.
- "Introduction to the Theory of Computation" by M. Sipser
- "Introduction to Automata Theory, Languages and Computation" by J. E. Hopcroft, R. Motwani e J. D. Ullman
Elements of the Theory of Computation is a good book, but not a basic one. And it's target audience is very restricted. Surely not a "for dummies" like type.
Most Helpful Customer Reviews on Amazon.com (beta)
Amazon.com:
36 reviews
31 of 34 people found the following review helpful
An Amazing Book on tough topic
20 Nov 2001
Format:Paperback
This was one of my favorite textbooks from college. In fact, I still have it on my shelf. It is a fantastic textbook, attemtping to introduce the Theoretical Foundations of Computer Science, in essence the science. In covering this, it moves into topics such as Finite Automata, Parsing, and Turing Machines.
I feel the negative reviews are due to some confusion. This is not an algorithms book, or a programming book, or an "intro to AI" book. It's a Math textbook. It's language is one of theorems and proofs, and this would be hard going for someone not comfortable with a college-level abstract mathematics background.
For those of you who have such a background, this book covers a topic where mathematics can become elegant. A physics major friend of mine fell in love with it, and he had no interest in Comp Sci!!
For it's topic, a similar book would be Feynman's lecture notes on Physics. Both those volumes and this book were attempt to bring the highest levels of theory within the field to the undergraduate audience. Both succeed.
15 of 15 people found the following review helpful
You'll love it or hate it.
20 Sep 2003
Format:Paperback
I discuss the first edition- I havent read the updated version. People have strong opinions about this classic book. Many students have it forced upon them for a class and they absolutely despise it. But a small number of people like me loved it, in fact its still one of my favorite textbooks. I first learned automata and computation theory here (which explains some of my fondness for the book), and it seemed kind of dull and strange until about halfway through- at which point I realized it's all very cool and I subsequently poured over the entire book several times. To get through it you need to enjoy mathematics and careful, rigorous definitions and proofs- rather than viewing these things as pointless obscurantism or pedantic arrogance. Engineering students tend to find the book dense, boring, and too difficult. Some people are intimidated by the sheer volume of special notation used. But if you're inclined towards mathematics or theoretical work you'll appreciate the extra rigor and precision (compared to most computation theory books). There are a few rough spots in it (I admit the development of the Herbrand expansion theorem in the last chapter is a mess, and the coverage of parsing theory isn't great), and some of the terminology and approaches are a little nonstandard, but overall a great book that will give you the foundation to begin studying computational complexity theory, recursive function theory, or mathematical logic. Note that the second edition has removed the chapters on logic, and I've heard its watered down. If you want something a little harder and more pure-math oriented, try Martin Davis's Computability and Unsolvability.
8 of 9 people found the following review helpful
A good textbook
24 April 2005
Format:Paperback
I taught a couple of classes from the first edition of this textbook, and my students did fairly well. On the whole, they were able to understand the material and solve the homework problems. I certainly wouldn't mind teaching a class on this subject from the second edition as well, which I feel is a mild improvement over the first one.
The chapter on finite automata is excellent. And the material on context-free languages is thorough and well written. So is the introduction to Turing machines.
Of course, the book then spends a fair amount of time on recursive function theory. That is exactly what I want it to do. And I think the chapter on unsolvability, starting with the Halting Problem, is excellent.
The style, especially of the first edition, is a little formal. But this is serious mathematical material, and I think it is not asking too much to require students to handle this subject in such a manner.
The chapter on finite automata is excellent. And the material on context-free languages is thorough and well written. So is the introduction to Turing machines.
Of course, the book then spends a fair amount of time on recursive function theory. That is exactly what I want it to do. And I think the chapter on unsolvability, starting with the Halting Problem, is excellent.
The style, especially of the first edition, is a little formal. But this is serious mathematical material, and I think it is not asking too much to require students to handle this subject in such a manner.
Were these reviews helpful?
Let us know
Listmania!
Look for similar items by category
- Books > Computing & Internet > Computer Science > Information Systems
- Books > Computing & Internet > Databases > Database Theory
- Books > Computing & Internet > Programming > Algorithms
- Books > Science & Nature > Mathematics > Discrete Mathematics
- Books > Science & Nature > Mathematics > Education > Higher Education
- Books > Science & Nature > Mathematics > Mathematical Foundations > Mathematical Logic
- Books > Science & Nature > Mathematics > Probability & Statistics
- Books > Science & Nature > Popular Science > Maths
- Books > Scientific, Technical & Medical > Mathematics > Applied Mathematics > Statistics & Probability
Look for similar items by subject
Feedback
- Would you like to update product info or give feedback on images?
- I am the Author, and I want to comment on my book.
- I am the Publisher, and I want to comment on this book.
