Thuật toán Algorithms (Phần 2)

Tham khảo tài liệu thuật toán algorithms (phần 2), khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Thuật toán Algorithms (Phần 2) Introduction The objective of this book is to study a broad variety of important and useful algorithms: methods for solving problems which are suited forcomputer implementation. We’ll deal with many different areas of applica-tion, always trying to concentrate on “fundamental” algorithms which areimportant to know and interesting to stu.dy. Because of the large number ofareas and algorithms to be covered, we won’t have room to study many ofthe methods in great depth. However, we will try to spend enough time oneach algorithm to understand its essential characteristics and to respect itssubtleties. In short, our goal is to learn a large number of the most impor-tant algorithms used on computers today, well enough to be able to use andappreciate them. To learn an algorithm well, one must implement it. Accordingly, thebest strategy for understanding the programs presented in this book is toimplement and test them, experiment with variants, and try them out onreal problems. We will use the Pascal programming language to discuss andimplement most of the algorithms; since, however, we use a relatively smallsubset of the language, our programs are easily translatable to most modernprogramming languages. Readers of this book are expected to have at least a year’s experiencein programming in high- and low-level languages. Also, they should havesome familiarity with elementary algorithms on simple data structures suchas arrays, stacks, queues, and trees. (We’ll review some of this material butwithin the context of their use to solve particular problems.) Some elementaryacquaintance with machine organization and computer architecture is alsoassumed. A few of the applications areas that we’ll deal with will requireknowledge of elementary calculus. We’ll also be using some very basic materialinvolving linear algebra, geometry, and discrete mathematics, but previousknowledge of these topics is not necessary. INTRODUCTION This book is divided into forty chapters which are organized into sevenmajor parts. The chapters are written so that they can be read independently,to as great extent as possible. Generally, the first chapter of each partgives the basic definitions and the “ground rules” for the chapters in thatpart; otherwise specific references make it clear when material from an earlierchapter is required.AlgorithmsWhen one writes a computer program, one is generally implementing a methodof solving a problem which has been previously devised. This method is oftenindependent of the particular computer to be used: it’s likely to be equallyappropriate for many computers. In any case, it is the method, not thecomputer program itself, which must be studied to learn how the problemis being attacked. The term algorithm is universally used in computer scienceto describe problem-solving methods suitable for implementation as computerprograms. Algorithms are the “stuff” of computer science: they are centralobjects of study in many, if not most, areas of the field. Most algorithms of interest involve complicated methods of organizingthe data involved in the computation. Objects created in this way are called data structures, and they are also central objects of study in computer science.Thus algorithms and data structures go hand in hand: in this book we willtake the view that data structures exist as the byproducts or endproducts ofalgorithms, and thus need to be studied in order to understand the algorithms.Simple algorithms can give rise to complicated data structures and, conversely,complicated algorithms can use simple data structures. When a very large computer program is to be developed, a great dealof effort must go into understanding and defining the problem to be solved,managing its complexity, and decomposing it into smaller subtasks which canbe easily implemented. It is often true that many of the algorithms requiredafter the decomposition are trivial to implement. However, in most casesthere are a few algorithms the choice of which is critical since most of thesystem resources will be spent running those algorithms. In this book, we will study a variety of fundamental algorithms basic to large programs in manyapplications areas. The sharing of programs in computer systems is becoming more wide-spread, so that while it is true that a serious computer user will use a largefraction of the algorithms in this book, he may need to implement only asomewhat smaller fraction of them. However, implementing simple versionsof basic algorithms helps us to understand them better and thus use advancedversions more effectively in the future. Also, mechanisms for sharing softwareon many computer systems often make it difficult to tailor stan ...