Скачать Computers and Intractability (A Series of books in the mathematical sciences): Michael R. Garey, David S. Johnson бесплатно
26 июня 2009 | Автор: Admin | Рубрика: Компьютерная литература » Програм-ние и разработка » Программирование | Комментариев: 0
Computers and Intractability (A Series of books in the mathematical sciences): Michael R. Garey, David S. Johnson
W. H. Freeman and Co. Ltd | ISBN: 0716710447 | 1979-04 | djvu (ocr) | 338 pages | 3.07 Mb
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.
Summary: Definitely a classic but not good for beginners
I have to say that this is a true classic. It gives a very nice treatment of what is NP-completeness in a fashion that really defends the topic well. It gives nice illustrations to show different situations and how to deal with it. But after the first couple of chapters it does get a little out there with the proofs it does. It is still approachable, but it assumes that the reader is already familiar with the basics of combinatorial complexity, especially in reductions. I would only recommend this book to readers who has gone through such books as Introduction to Algorithms by Cormen et al. or Combinatorial Complexity by Papadimitriou and Steiglitz. Those two books are more for beginners and this book should be one to help anyone interested in NP-complete problems to get more practice and depth understanding. Overall a great book for anyone interested in the topic. The grand challenge is to reduce everything to at least something within the 150 problems listed on your own.
Summary: comprehensive book for NP-completeness
The book is excellent in explaining NP-completeness problem. Take it as a reference if you would like to do research in this field.
Summary: Published in 1979 and still the best
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.
Summary: Arrived in time, good condition
The book arrived in time, in good condition, and adequate packing.
Summary: A Beautiful Book on a Beautiful Subject
This is among the most eloquently written books that I have ever read in my life. Highly recommended.