 |
GetTextbooks.com
Compare Prices & Save up to 90% |
|
|
|
| Login | Sign up | My Wish List |
 | | Elements of the Theory of Computation (2nd Edition) by Harry R. Lewis, Christos H. Papadimitriou ISBN-10: 9780132624787 ISBN-10: 0-13-262478-8 ISBN-13: 9780132624787 ISBN-13: 978-0-13-262478-7 Paperback 1997-08-17 Prentice Hall Find Lowest Price |
Editorials | ||
Product Description Lewis and Papadimitriou present this long awaited Second Edition of their best-selling theory of computation. The authors are well-known for their clear presentation that makes the material accessible to a a broad audience and requires no special previous mathematical experience. In this new edition, the authors incorporate a somewhat more informal, friendly writing style to present both classical and contemporary theories of computation. Algorithms, complexity analysis, and algorithmic ideas are introduced informally in Chapter 1, and are pursued throughout the book. Each section is followed by problems. | ||
Reviews | ||
The most understandable book on computation theory I have used Approximately two decades ago, I developed a course in the theory of computation for undergraduates. The coverage was finite automata, context-free languages, Turing machines and computational complexity. This was the text that I used and I have never regretted it and neither did the students. They found it to be very understandable, they were generally able to read and follow the proofs. Over the years, I left teaching and have recently come back to it. After using other texts for a course in computation theory in the last few years, next academic year I am going to return to this one. One of the greatest strengths is the simple form of notation, when using other textbooks I have often said something equivalent to, "I am puzzled why the author used this form of notation for this operation." I have never said that when using this book. The examples are crisp, there are many diagrams and a large number of exercises are included at the ends of the chapters. | ||
Good book, but lots of typos I used this book for a Theory of Computation (TOC) course that I did in the 4th year of my college. I must mention that I am a Math major, and had done courses in Mathematical Logic and others BEFORE doing TOC. TOC is an extremely interesting subject. I had a great instructor for my course, and towards the later part of the course I used this book only for the end of the chapter problems which I found to be very useful in understanding the course contents. This book, unfortunately has a lot of typos. Typos in Mathematical proofs are extremely irritating, because students often end up wasting a lot of time on the proofs with the typos. Another thing that I didnt like about the book was that the authors don't give sufficient examples. The section on turing machines should ideally have examples of machines for various computable functions. The authors give examples for only a few. The few examples given are well explained, but am sure the authors could have done with a some more examples. Similar problems are seen in the sections covering the pumping lemmas. The authors give only a couple of examples wherein they apply the pumping lemma for regular/context-free languages. Too little to help undergraduates master the techniques of using the very versatile and powerful pumping lemmas. They do give a good selection of exercises at the end of the chapter, but if you are using the book for self study, and dont have a good instructor to help you, you are going to have a hard time trying to solve those problems. The exercises require many original ideas, and I don't think the text/solved examples prepare one for that. | ||
No Ackermann function Computability: An Introduction to Recursive Function Theory I have a better book that gives a better introduction to this field. I have read several books (older and newer) along these lines. While this book gives a bad introduction to the tiling problem, it ignores what is pretty much a "standard" problem in modern texts : the Ackermann recursion. The text takes the Mathematical high road and leaves most of the human race out in the cold by lack of good illustrations and explanations. If I were teaching the course in computation , I might tell students to look this book up in the library, but never make them spend this much for a text that will fail all but the top 5 % of students. | ||
Needlessly cryptic; too clever for its own good This book claims to "make the essentials of the subject accessible to a broad undergraduate audience in a way that is mathematically sound but presupposes no special mathematical experience." On this count, the book fails miserably. The book starts easily enough with an introduction to sets and languages, but by the time Chapter 3 rolls around, the writing degenerates into the hectoring style of Russell and Whitehead... pages and pages of non-intuitive academic proofs, and making simple concepts needlessly complex in the name of Formality. The concepts the authors are presenting are fascinating, but in order to get to them you have to spend way too much time shuffling symbols. By the time we've made it to Chapters 6 and 7 (the good ones) we've lost most of the students in the muddy bootcamp of Chapters 3 and 4. Don't buy this book, and don't use it to teach; the Sipser book is the way to go. | ||
Great math, bad writing. I read this book while taking a bachelor level course in computer science. I am not many many years beyond that degree and thought it would be nice to reflect on it as a working professional. I now understand the math much better, and I can now somewhat read through this book... However, when I recall my days as a student, this book simply did not serve well as a text book (nor does it serve as recreational reading). The author obviously knows his set theory and discrete mathematics... The writing is just so poor and hard to read that it makes the book relatively worthless. Good books take a (potentially) complicated subject and make it easy to understand. The subject may look complicated, but it really isn't that hard to grasp once you develop a general understanding of it. If it isn't explained well, then the subject matter seems to be written in a different language. That is what happens with this book. Explanations are often given a line or two before the author continues to build upon the material. Similarly to a calculus course, the information you just learned will be used in a more advanced manner, increasing in complexity as you move forward. That is what happens here. The problem is that the few sentences aren't always enough to "get" or understand the material. If you don't quite grasp what is happening, then you immeidately become lost as the author moves on. The examples aren't always that helpful, and the information is just presented in a non reader-friendly fashion that it is exceptionally easy to get lost and lose your way... The book has the potential to be very good... but it would probably take 600 pages of writing instead of 300. If the author spent more time "hammering" in the facts of the topic, it would be way more effective as a learning tool.. | ||