Algorithmics The Spirit of Computing THIRD EDITION David Harel with Yishai Feldman 大 ADDISON WESLEY
The Spirit of Computing David Harel with Yishai Feldman Yishai Feldman with David Harel The Spirit of Computing The Spirit of Computing THIRD EDITION THIRD EDITION THIRD EDITION Algorithmics Algorithmics Algorithmics From a review of the first edition: ‘This book is a veritable tour de force. Harel writes with uncommon verve, clarity and imagination. ‘Through the use of tantalizing questions and aptly chosen and often amusing examples, the author transmits to the reader the excitement and intellectual satisfaction of computer science research. Without the use of formal mathematics and without any sacrifice of intellectual integrity, he conveys to the general reader the profound principles on which computer science is founded and which hitherto were only accessible in abstruse and esoteric textbooks and papers. ‘This is scientific writing at its best.’ Dr Stan Scott, Queen's University Belfast The Times Higher Education Supplement. 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 concerns the true ‘spirit’ of computers; with the ‘recipes’ that make them tick – their algorithms. New to this edition ■ Chapters on software engineering and on reactive systems. ■ Thoroughly revised chapter on programming languages. ■ New material on quantum and molecular computing. ■ Whole text thoroughly updated to include new material on many topics, including abstract data types, the object–oriented paradigm, primality testing, and system verification and validation. David Harel is Professor and Dean of the Faculty of Mathematics and Computer Science at the Weizmann Institute of Science. He is renowned for outstanding research in many areas of the field, and has recently been awarded the Israel Prize in Computer Science. Yishai Feldman is on the faculty of the Efi Arazi School of Computer Science at the Interdisciplinary Centre, Herzliya. He specializes in the use of artificial–intelligence techniques in software engineering and their real–world applications. an imprint of www.pearson-books.com Harel Cvr.QXD 16/01/2006 09:40 PM Page 1
Contents Declare the things that are to come hereafter ISALAH 41:23 Preface xi Acknowledgments xvii Part I.Preliminaries 1 1.Introduction and Historical Review 3 or,What's It All About? 2.Algorithms and Data 19 or,Getting It Done 3.Programming Languages and Paradigms 49 or,Getting It Done by Computer Part Il.Methods and Analysis 79 4.Algorithmic Methods 81 or,Getting It Done Methodically 5.The Correctness of Algorithms 99 or,Getting It Done Right
P1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 Contents Declare the things that are to come hereafter ISAIAH 41: 23 Preface xi Acknowledgments xvii Part I. Preliminaries 1 ■ 1. Introduction and Historical Review 3 or, What’s It All About? ■ 2. Algorithms and Data 19 or, Getting It Done ■ 3. Programming Languages and Paradigms 49 or, Getting It Done by Computer Part II. Methods and Analysis 79 ■ 4. Algorithmic Methods 81 or, Getting It Done Methodically ■ 5. The Correctness of Algorithms 99 or, Getting It Done Right vii
viii Contents 6.The Efficiency of Algorithms 129 or,Getting It Done Cheaply Part lll.Limitations and Robustness 157 7.Inefficiency and Intractability 159 or,You Can't Always Get It Done Cheaply 8.Noncomputability and Undecidability 191 or,Sometimes You Can't Get It Done At All! 9.Algorithmic Universality and Its Robustness 219 or,The Simplest Machines That Get It Done Part IV.Relaxing the Rules 255 10.Parallelism,Concurrency,and Alternative Models 257 or,Getting Lots of Stuff Done at Once 11.Probabilistic Algorithms 297 or,Getting It Done by Tossing Coins 12.Cryptography and Reliable Interaction 317 or,Getting It Done in Secret Part V.The Bigger Picture 335 13.Software Engineering 337 or,Getting It Done When It's Large ■14.Reactive Systems 357 or,Getting It to Behave Properly Over Time 15.Algorithmics and Intelligence 379 or,Are They Better at It Than Us?
P1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 viii Contents ■ 6. The Efficiency of Algorithms 129 or, Getting It Done Cheaply Part III. Limitations and Robustness 157 ■ 7. Inefficiency and Intractability 159 or, You Can’t Always Get It Done Cheaply ■ 8. Noncomputability and Undecidability 191 or, Sometimes You Can’t Get It Done At All! ■ 9. Algorithmic Universality and Its Robustness 219 or, The Simplest Machines That Get It Done Part IV. Relaxing the Rules 255 ■ 10. Parallelism, Concurrency, and Alternative Models 257 or, Getting Lots of Stuff Done at Once ■ 11. Probabilistic Algorithms 297 or, Getting It Done by Tossing Coins ■ 12. Cryptography and Reliable Interaction 317 or, Getting It Done in Secret Part V. The Bigger Picture 335 ■ 13. Software Engineering 337 or, Getting It Done When It’s Large ■ 14. Reactive Systems 357 or, Getting It to Behave Properly Over Time ■ 15. Algorithmics and Intelligence 379 or, Are They Better at It Than Us?
Contents ix Postscript 401 Selected Solutions 403 Bibliographic Notes 433 Index 495
P1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 Contents ix Postscript 401 Selected Solutions 403 Bibliographic Notes 433 Index 495
Preface (written for the First Edition) Read this,I pray thee ISALAH 29:12 This book tells a story.The story concerns the concepts,ideas,methods,and results fundamental to computer science.It is not specifically about computer technology, nor is it about computer programming,though obviously it is heavily influenced by both. The book is intended to fill a rather disturbing gap in the literature related to the computer revolution.Scores of excellent books can be found on computers themselves,with details of their structure,workings,and operation.There are also numerous books about the act of writing programs for computers in any of a growing number of languages.These books come at a wide range of levels,some aimed at people with no computer-related background at all,and some aimed at the most computer-literate professionals.In addition,there are many books on subjects pe- ripheral to the technology,such as the social and legal aspects of the revolution, as well as books describing the relevance of computers to a variety of application areas.All this comes as no surprise.People are curious about computers,and want to learn how to put them to use.They are typically interested in specific kinds of computers,and often for specific purposes,too. Then there are textbooks.Indeed,computer science is a fast-growing academic discipline,with ever-larger numbers of potential students knocking at the doors of admission offices.Well-established academic disciplines have a habit of yielding excellent textbooks,and computer science is no exception.Over the years many comprehensive and clearly written textbooks have appeared,containing detailed technical accounts of the subjects deemed appropriate to students of computer sci- ence.However,despite the dizzying speed with which some of the technological innovations become obsolete and are replaced by new ones,the fundamentals of the science of computation,and hence many of the basic concepts that are considered important in a computer science curriculum,change slowly,if at all.Of course,new technologies and new languages require revisions in scientific emphasis,which are eventually reflected in the scientific literature.However,by and large,there is almost
P1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 Preface (written for the First Edition) Read this, I pray thee ISAIAH 29: 12 This book tells a story. The story concerns the concepts, ideas, methods, and results fundamental to computer science. It is not specifically about computer technology, nor is it about computer programming, though obviously it is heavily influenced by both. The book is intended to fill a rather disturbing gap in the literature related to the computer revolution. Scores of excellent books can be found on computers themselves, with details of their structure, workings, and operation. There are also numerous books about the act of writing programs for computers in any of a growing number of languages. These books come at a wide range of levels, some aimed at people with no computer-related background at all, and some aimed at the most computer-literate professionals. In addition, there are many books on subjects peripheral to the technology, such as the social and legal aspects of the revolution, as well as books describing the relevance of computers to a variety of application areas. All this comes as no surprise. People are curious about computers, and want to learn how to put them to use. They are typically interested in specific kinds of computers, and often for specific purposes, too. Then there are textbooks. Indeed, computer science is a fast-growing academic discipline, with ever-larger numbers of potential students knocking at the doors of admission offices. Well-established academic disciplines have a habit of yielding excellent textbooks, and computer science is no exception. Over the years many comprehensive and clearly written textbooks have appeared, containing detailed technical accounts of the subjects deemed appropriate to students of computer science. However, despite the dizzying speed with which some of the technological innovations become obsolete and are replaced by new ones, the fundamentals of the science of computation, and hence many of the basic concepts that are considered important in a computer science curriculum, change slowly, if at all. Of course, new technologies and new languages require revisions in scientific emphasis, which are eventually reflected in the scientific literature. However, by and large, there is almost xi