- اطلاعات کتاب
- زمینه: ساختمانهای داده و الگوریتمها
- تعداد بازدید از این کتاب: 1402 بار

انتشارات: Springer

اثر: Juraj Hromkovic

تعداد صفحه: 549

حجم: 4.7MB

توضیحات کتاب (خلاصه پیشگفتار):

Parts of the Preface to the First Edition:

Algorithmic design, especially for hard problems, is more essential for success in solving them than any standard improvement of current computer technologies. Because of this, the design of algorithms for solving hard problems is the core of current algorithmic research from the theoretical point of view as well as from the practical point of view. There are many general textbooks on algorithmics, and several specialized books devoted to particular approaches such as local search, randomization, approximation algorithms, or heuristics. But there is no textbook that focuses on the design of algorithms for hard computing tasks, and that systematically explains, combines, and compares the main possibilities for attacking hard algorithmic problems. As this topic is fundamental for computer science, this book tries to close this gap.

Another motivation, and probably the main reason for writing this book, is connected to education. The considered area has developed very dynamically in recent years and the research on this topic discovered several profound results, new concepts, and new methods. Some of the achieved contributions are so fundamental that one can speak about paradigms which should be included in the education of every computer science student. Unfortunately, this is very far from reality. This is because these paradigms are not sufficiently known in the computer science community, and so they are insufficiently communicated to students and practitioners. The main reason for this unpleasant situation is that simple explanations and transparent presentations of the new contributions of algorithmics and complexity theory, especially in the area of randomized and approximation algorithms, are missing on the level of textbooks for introductory courses. This is the typical situation when principal contributions, whose seeping into the folklore of the particular scientific discipline is only a question of time, are still not recognized as paradigms in the broad community, and even considered to be too hard and too special for basic courses by non-specialists in this area. Our aim is to try to speed up this transformation of paradigmatic research results into educational folklore.

This book should provide a "cheap ticket" to algorithmics for hard problems. Cheap does not mean that the matter presented in this introductory material is not precisely explained in detail and in its context, but that it is presented as transparently as possible, and formalized by using mathematics that is as simple as possible for this purpose.

Aachen, March 2001, Juraj Hromkovic

Parts of the Preface to the Second, Enlarged Edition:

The term algorithm is the central notion of computer science and algorithmics is one of the few fundamental kernels of theoretical computer science. Recent developments confirm this claim. Hardly any other area of theoretical computer science has been more lively and has achieved comparably deep progress and breakthroughs so fascinating (such as the PCP-theorem and efficient algorithms for primality testing) in recent years. The most exciting development happened exactly in the field of algorithmics for hard problems, which is the topic of this book.

The goal of this textbook is to give a transparent, systematic introduction to the concepts and to the methods for designing algorithms for hard problems. Simplicity is the main educational characteristic of this textbook. All ideas, concepts, algorithms, analyses, and proofs are first explained in an informal way in order to develop the right intuition, and then carefully specified in detail. Following this strategy we preferred to illustrate the algorithm design methods using the most transparent examples rather than to present the best, but too technical, results. The consequence is that there are sections where the first edition of this book does not go deep enough for advanced courses.

To smooth this drawback in the second edition, we extended the materials for some of the topics of central interest - randomized algorithms for primality testing and applications of linear programming in the design of approximation algorithms.

Aachen, October 2002, Juraj Hromkovic

توضیحات بیشتر:

Note that hard does not mean only NP-hard here; rather, any problem that does not admit any low-degree polynomial-time algorithm is considered to be hard.

The methods for the design of algorithms are not only presented in a systematic way, they are also combined, compared, and parallelized in order to produce a practical algorithm for the given application.

This book contains a fascinating topic that shows the importance of theoretical knowledge for solving practical problems. Several of you (comuter science sutdents) consider theory to be boring and irrelevant for computer scientists and too hard in comparison with courses in applied areas of computer science and engineering. Still worse, some of you may view the courses in theory only as a troublesome threshold that must be overcome in order to obtain some qualification certificates. This book tries to show that the opposite of this judgment is true, i.e., that the theory involves exciting ideas that have a direct, transparent connection with practice, and that they are understandable.

Moreover, we show in this book that several practical problems can be solved only due to some nontrivial theoretical results, and so that success in many applications strongly depends on the theoretical know-how of the algorithm designers. you will learn paradigms that, in contrast to specific technical knowledge (though useful now, but becomes outdated in a few years), may remain useful for several decades or even become the core of future progress.

Mathematics is used here as a formal language and as a tool, but not as a mysterious end in itself. We show here that a very simple formal language on a low level of mathematical abstraction is often sufficient to clearly formulate the main ideas and to prove useful assertions.

This book consists of three parts. The first part is presented in Chapter 2 and it contains elementary fundamentals of mathematics and algorithmics as usually taught in undergraduate courses. Chapters 3, 4, 5, and 6 are devoted to the proper subject of this textbook, i.e., to a systematic presentation of methods for the design of efficient algorithms for hard problems. The third part is covered in Chapter 7 and serves you as a guide in the field of applications of the methods presented in the second part.