Amazon.com
"Intended as an upper-level undergraduate or introductory graduate text in computer science theory," this book lucidly covers the key concepts and theorems of the theory of computation. The presentation is remarkably clear; for example, the "proof idea," which offers the reader an intuitive feel for how the proof was constructed, accompanies many of the theorems and a proof. Introduction to the Theory of Computation covers the usual topics for this type of text plus it features a solid section on complexity theory--including an entire chapter on space complexity. The final chapter introduces more advanced topics, such as the discussion of complexity classes associated with probabilistic algorithms.
Book Description
This highly anticipated revision builds upon the strengths of the previous edition. Sipser's candid, crystal-clear style allows students at every level to understand and enjoy this field. His innovative "proof idea" sections explain profound concepts in plain English. The new edition incorporates many improvements students and professors have suggested over the years, and offers updated, classroom-tested problem sets at the end of each chapter.
Customer Reviews:
My choice for textbook in my computation theory class.......2007-10-01
I recently encountered this book at a publisher's booth at a computer conference and read it on the ride back home. This morning I made a trip to the college bookstore and notified them that it is the textbook that I will be using in my computation theory class this spring.
The chapter titles are:
0) Introduction - this chapter contains the fundamental mathematical background of sets, functions, graphs and proofs. For most students, it could be skipped or skimmed.
1) Regular languages - this chapter is an introduction to deterministic and nondeterministic finite automata and regular expressions.
2) Context-free languages - an introduction to context-free grammars and pushdown automata.
3) The Church-Turing theses - an introduction to Turing machines and the variants, such as multiple tapes and nondeterministic Turing machines.
4) Decidability - the definition of decidability and how Turing machines and finite automata are used to prove or disprove if a language is decidable.
5) Reducibility - the definition of reducible and how Turing machines can be used to execute reductions.
6) The recursion theorem - an introduction to the recursion theorem and some applications to formal theories.
7) Time complexity - the first chapter in the coverage of algorithmic complexity, in this case execution time.
8) Space complexity - an examination of the complexity of algorithms from the perspective of the amount of memory required.
9) Intractability - an examination of the problems that can be solved in principle but not in practice.
10) Advanced topics in complexity theory - approximation algorithms, probabilistic algorithms, alternation, interactive proof systems, parallel computation and cryptography.
There is less coverage of grammars than most books, which is replaced by more in the area of algorithmic analysis. In my opinion, that is an appropriate tradeoff, the analysis of algorithms gives the students some understanding of how automata are applied in computer science.
Another excellent feature of this book is the solutions to selected exercises that appear at the end of the chapters. My estimate is that reasonably detailed solutions to approximately one-third of the problems are included. This allows the students to work extra problems by themselves, and helps the instructor if they are asked to do another example in class that they have not already worked through.
The exposition is very good; I am convinced that the students will be able to read the material on their own, which is one more reason why I adopted this book for my course.
well-organized, progressive, and understandable.......2007-01-06
As an intro to the theoretical background to computer science goes, this book is about as readable and approachable as you can get.
It gives a very thorough treatment of the whole theoretical basis, from regular languages and pumping lemmas out through Turing machines and related issues, and on to some interesting language classes (like NP and PSpace-complete).
If there's a single sticking point with the book, it's that it insists on a very strict formalism (ie: everything is proof-based) -- something necessary for the topic, but it sometimes renders the material a bit hard to digest.
Great book on the subject.......2006-12-27
If you are interested in or for other reasons must read a book on this subject, this is the book. I took a class last semester which used Hopcroft as the text and I found myself often turning to this book for better understanding. This book is more intuitive and thus a bit less formal than Hopcroft but when trying to learn, understanding is better than mathematical formalism. If you are new to the subject, Sipser is the book to begin with.
Very readable, diverse, and a little sparse.......2006-11-25
This is a wonderful little gem of a book that presents the theory of computation in a fascinating way. It is targeted at advanced undergraduates in computer science, but assumes remarkably little prior knowledge, making it accessible to nearly anyone. The book covers a lot of ground, including the standard fare of automata, computability, and complexity results, plus some bonus material such as probablistic and parallel complexity, information theory, decidable logical theories, and other topics that are normally left out of introductory books. On top of this, the book is remarkably thin!
The best attribute of Sipser's book, though, is the engaging style. This is an easy book to read. You will not feel like you're running into a brick wall, as is sometimes the case with books on abstract topics. It's not so much that the book is slow or gentle (it's really not) as that it is interesting, engaging, and has a knack for stopping short of getting too caught up in details. A number of small things -- the occasional amusing exercise, the "proof idea" sections, or helpful pictures -- add up to an enjoyable reading experience.
Two cautions are appropriate to students considering this book. First, there are variations between authors in the definitions of various automata (especially PDAs). The differences are trivial, and more a matter of taste than of any real importance; but it could come up if you use Sipser as a supplement to a course that follows a different textbook. Second, the coverage of many topics in Sipser's book is brief and concise, sometimes more than you might like. Some important concepts (for example, pairwise distinguishability of strings) are only mentioned in exercises, not in the main chapter, so at least skim all the exercises even if you don't do them. The sketchy coverage is especially pronounced in advanced topics, so (as always) expect to do some filling in of concepts if you go on into further study of this area.
Most appropriate for CS students.......2006-06-01
As a teacher of the subject, I have had the chance to evaluate numerous books on the theory of computation. Of all the available texts, I think this one is the most appropriate for CS students. In the past I taught out of Dexter Kozen's book, which is incredibly elegant, but had some resistance from the students. Thinking it over I decided that Kozen's text, although beautiful, may be better suited to students pursuing a degree in pure math. Sipser's book, on the other hand, is more gentle. I find that Sipser demands far less mathematical maturity from his readers, and thus allows the difficulty to be shifted from excessive formalism to the inherent challenges present in the material. In addition, following Sipser's treatment, I was able to cover finite state machines and pushdown automata in far less time, thus allowing me to concentrate on computability and beyond. The book really shines in its treatment of computability theory, eloquently directing attention to some of the most beautiful aspects.
Another benefit of Sipser's book is the exercises, of which there are many more in this edition. Someone studying on their own should find the initial group of exercises in each section quite approachable. Even the more challenging problems are not incredibly hard, and typically draw their difficulty from the deeper themes of the chapter instead of obscure details.
If you are looking for an enjoyable, well-paced book with an introduction to computability and complexity that is truly inspiring, this is the one for you. A mathematician looking for a bit more rigor may do better with Kozen.
Average customer rating:
- A Butchered Classic
- Updated Classic Text
- Good, but just it
- Automata theory. The heart of Computer Science
- Eh... Whatever...
|
Introduction to Automata Theory, Languages, and Computation (3rd Edition)
John E. Hopcroft ,
Rajeev Motwani , and
Jeffrey D. Ullman
Manufacturer: Addison Wesley
ProductGroup: Book
Binding: Hardcover
 Logic
