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

Tham khảo tài liệu thuật toán algorithms (phần 1), 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 1)ALGORITHMS ROBERT SEDGEWICK BROWN UNNER!MY ADDISON-WESLEY PUBLISHING COM P ANY Reading, Massachusetts l Menlo Park, California London l Amsterdam l Don Mills, Ontario l Sydney To Adam, Brett, Robbie and especially LindaThis book is in theAddison-Wesley Series in Computer ScienceConsulting EditorMichael A. HarrisonSponsoring EditorJames T. DeWolfeLibrary of Congress Cataloging in Publication DataSedgewick, Robert, 1946- Algorithms. 1. Algorithms. I. Title.QA76.6.S435 1 9 8 3 519.4 82-11672ISBN O-201 -06672-6Reproduced by Addison-Wesley from camera-ready copy supplied by the author.Reprinted with corrections, August 1984Copyright 0 1983 by Addison-Wesley Publishing Company, Inc.All rights reserved. No part of this publication may be reproduced, stored ina retrieval system, or transmitted, in any form or by any means, electronic,mechanical, photocopying, recording, or otherwise, without prior written per-mission of the publisher. Printed in the United States of America.ISBN o-201-06672-6FGHIJ-HA-8987654 PrefaceThis book is intended to survey the most important algorithms in use oncomputers today and to teach fundamental techniques to the growing numberof people who are interested in becoming serious computer users. It is ap-propriate for use as a textbook for a second, third or fourth course in computerscience: after students have acquired some programming skills and familiaritywith computer systems, but before they have specialized courses in advancedareas of computer science or computer applications. Additionally, the bookmay be useful as a reference for those who already have some familiarity withthe material, since it contains a number of computer implementations of usefulalgorithms. The book consists of forty chapters which are grouped into seven majorparts: mathematical algorithms, sorting, searching, string processing, geomet-ric algorithms, graph algorithms and advanced topics. A major goal in thedevelopment of this book has been to bring together the fundamental methodsfrom these diverse areas, in order to provide access to the best methodsthat we know for solving problems by computer for as many people as pos-sible. The treatment of sorting, searching and string processing (which maynot be covered in other courses) is somewhat more complete than the treat-ment of mathematical algorithms (which may be covered in more depth inapplied mathematics or engineering courses), or geometric and graph algo-rithms (which may be covered in more depth in advanced computer sciencecourses). Some of the chapters involve mtroductory treatment of advancedmaterial. It is hoped that the descriptions here can provide students withsome understanding of the basic properties of fundamental algorithms suchas the FFT or the simplex method, while at the same time preparing themto better appreciate the methods when they learn them in advanced courses. The orientation of the book is towards algorithms that are likely to beof practical use. The emphasis is on t,eaching students the tools of theirtrade to the point that they can confidently implement, run and debug usefulalgorithms. Full implementations of the methods discussed (in an actualprogramming language) are included in the text, along with descriptions ofthe operations of these programs on a consistent set of examples. Though notemphasized, connections to theoretical computer science and the analysis ofalgorithms are not ignored. When appropriate, analytic results are discussedto illustrate why certain algorithms are preferred. When interesting, therelationship of the practical algorithms being discussed to purely theoreticalresults is described. More information of the orientation and coverage of thematerial in the book may be found in the Introduction which follows. One or two previous courses in computer science are recommended forstudents to be able to appreciate the material in this book: one course in . .. 111ivprogramming in a high-level language such as Pascal, and perhaps anothercourse which teaches fundamental concepts of programming systems. In short,students should be conversant with a modern programming language andhave a comfortable understanding of the basic features of modern computersystems. There is some mathematical material which requires knowledge ofcalculus, but this is isolated within a few chapters and could be skipped. There is a great deal of flexibility in the way that the material in thebook can be taught. To a large extent, ...