Harel Cvr.QXD 16/01/2006 09:40 PM Page 1 Algorithmics Algorithmics The Spirit of Computing The Spirit of Computing T A h THIRD EDITION e l S g From a review of the first edition: p THIRD EDITION i r o ‘This book is a veritable tour de force. Harel writes with uncommon verve, i t clarity and imagination. r o David Harel f i ‘Through the use of tantalizing questions and aptly chosen and often amusing examples, C t the author transmits to the reader the excitement and intellectual satisfaction of computer o science research. Without the use of formal mathematics and without any sacrifice of m h with intellectual integrity, he conveys to the general reader the profound principles on which p computer science is founded and which hitherto were only accessible in abstruse and u m Yishai Feldman t esoteric textbooks and papers. i n ‘This is scientific writing at its best.’ g i c Dr Stan Scott, Queen's University Belfast The Times Higher Education Supplement. s This book tells the story of the concepts, ideas, methods and results fundamental to computer science, in a form independent of the details of specific computers, languages and formalisms. It T concerns the true ‘spirit’ of computers; with the ‘recipes’ that make them tick – their algorithms. H I R New to this edition D ■ Chapters on software engineering and on reactive systems. ED ■ Thoroughly revised chapter on programming languages. IT ■ New material on quantum and molecular computing. IO ■ Whole text thoroughly updated to include new material on many topics, including abstract N data types, the object–oriented paradigm, primality testing, and system verification and validation. YwD ii shtha v David Harel is Professor and Dean of the Faculty of Mathematics and Computer Science at the a i i Weizmann Institute of Science. He is renowned for outstanding research in many areas of the d F field, and has recently been awarded the Israel Prize in Computer Science. Yishai Feldman is on e l H the faculty of the Efi Arazi School of Computer Science at the Interdisciplinary Centre, Herzliya. d m a He specializes in the use of artificial–intelligence techniques in software engineering and their a r real–world applications. n e l www.pearson-books.com an imprint of www.it-ebooks.info P1:GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March19,2004 19:35 Algorithmics The Spirit of Computing www.it-ebooks.info i P1:GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March19,2004 19:35 Weworkwithleadingauthorstodevelopthe strongesteducationalmaterialsincomputing, bringingcutting-edgethinkingandbestlearning practicetoaglobalmarket. Underarangeofwell-knownimprints,including Addison-Wesley,wecrafthighqualityprintand electronicpublicationswhichhelpreaderstounderstand andapplytheircontent,whetherstudyingoratwork. Tofindoutmoreaboutthecompleterangeofour publishing,pleasevisitusontheWorldWideWebat: www.pearsoned.co.uk www.it-ebooks.info ii P1:GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March19,2004 19:35 Algorithmics The Spirit of Computing THIRD EDITION David Harel TheWeizmannInstitute with Yishai Feldman TheInterdisciplinaryCenter,Herzliya www.it-ebooks.info iii P1:GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March19,2004 19:35 PearsonEducationLimited EdinburghGate Harlow EssexCM202JE England andAssociatedCompaniesthroughouttheworld VisitusontheWorldWideWebat: www.pearsoned.co.uk Firstpublished1987 Secondedition1992 Thirdeditionpublished2004 (cid:2)C Addison-WesleyPublishersLimited1987,1992 (cid:2)C PearsonEducationLimited2004 TherightsofDavidHarelandYishaiFeldmantobeidentifiedasauthorsofthiswork havebeenassertedbytheminaccordancewiththeCopyright,DesignsandPatentsAct1988. Allrightsreserved.Nopartofthispublicationmaybereproduced,storedinaretrieval system,ortransmittedinanyformorbyanymeans,electronic,mechanical, photocopying,recordingorotherwise,withouteitherthepriorwrittenpermissionofthe publisheroralicencepermittingrestrictedcopyingintheUnitedKingdomissuedbythe CopyrightLicensingAgencyLtd,90TottenhamCourtRoad,LondonW1T4LP. Theprogramsinthisbookhavebeenincludedfortheirinstructionalvalue.Theyhavebeen testedwithcarebutarenotguaranteedforanyparticularpurpose.Thepublisherdoesnot offeranywarrantiesorrepresentationsnordoesitacceptanyliabilitieswithrespecttothe programs. Alltrademarksusedhereinarethepropertyoftheirrespectiveowners.Theuseofany trademarkinthistextdoesnotvestintheauthororpublisheranytrademarkownershiprights insuchtrademarks,nordoestheuseofsuchtrademarksimplyanyaffiliationwithor endorsementofthisbookbysuchowner. ISBN0321117840 BritishLibraryCataloguing-in-PublicationData AcataloguerecordforthisbookisavailablefromtheBritishLibrary. LibraryofCongressCataloging-in-PublicationData Harel,David,1950– Algorithmics:thespiritofcomputing/DavidHarel,withYishaiFeldman.–3rded. p.cm. Includesbibliographicalreferencesandindex. ISBN0-321-11784-0 1.Computeralgorithms. I.Feldman,YishaiA.,1958– II.Title. QA76.9.A43H37 2004 005.1–dc22 2004041063 10987654321 0807060504 Typesetby59in10/12ptTimes PrintedandboundinGreatBritainbyBiddlesLtd.,GuildfordandKing’sLynn www.it-ebooks.info iv P1:GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March19,2004 19:35 Formydearmother,JoyceFisch Andinmemoryofmydearfather,HaroldFisch Belovedparentsandgiftedteachersboth (D.H.) Tothememoryofmydearparents, HadassaandMosheFeldman Fortheirunfailingloveandsupport (Y.F.) www.it-ebooks.info v P1:GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March19,2004 19:35 Tellme,Ipraythee, inwhatthygreatstrengthlies JUDGES16:6 Behold,thisIhavefound... countingonethingtoanother,tofindoutthesum ECCLESIASTES7:27 www.it-ebooks.info vi P1:GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March19,2004 19:35 Contents Declarethethings thataretocome hereafter ISAIAH41:23 Preface xi Acknowledgments xvii Part I. Preliminaries 1 (cid:2) 1. Introduction and Historical Review 3 or,What’sItAllAbout? (cid:2) 2. Algorithms and Data 19 or,GettingItDone (cid:2) 3. Programming Languages and Paradigms 49 or,GettingItDonebyComputer Part II. Methods and Analysis 79 (cid:2) 4. Algorithmic Methods 81 or,GettingItDoneMethodically (cid:2) 5. The Correctness of Algorithms 99 or,GettingItDoneRight www.it-ebooks.info vii P1:GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March19,2004 19:35 viii Contents (cid:2) 6. The Efficiency of Algorithms 129 or,GettingItDoneCheaply Part III. Limitations and Robustness 157 (cid:2) 7. Inefficiency and Intractability 159 or,YouCan’tAlwaysGetItDoneCheaply (cid:2) 8. Noncomputability and Undecidability 191 or,SometimesYouCan’tGetItDoneAtAll! (cid:2) 9. Algorithmic Universality and Its Robustness 219 or,TheSimplestMachinesThatGetItDone Part IV. Relaxing the Rules 255 (cid:2) 10. Parallelism, Concurrency, and Alternative Models 257 or,GettingLotsofStuffDoneatOnce (cid:2) 11. Probabilistic Algorithms 297 or,GettingItDonebyTossingCoins (cid:2) 12. Cryptography and Reliable Interaction 317 or,GettingItDoneinSecret Part V. The Bigger Picture 335 (cid:2) 13. Software Engineering 337 or,GettingItDoneWhenIt’sLarge (cid:2) 14. Reactive Systems 357 or,GettingIttoBehaveProperlyOverTime (cid:2) 15. Algorithmics and Intelligence 379 or,AreTheyBetteratItThanUs? www.it-ebooks.info P1:GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March19,2004 19:35 Contents ix Postscript 401 SelectedSolutions 403 BibliographicNotes 433 Index 495 www.it-ebooks.info