| Pure Mathematics
| Mathematics
| Science
| Subjects
| Books
Logic
| Pure Mathematics
| Mathematics
| Professional Science
| Professional & Technical
| Subjects
| Books
General
| Computers & Internet
| Subjects
| Books
Look Inside Science Books
| Trip
| Specialty Stores
| Books
All Titles
| Qualifying Textbooks - Fall 2007
| Stores
| Books
Computers & Internet
| Qualifying Textbooks - Fall 2007
| Stores
| Books
Professional
| Qualifying Textbooks - Fall 2007
| Stores
| Books
Science
| Qualifying Textbooks - Fall 2007
| Stores
| Books
ASIN: 0321462254 |
Amazon.com
This book is a rigorous exposition of formal languages and models of computation, with an introduction to computational complexity. The authors present the theory in a concise and straightforward manner, with an eye out for the practical applications. Exercises at the end of each chapter, including some that have been solved, help readers confirm and enhance their understanding of the material. This book is appropriate for upper-level computer science undergraduates who are comfortable with mathematical arguments.
Book Description
This classic book on formal languages, automata theory, and computational complexity has been updated to present theoretical concepts in a concise and straightforward manner with the increase of hands-on, practical applications. This new edition comes with Gradiance, an online assessment tool developed for computer science.
Gradiance is the most advanced online assessment tool developed for the computer science discipline. With its innovative underlying technology, Gradiance turns basic homework assignments and programming labs into an interactive learning experience for students. By using a series of “root questions” and hints, it not only tests a student’s capability, but actually simulates a one-on-one teacher-student tutorial that allows for the student to more easily learn the material. Through the programming labs, instructors are capable of testing, tracking, and honing their students’ skills, both in terms of syntax and semantics, with an unprecedented level of assessment never before offered.
Customer Reviews:
A Butchered Classic.......2007-09-28
I've heard that the first edition of this book is a classic. Reading the second edition, I can kind of see that -- occasionally there will be a stretch of 5 pages or so that is wonderfully clear, concise, and informative.
But overall, this edition is a disappointment. The explanations tend to be mechanical and unhelpful, and are sometimes confused or just incorrect. New sections on mathematical foundations and applications have been added, but there isn't really adequate space devoted to covering either topic, and the results are so rushed and lacking in context that I can't see those sections being useful to anyone who would need them in the first place. Finally, this edition needs to be proofread for correctness! It contains numerous mistakes, some of them in the presentations of key proofs.
Updated Classic Text.......2007-08-29
The previous edition of this text was published in the late 70's (1979), and it was still in use today in many schools and Universities across the world. For good reason too, the authors of this text really nail down the concept of computability as we understand it today. It is very difficult to find an undergraduate curriculum that does not include a course in Computability or theory of computation, and that is certainly a change from a couple of decades ago where this type of study was left to the Graduate level curricula. What this means to the reader is that one can not be a Computer Scientist without understanding the concepts and theory behind what computability really means.
Things like Context Free languages and grammar are used readily in things like XML and its accompanying standards such as the DTD. So, it makes sense to update a classic text to include such topics and further illustrate to the reader that what once was a theory is now center stage of Computer Science and the IT industry as a whole.
The text starts with the classics such as an introduction to automata theory followed by languages. The authors have taken a more relaxed approach to the topics as the proofs are less formal and easier to follow. Plain text is usually used to informally proof the topic at hand, and the authors go into a more formal approach on selected proofs. This is definitely a better approach than the other texts in the same topic that proofs are center stage of the discussion and the reader gets lost early on in the process. The text is easy to read for students, and easy to explain for the instructors. I remember when I took theory of Computation for my graduate work proofs were so convoluted and difficult to read that I had to spend many of nights trying to understand what the instructor was talking about in the class.
As one would expect, the book then goes into Turning Theory and Machine with the concept to computability and complexity. Well, the good news is that the authors' approach to the topic does not change; lots of explaining of the basics followed by a more detailed formal approach to the topic. All I need to say is that I wish my text was this reader friendly! Chapter 8, Introduction to Turing Machines, sets the ground work for the rest of the text. It explains reducibility and more importantly how to reduce a problem, something I have never seen in any other text in such detail! Automata and its relation to Turing Machine is depicted in detail, so there is no gap between the topics. What is interesting is that the authors close the loop with actually talking about, for example the Halting problem, in the real world with a program.
As one would expect, different classes of problems are explored in detail with many examples (theory and real-world examples) that accompany the topic at hand. Each chapter ends with a summary of topics discussed followed by a set of exercises. There are also a number of exercises at the end of each section in a given chapter in order to reel-in the topic for the reader.
All and all, this is one great text on automata and computation theory. It is easy to read and follow for the students without the loss of content. The authors relate abstract concepts to real-world examples to further illustrate the importance of the topic at hand.
Good, but just it.......2007-06-27
A good book, but just it.
It's like a normal book. It's not bad but not excellent...
Automata theory. The heart of Computer Science.......2007-04-06
Excellent book. Nothing to say for this one.
Eh... Whatever..........2007-01-21
Uhm... I had to buy this book because it was a required text for a required course. Who would buy a book like this otherwise? Duh!
Average customer rating:
- No Ackermann function
- Needlessly cryptic; too clever for its own good
- Great math, bad writing.
- Content left as an exercise
- A good textbook
|
Elements of the Theory of Computation (2nd Edition)
Harry R. Lewis , and
Christos H. Papadimitriou
Manufacturer: Prentice Hall
ProductGroup: Book
Binding: Paperback
General
| Algorithms
| Programming
| Computers & Internet
| Subjects
| Books
Computer Mathematics
| Artificial Intelligence
| Computer Science
| Computers & Internet
| Subjects
| Books
General
| Computers & Internet
| Subjects
| Books
Discrete Mathematics
| Pure Mathematics
| Mathematics
| Science
| Subjects
| Books
Logic
| Pure Mathematics
| Mathematics
| Science
| Subjects
| Books
General
| Mathematics
| Science
| Subjects
| Books
Probability & Statistics
| Applied
| Mathematics
| Science
| Subjects
| Books
Discrete Mathematics
| Pure Mathematics
| Mathematics
| Professional Science
| Professional & Technical
| Subjects
| Books
Logic
| Pure Mathematics
| Mathematics
| Professional Science
| Professional & Technical
| Subjects
| Books
General
| Computer Science & Information Systems
| New & Used Textbooks
| Stores
| Books
General
| Mathematics
| Sciences
| New & Used Textbooks
| Stores
| Books
All Titles
| Qualifying Textbooks - Fall 2007
| Stores
| Books
Computers & Internet
| Qualifying Textbooks - Fall 2007
| Stores
| Books
Professional
| Qualifying Textbooks - Fall 2007
| Stores
| Books
Science
| Qualifying Textbooks - Fall 2007
| Stores
| Books
Similar Items:
-
Computational Complexity
-
JFLAP: An Interactive Formal Languages and Automata Package
-
Introduction to Automata Theory, Languages, and Computation (2nd Edition)
-
Introduction to the Theory of Computation
-
Operating System Concepts with C & C++
ASIN: 0132624788 |
Book 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.
Customer Reviews:
No Ackermann function.......2007-10-01
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.......2007-06-30
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........2007-06-10
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..
Content left as an exercise.......2005-06-08
I had the "pleasure" of being exposed to this nightmare of a book in a bachelor level course. I am told that it is normal to use this book on masters-degree level, so maybe it's because I wasn't "prepared" enough for this book that my take on it is so negative. The book does have it's moments, where things are understandable, but thats mainly if the stuff is easy. There is a lack of explenations throughout the entire book. It seems the author(s) view of "explenation" is the words "it is easy to see..." or "left as an exercise"....The proof of my feelings toward this book, can be seen on the teeth-marks that decorate the books cover. Im not writing this, because I need to vent steam...I passed the course on the first try, and it is now behind me, but I advice anyone faced with this book, to seek alternatives..this book is not a teaching book, it is a telling book.
The best way to describe the book, is if you imagine a book, that on page 2 reads "content left as an exercise"...and then its blank for the rest.
A good textbook.......2005-04-25
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.
Amazon.com
This book comprehensively discusses the neural network models from a statistical mechanics perspective. It starts with one of the most influential developments in the theory of neural networks: Hopfield's analysis of networks with symmetric connections using the spin system approach and using the notion of an energy function from physics. Introduction to the Theory of Neural Computation uses these powerful tools to analyze neural networks as associative memory stores and solvers of optimization problems. A detailed analysis of multi-layer networks and recurrent networks follow. The book ends with chapters on unsupervised learning and a formal treatment of the relationship between statistical mechanics and neural networks. Little information is provided about applications and implementations, and the treatment of the material reflects the background of the authors as physicists. However the book is essential for a solid understanding of the computational potential of neural networks. Introduction to the Theory of Neural Computation assumes that the reader is familiar with undergraduate level mathematics, but does not have any background in physics. All of the necessary tools are introduced in the book.
Customer Reviews:
Clear and logical exposition.......2007-08-18
It's not the latest book on this topic, so today, there are other texts that have more recent developments to be sure. I originally read this text about 15 years ago. But what I got from this book, that I didn't get from most, are important insights and clear understanding of the material that's covered. The authors have a deep understanding, and have teaching as their goal in writing. Most other texts in this area are lacking in one or both of those characteristics, and aren't worth the paper they are printed on.
Introduction to the Theory of Neural Computation.......2000-10-06
This book is written from a mathematical perspective. The book introduces the Hopfield Neural Network with history and applications. The authors solve the network problem and develop the Hebb Rule. Links are made to Ising Spin models and stochastic problems. I find this book to be one of the best written mathematical guides for Neural Networks.
A Broad Survey.......1997-11-08
This was a good survey, and well-grounded mathematically. It is kind of scattershot, and if you primarily want to do practical projects like predicting financial markets, a lot of the sections won't be relevant. But if you want a broad-based approach, emphasizing a variety of network designs fro different purposes, this book is very good.
Book Description
"The book is outstanding and admirable in many respects. ... is necessary reading for all kinds of readers from undergraduate students to top authorities in the field." Journal of Symbolic Logic Written by two experts in the field, this is the only comprehensive and unified treatment of the central ideas and their applications of Kolmogorov complexity. the book presents a thorough treatment of the subject with a wide range of illsutrative applications. Such applications include the randomeness of finite objects or infinite sequences, Martin-Loef tests for randomness, information theory, computationla learning theory, the complexity of algorithms, and the thermodynamics of computing. It will be ideal for advanced undergraduate students, graduate students, and researchers in computer science, mathematics, cognitive sciences, philosophy, artificial intelligence, statistics, and physics. the book is self-contained in that it contains the basic requirements from mathematics and computer science. Included are also numerous problem sets, comments, source references, and himnts to solutions of problems. In this new edition the authors have added new material on circuit theory, distributed algorithms, data compression, and other topics.
Customer Reviews:
Biggest return for the biggest investment.......2005-05-08
This was the second-hardest book I ever read. Honestly, it took me years and years to get through it. I even had to buy a 2nd copy, because I kept getting frustrated and throwing the first copy across the room until it was destroyed. So yes, this book requires a substantial effort to read.
But the payback!! I've gotten more return on investment from this book than from any other book I've ever read. If you dilligently read and master this book, you will be able to analyze and solve problems your collegues just can't.
The basic idea behind Kolmogorov complexity is straighforward: a good measure of the complexity of an object is the length of the shortest computer program which will construct that object. From this basic idea an amazing variety of insights and powerful techniques have been developed, and this book is quite comprehensive in cataloging and explaining them.
For computer scientists and working programmers, probably the most useful result of Kolmogorov complexity would be the "Incompressibility Method", which is a powerful technique for the analysis of the runtime of algorithms. Typically, it is relatively easy to figure out what the best case or the worst case runtime of an algorithm is. Until now, it was hard to calculate the average runtime of an algorithm, because it usually involved a tricky counting problem, to enumerate all possible runs of the the algorithm and summing over them. The incompressibility method eliminates the need for doing these complicated enumerations, by letting you perform the analysis on a single run of the algorithm which is guarunteed to be representative of the average runtime of the algorithm. If you program for a living like I do, this will give you an edge, because if you can accurately predict that the worst-case runtimes almost never happen, you can usually simplify and streamline your programs by optimizing it for the average case. If your competitors are wasting time optimizing for a worst case which almost never happens--at the expense of _not_ optimizing for the average case, you win bigtime.
For philosophers of science and AI/knowledge representation folks, the most useful results of Kolmogorov complexity are probably the contributions of Kolmogorov complexity to Baysianism. To be a Baysian is to follow a two step process: (STEP 1) for every possible sentence, assign to it a number between 0 and 1 which represents how certain you are that that sentence is true. This initial assignment should be a probability distribution over all possible sentences. It should be a "good" probability distrubution, but of course it won't be perfect, since you don't know everything. (STEP 2) when confronted with new evidence, e.g. an observation, update your current "good" degrees of belief by using Bayes' law, to yield a new "better" set of degrees of belief.
The Baysians always had a good story for Step 2--just use Bayes law. But until now, they were mostly hand-waving on Step 1--what would constitude a "good" initial probability distribution? There were many proposals (e.g. maximum entropy) but all proposals had benefits and drawbacks. What Kolmogorov complexity provides is the so-called "universal" distribution, which is guarunteed to be a "good" initial distirbution. This book devotes much time to explaining and exploring this, and shows how previous techniques, like maximum entropy, minimum description length, etc all can be seen as computable approximations to the (unfortunately uncomputable) universal distribution. This really gives a nice framework for evalutating and formulating good prior distributions.
After remarking on how hard this book was to read, I should emphasize that this is not due to bad writing on the part of the authors! Indeed, after throwing the book across the room, I was always drawn back by Li & Vitanyi's most engaging writing style to pick the book back up, dust it off, and have another go at it. If it were not for their wonderul ability to expain a very complicated subject matter, I never would have gotten through it.
An unsung hero of this book is Peter Gacs, who wrote a set of lecture notes which really could be considered to be an Urtext for this book. If you tackle this book, I highly recommend that you also get ahold of these notes, because it is sometimes very useful, when trying to puzzle out a difficult argument, to get another description/explaination of it from a different point of view. These notes are available on the web, just google for "Lecture note on descriptional complexity and randomness" by Peter Gacs.
If you're up to the challange, then buy this book, dilligently read it, swear at it--then swear by it.
A must.......2003-10-29
The book provides all the tools needed for a productive use of the theory. Written by leading experts in the field, the book is both a fascinating introduction as well as a comprehensive reference for experts.
The authors are careful to place the development of the theory in its historical context, give a face to the main players in the field and explore frictions with other lines of thought. But the main storyline is the mathematical world of Kolmogorov complexity. Neccessary background knowledge is provided, most proofs are given and the open problems are presented. Most chapters are more or less self sufficient, making it possible to skip those that are of less relevance to you. In the later chapters much thought is given to the different fields of application.
A third edition is in the making which will include recent advances. But since the authors make new discoveries available on the web, the present edition will continue for a long time to hold a prominent place in the book shelves of many computer scientist.
Excellent if you have the math..........2002-08-13
to understand it. This book is intended for serious students of computer science or those who have some similar training - it is definitely set up as a textbook. However, that being said, if you have the background the authors' delivery is fist-class and very clear.
The reviews below give more than enough information so I won't belabour the Kolmogorov complexity here. Suffice it to say you won't find the subject detailed more fully in any other reference work in existence today.
However, this book does need to be revised and updated. There has been a lot of development in the field and the sections overviewing Solomonoff's work, in particular, could be expanded. Also, I found it hard to believe that nothing about the 'philosophical' importance of the whole induction question - this is at the core of many very important questions and should not be treated trivially.
There should also be some overview of two other areas that, in combination with the theory outlined in this text, are starting to form the nexus of a "new kind of science" (definitely not Wolfram's pathetic attempt). I refer to some information regarding non-classical logical systems as well as anticipatory computing systems. Both will, I predict, become core areas in addition to extensions to Kolmogorov/Chaitin complexity in the future.
All textbooks should be as clear and concise as this example.
The only one of its kind...........2001-09-23
The theory of Kolmogorov complexity attempts to define randomness in terms of the complexity of the program used to compute it. The authors give an excellent overview of this theory, and even discuss some of its philosophical ramifications, but they are always careful to distinguish between mathematical rigor and philosophical speculation. And, interestingly, the authors choose to discuss information theory in physics and the somewhat radical idea of reversible computation. The theory of Kolmogorov complexity is slowly making its way into applications, these being coding theory and computational intelligence, and network performance optimization, and this book serves as a fine reference for those readers interested in these applications. Some of the main points of the book I found interesting include: 1. A very condensed but effective discussion of Turing machines and effective computability. 2. The historical motivation for defining randomness and its defintiion using Kolmogorov complexity. 3. The discussion of coding theory and its relation to information theory. The Shannon-Fano code is discussed, along with prefix codes, Kraft's inequality, the noiseless coding theorem, and universal codes for infinite source word sets. 4. The treatment of algorithmic complexity. The authors stress that the information content of an object must be intrinsic and independent of the means of description. 5. The discussion of the explicit universal randomness test. 6. The discussion (in an exercise) of whether a probabilistic machine can perform a task that is impossible on a deterministic machine. 7. The notion of incompressibility of strings. 8. The discussion of randomness in the Diophantine equations; it is shown that the set of indices of the Diophantine equations with infinitely many different solutions is not recursively enumerable; with the initial segment of length n in the characteristic sequence having Kolmogorov complexity n. 9. The discussion on algorithmic probability, especially the test for randomness by martingales. 10. The Solomonoff theory of prediction and its ability to solve the problem of induction. 11. The treatment of Pac-learning and the resultant formalization of Occam's razor. 12. The discussion of compact routing; the optimal space to represent routing schemes in communication networks on the average for all static networks. 13. Computational complexity and its connection to resource-bounded complexity. 14. The notion of logical depth, i.e. the time required by a universal computer to compute the object from its compressed original description. 15. The connection between algorithmic complexity and Shannon's entropy. 16. The discussion on reversible computation, i.e. logically reversible computers that do not dissipate heat. 17. The treatment of information distance, i.e. for two strings, the minimal quantity of information sufficient to translate from one to the other.
Comprehensive and Excellent.......1999-07-31
This is one of the best-written mathematical texts I've read. It builds up the theory from basic principles, and illustrates it with numerous examples and applications. A definitive work.
Book Description
This introductory text covers the key areas of computer science, including recursive function theory, formal languages, and automata. It assumes a minimal background in formal mathematics. The book is divided into five parts: Computability, Grammars and Automata, Logic, Complexity, and Unsolvability.
* Computability theory is introduced in a manner that makes maximum use of previous programming experience, including a "universal" program that takes up less than a page.
* The number of exercises included has more than tripled.
* Automata theory, computational logic, and complexity theory are presented in a flexible manner, and can be covered in a variety of different arrangements.
Customer Reviews:
Pure mathematical view of Computability and Complexity.......2002-02-14
This is not a common book on Computability and Complexity as Hopcroft-Ullman, Sipser or Papadimitrou. You won't find here too many words describing topics: you'll find the power and elegance of a superlative mathematical approach from one the best authors of the century in the field. Conversely, you'll find here a detailed and elegant treatment of the whole history of computational models that starts at the Primitive Recursive Functions, something you won't find in the other books above mentioned.
A special note goes to the chapter on Blum's complexity, which is about the only good place where I found it and from where I studied for my course on Complexity I.
For this reason the book requires quite more attention than others, but it really worths all the time one can spend reading it. Truly understanding Computability and Complexity as Professor Davis teaches them with this book is in my opinion a definitely high achievement, bringing the sensation that you grasp it totally, with no space for ambiguity or weakness.
Beautiful overview.......2001-07-11
The authors of this book define theoretical computer science as the mathematical study of models of computation, and they do an excellent job of detailing the major results in the theory of computation as related to mathematical logic. Mathematicians, programmers, and philosophers will find the book an effective one in which to learn computability theory, and it serves well as a textbook for courses in the subject.
After a brief review of elementary mathematics and mathematical logic in chapter 1, the authors move right into the consideration of computable functions in chapter 2. They choose a particular abstract programming language in which to study the computability theory, which is built from variables, and programs that can be built from lists of instructions. Examples of programs are given, which have a Fortran flavor, with examples of computing partial functions. Unfortunately, a plethora of GOTO statements appear in the programs, and throughout the rest of the book, which is surprising given the publishing date. The use of these GOTO statements in the book is a major annoyance.
Then in chapter 3, the authors discuss primitive recursive functions, beginning with a treatment of composition, followed by the all-important concept of recursion. The class (PRC) of primitive recursive functions is introduced, and shown to be computable. The primitive recursive predicates are introduced, followed by a proof that the existential and universal quantifiers over an element of a PRC class are also PRC. This is followed by a discussion of minimalization and Godel numbers.
The next chapter is very interesting, wherein the famous halting problem is discussed and related to Church's thesis. The authors stress, most importantly, that an algorithm cannot be defined outside of the choice of a language, and therefore Church's thesis cannot be proved as a theorem. The authors also introduce recursively enumerable sets and show, via diagonalization, that non-recursively enumerable sets exist. They give an interesting example of a function that is computable but not primitive recursive.
The next chapter extends the results to strings of symbols instead of just numbers, and the authors introduce programming languages for doing string computations. One of these is the famous Post-Turing language, which they use to discuss the halting problem, with a variant used in the next chapter on Turing machines. The authors discuss the famous halting problem for Turing machines in this chapter. This is followed in chapter 7 by a discussion of productions and simulation of nondeterministic Turing machines. A very lucid treatment of Post's correspondence problem is given.
Things get somewhat more complicated in chapter 8, where the authors attempt to classify unsolvable problems. It contains one of the best discussions I have seen in the literature on oracles, and the authors give a very clear treatment of arithmetic hierarchies.
The second part of the book reads more like a book on compilers, as the authors delve into the area of grammars and automata. Regular languages, deterministic and non-deterministic finite automata are discussed, and Kleene's theorem, which states that regular languages and finite automata define the same languages, is proven. The context-free languages, so familiar from the study of compilers, are discussed also, along with a proof that a context-free grammar can be reduced to a Chomsky normal form grammar. Pushdown automata, needed for accepting context-free languages, are treated in detail. The authors give a good explanation here as to the additional facilities needed for a finite automaton to decide if a word belongs to a "bracket" language. Chomsky hierarchies are also discussed, and the authors motivate nicely the need for a linear bounded automaton to accept context sensitive languages.
Part three of the book is an overview of mathematical logic, and begins with a treatment of the propositional calculus. The satisfiability problem is discussed for this system, along with how to reduce formulas to normal form. The important compactness theorem is given a very detailed proof. Predicate calculus is then discussed, and Herbrand's theorem, which effectively reduces logical inference in predicate calculus to a problem of satisfiability of universal sentences, is proven. This theorem is fascinating and has important applications to automated theorem proving, as it ties together semantic and syntactical properties of a formal system. The Godel incompleteness theorem and the unsolvability of the satisfiability problem in predicate logic is proven.
In part 4, issues in computational complexity are addressed, the measure of complexity given in terms of the Blum axioms. This is a very abstract way of introducing complexity theory, as it introduces measures of complexity that more general than time and space complexity. The fascinating gap theorem, comparing program performance on two computing machines via complexity measures, is proven. This is followed by a detailed discussion of the speedup theorem, which essentially states that there is a wildly complicated recursive function such that for any program computing this function, there exists another program computing the function that works a lot faster for almost every input. The polynomial-time computability is discussed along with the famous P vs NP problem, with the discussion given in terms of Turing machines. Examples of NP-complete problems are given.
The last part of the book covers semantics, with operational and denotational semantics defined and compared. The emphasis in this part is on programming languages and constructions that one would actually find in practice, and so the preceding chapters on computable functions must be extended. The concept of an approximate ordering is introduced to allow for the instantaneous of a computation at some point before its completion. The denotational semantics of recursion equations and infinitary data structures are discussed, with the latter put it in to deal with the sophisticated systems that are constructed here. The discussion here is very involved, but the authors do a fair job of explaining the need for these types of data structures. The same is done for operational semantics, and the authors finally show that the computable numerical functions are actually partially computable. They then show the existence of computable irrational numbers.
My favorite book on the theory of computation.......2000-05-11
I first learned computability from this book and I loved every minute of it. It has lots of material and is superbly written. In fact, I think the chapters on logic are the most painless way to learn that subject. There are many other books around on this subject, but this is the ultimate!
CS Theory at it's best.......2000-03-30
I haven't found a better book on the Theoretical foundations of Computer Science. However since this IS theory the text can be a bit cryptic. Still, I'd recomend this book to any PhD Candidate or full Professor. Even a lowly Master's student like myself could use it.
This is a wonderful text about the theory of computation........1999-02-25
It taught me how to think about the theory of computation. The exercises added to the second edition are a big improvement over the first editon.
Customer Reviews:
Complete Scam.......2007-02-18
Papadimitriou's book is a classic, but many of my students find it difficult. This book is clearly not written by Papadimitriou. When I saw this book (Cram101) I didn't know what to expect, but hoped for some sort of easy presentation of similar material. This book has nothing to do with Papadimitriou's Computational Complexity. Half the pages are intentionally blank. The other half have definitions of terms (most repeated over and over) that have nothing or virtually nothing to do with the topic. For example "mean" is defined (poorly) 17 times and "sets" is defined (poorly) 12 times.
The book is simply not useful.......2006-02-06
If your purpose is to learn something. This book is really bad at teaching you.
The author assumes many things. He has no idea of building things in a gradient. He leaves out the details of how something was arrived at.
If his purpose is to show off, then he has achieved. If his purpose is to create a text that is readable and understandable. He has failed.
Good overall........2004-02-06
A well-written book that teaches you how to think about complexity theory instead of just a flat summary of results. Something like Lewis and Papadimitriou's _Elements of the Theory of Computation_ would be more than enough preparation for this (note that the style of these books is quite different- this one is more informal and descriptive). Covers all the material you need in a first text. Has a good little introduction to mathematical logic in it, including a nice succinct version of Godels Incompleteness Theorem. Lots of interesting exercises.
All in one roof, but presentation very poor.......2003-06-03
I agree with the review by Arthur Fischer. Papadimitriou might
be an excellent researcher, but his communication skills are
hopeless and horrible. The typos make learning even harder.
Perhaps someone like Michael Sipser should take up the task of
rewriting this book.
It is hard to catch some ideas, but it is worth reading.......2003-06-02
Yes,it is generally "hard" for undergradute students even grad. students. If you are taking course "Theory of computation", I would like to recommend the Sipser's or Cohen's books for reading supplement. But you should keep reading this book ! IMO, this book covers so many topics, that it becomes too dense to read. It means you should read it carefully and slowly. For example, it introduces the "reduction" in some previous chapters but without precise defintion and therefore misses the more important part :how to do the reduction correctly and what is the "reseasonable" reduction ? You will find the concept of "reduction" is not very easy to catch if you refer to the Sipser's or Ullman's books. Many friends and me could not go through more than 20 pages of this book in the beginning. But we were keeping on reading and surveying some "easy books". Finally, we understood most half parts of this book. Moreover, if some readers prepare to study more advanced and recent topics, this book is the must.
Amazon.com
This book's introduction features a humorous story of a man with a line of people behind him, who explains to his boss, "I can't find an efficient algorithm, but neither can all these famous people." This man illustrates an important quality of a class of problems, namely, the NP-complete problems: if you can prove that a problem is in this class, then it has no known polynomial-time solution that is guaranteed to work in general. This quality implies that the problem is difficult to deal with in practice.
The focus of this book is to teach the reader how to identify, deal with, and understand the essence of NP-complete problems; Computers and Intractability does all of those things effectively. In a readable yet mathematically rigorous manner, the book covers topics such as how to prove that a given problem is NP-complete and how to cope with NP-complete problems. (There is even a chapter on advanced topics, with numerous references.) Computers and Intractability also contains a list of more than 300 problems--most of which are known to be NP-complete--with comments and references.
Customer Reviews:
comprehensive book for NP-completeness.......2007-09-21
The book is excellent in explaining NP-completeness problem. Take it as a reference if you would like to do research in this field.
Published in 1979 and still the best.......2007-06-16
This is a rare example of a textbook where the authors actually go to the trouble of considering the fact that the intended reader is a non-expert. Published in 1979 and still the best.
Arrived in time, good condition.......2006-02-24
The book arrived in time, in good condition, and adequate packing.
A Beautiful Book on a Beautiful Subject.......2005-12-11
This is among the most eloquently written books that I have ever read in my life. Highly recommended.
This is the Bible for NP-Complete research.......2005-10-07
I most like the fact that a good number of problems reduced to NP-Complete or NP-Hard are listed. I would like someday to see a compiled list of the reductions involved included in one text, but it's not likely that I ever will. It would be nice to see an updated version, but this describes the theory very, very nicely.
This is a must have for any serious computer scientist.
Amazon.com
Languages and Machines is a user-friendly text that covers the key ideas of the theory of computation clearly and thoroughly. Examples and numerous diagrams, including diagrams that illustrate the principle of induction, aid in the understanding of the material. Relative to other books containing similar information, this text contains in-depth coverage of languages and parsing.
Book Description
The third edition of Languages and Machines: An Introduction to the Theory of Computer Science provides readers with a mathematically sound presentation of the theory of computer science. The theoretical concepts and associated mathematics are made accessible by a "learn as you go" approach that develops an intuitive understanding of the concepts through numerous examples and illustrations.
Customer Reviews:
No Examples , No Answers, No Hints.......2006-11-20
Besides the fact that the book is "dry", in which most Math theory based books are, the examples are just the basis step towards solving a problem. I equate it to teaching a child how to add, and just giving them the example "1 + 0", then assume they can figure out the rest. There are no answers, either in the back of the book for particular exercies, nor was a study guide made available. What is really shocking is that it's the most expensive book out there! Not to mention that there isn't any programming steps made available. Great text for a Math major ... horrible textbook for Computer Science Majors, mainly because computer science majors would want to see programming examples and may not be as strongly math oriented as a Math major would be.
A Good Book for a Tough Subject.......2006-02-15
Abstract language theory is hard, but Languages and Machines does a very good job of explaining the subject step by step. The topics are covered extremely thoroughly and with just the right amount of rigor. As for those who claim it's not exciting enough, you can't get blood out of a stone. Only the most dedicated computer scientist and mathematicians will find this topic interesting. Even so, this book does a superb job of tying theory to application (e.g., the machines one can use language theory to build) for even the most obscure concepts (like the Greibach Normal Form).
That being said, there are a few problems. First, the author's claim that this is a book for undergrads is not credible (except perhaps at MIT or CalTech). Even my graduate students have to read sections multiple times to "get it". Second, the author needs to provide solutions to selected problems at the back of the textbook. Most theory books do this, but not this one. This is a major weakness, especially given the difficulty of the material. Lastly, Sudkamp's proofs are extremely dry and very difficult to follow. He should take a cue from Sipser's excellent book (Intro to Theory of Computation) and introduce "proof ideas" to give the big picture for important proofs.
emphasises the Turing machine.......2005-09-29
[A review of the 3RD EDITION, 2005.]
Sudkamp gives a formal and rigorous explanation of what constitutes a language. Where this is deliberately taken to include both natural (spoken) languages and programming languages. To do this, you should note that the treatment is necessarily non-trivial. It is not a lightweight book, conceptually.
The book summarises decades of work in this field, that have attempted to reduce human languages to a form that could be "understood" by a machine. So he explains the various techniques that have arisen. Like finite state machines (finite automata).
Notably, he discusses what is a Turing machine. A universal computing engine, that all other computers can map to. Such a Turing machine might be deterministic or non-deterministic. You can learn very powerful unifying ideas.
From the construct of a Turing machine, the book uses this to delve into problems that are NP complete or P complete. The implementation of a solution as steps to be done by a Turing machine are elegant, and show how such a machine, while an idealisation, can be used to give provable results.
horrified.......2005-09-22
The book is incredibly boring. If you're condemned to read it (say, it's required reading for your qualifiers), I strongly recommend that you find a group of people to study w/ and pool your resources to only buy a single copy. The lack of answers at the back of the book makes self study difficult, and groupwork might be the only way to stay awake.
I wish to God I could think of another book to recommend over this one. I imagine any will do.
Taught by the author!.......2004-09-21
Hey,
I was fortunate enough to learn this course from the author of the book. The book by itself might seem tough. The fault lies in the fact that subject matter is not altogether too simple to understand without someone teaching it to you!
With the help of the instructor, we did learn a lot about formal languages, finite automaton, regular grammer, etc.
The key to understanding this material (and using this book effectively) is solving as many problems as possible, preferably in a group setting so that solutions can be discussed.
Note: For most problems, there exists multiple solutions, and the approach is what needs to be learned and discussed.
Recommended, with some reservations...Good luck!
Average customer rating:
|
Average-Case Complexity
Andrej Bogdanov , and
Luca Trevisan
Manufacturer: Now Publishers Inc
ProductGroup: Book
Binding: Paperback
General
| Algorithms
| Programming
| Computers & Internet
| Subjects
| Books
General
| Computers & Internet
| Subjects
| Books
All Titles
| Qualifying Textbooks - Fall 2007
| Stores
| Books
ASIN: 1933019492 |
Book Description
Average-Case Complexity is a thorough survey of the average-case complexity of problems in NP. The study of the average-case complexity of intractable problems began in the 1970s, motivated by two distinct applications: the developments of the foundations of cryptography and the search for methods to "cope" with the intractability of NP-hard problems. This survey looks at both, and generally examines the current state of knowledge on average-case complexity. Average-Case Complexity is intended for scholars and graduate students in the field of theoretical computer science. The reader will also discover a number of results, insights, and proof techniques whose usefulness goes beyond the study of average-case complexity.
Books:
- Just a Dream
- Kingdom Come: The Final Victory: The Final Victory (Left Behind #13)
- Last Place on Earth (National Geographic)
- Leroy Grannis: Surf Photography of the 1960s and 1970s
- Losing It All to Sprawl: How Progress Ate My Cracker Landscape (Florida History and Culture)
- Management Of Uncertainty: Learning From Chernobyl (INTERNATIONAL STUDIES IN GLOBAL CHANGE)
- Marine Conservation Biology: The Science of Maintaining the Sea's Biodiversity
- Marine Life of the Pacific Northwest: A Photographic Encyclopedia of Invertebrates, Seaweeds And Selected Fishes
- MCSE Self-Paced Training Kit (Exams 70-290, 70-291, 70-293, 70-294): Microsoft Windows Server 2003 Core Requirements, Second Edition
- Modern Roses: The World Encyclopedia of Roses
Books Index
Books Home
Recommended Books
- Murder in Foggy Bottom
- Goodnight Moon
- Cybernation
- Hartmann Schedel: Nuremberg Chronicle
- Film Posters of the Russian Avant-Garde
- History: Fiction or Science
- Fish! Tales: Real-Life Stories to Help You Transform Your Workplace and Your Life
- The Fertile Crescent, 1800-1914: A Documentary Economic History
- Cultural Advantage: A New Model for Succeeding With Global Teams
- Sir Hugh Rose and the Central India Campaign, 1858
Introduction to Algorithms
Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences)
Compilers: Principles, Techniques, and Tools (2nd Edition)
