《计算机问题求解》课程参考书籍：《算法学——计算精髓》PDF电子版（Algorithmics - The Spirit of Computing，THIRD EDITION，David Harel）.pdf_大学文库

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

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

xii Preface universal agreement on a core of fundamental topics that computer science students should be taught. It would appear that anyone associated with computers ought to be aware of these topics,and not only those who have decided to spend three or four years getting a particular kind of academic diploma.Moreover,given that a revolution is indeed taking place before our very eyes,many of these topics,and the special ways of thinking that go with them,ought to be available to the enquiring person even if that person is not directly associated with a computer at all. Books concerned primarily with computers or programming are intended to fulfill quite different needs.Computers are made of bits and bytes,and programming is car- ried out using languages with rigid rules of grammar and punctuation.Consequently, computer books often suffer from the"bit/byte syndrome"and programming books from the"semicolon syndrome."In other words,the reader becomes predominantly involved in the principles of a particular computer or the syntactic rules of a particu- lar programming language (or both).It would seem that things cannot be explained without first describing,in detail,either a machine or a medium for communicating with one (or both). Many advanced textbooks do treat the fundamentals,but by their very nature they concentrate on specific topics,and do so at an advanced technical level that is usually unsuitable for the general reader.Even professional programmers and systems analysts might lack the background or motivation required to get through books aimed at full-time computer science students. Curiously,there appears to be very little written material devoted to the science of computing and aimed at the technically-oriented general reader as well as the computer professional.This fact is doubly curious in view of the abundance of precisely this kind of literature in most other scientific areas,such as physics,biology, chemistry,and mathematics,not to mention humanities and the arts.There appears to be an acute need for a technically-detailed,expository account of the fundamentals of computer science;one that suffers as little as possible from the bit/byte or semicolon syndromes and their derivatives,one that transcends the technological and linguistic whirlpool of specifics,and one that is useful both to a sophisticated layperson and to a computer expert.It seems that we have all been too busy with the revolution to be bothered with satisfying such a need. This book is an attempt in this direction.Its objective is to present a readable account of some of the most important and basic topics of computer science,stress- ing the fundamental and robust nature of the science in a form that is virtually independent of the details of specific computers,languages,and formalisms. This book grew out of a series of lectures given by the first author on"Galei Zahal," one of Israel's national radio channels,between October 1984 and January 1985.It is about what shall be called algorithmics in this book,that is,the study of algorithms. An algorithm is an abstract recipe,prescribing a process that might be carried out by a human,by a computer,or by other means.It thus represents a very general concept,with numerous applications.Its principal interest and use,however,is in those areas where the process is to be carried out by a computer

P1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 xii Preface universal agreement on a core of fundamental topics that computer science students should be taught. It would appear that anyone associated with computers ought to be aware of these topics, and not only those who have decided to spend three or four years getting a particular kind of academic diploma. Moreover, given that a revolution is indeed taking place before our very eyes, many of these topics, and the special ways of thinking that go with them, ought to be available to the enquiring person even if that person is not directly associated with a computer at all. Books concerned primarily with computers or programming are intended to fulfill quite different needs. Computers are made of bits and bytes, and programming is carried out using languages with rigid rules of grammar and punctuation. Consequently, computer books often suffer from the “bit/byte syndrome” and programming books from the “semicolon syndrome.” In other words, the reader becomes predominantly involved in the principles of a particular computer or the syntactic rules of a particular programming language (or both). It would seem that things cannot be explained without first describing, in detail, either a machine or a medium for communicating with one (or both). Many advanced textbooks do treat the fundamentals, but by their very nature they concentrate on specific topics, and do so at an advanced technical level that is usually unsuitable for the general reader. Even professional programmers and systems analysts might lack the background or motivation required to get through books aimed at full-time computer science students. Curiously, there appears to be very little written material devoted to the science of computing and aimed at the technically-oriented general reader as well as the computer professional. This fact is doubly curious in view of the abundance of precisely this kind of literature in most other scientific areas, such as physics, biology, chemistry, and mathematics, not to mention humanities and the arts. There appears to be an acute need for a technically-detailed, expository account of the fundamentals of computer science; one that suffers as little as possible from the bit/byte or semicolon syndromes and their derivatives, one that transcends the technological and linguistic whirlpool of specifics, and one that is useful both to a sophisticated layperson and to a computer expert. It seems that we have all been too busy with the revolution to be bothered with satisfying such a need. This book is an attempt in this direction. Its objective is to present a readable account of some of the most important and basic topics of computer science, stressing the fundamental and robust nature of the science in a form that is virtually independent of the details of specific computers, languages, and formalisms. ■ ■ This book grew out of a series of lectures given by the first author on “Galei Zahal,” one of Israel’s national radio channels, between October 1984 and January 1985. It is about what shall be called algorithmicsin this book, that is, the study of algorithms. An algorithm is an abstract recipe, prescribing a process that might be carried out by a human, by a computer, or by other means. It thus represents a very general concept, with numerous applications. Its principal interest and use, however, is in those areas where the process is to be carried out by a computer

Preface xiii The book could be used as the basis of a one-semester introductory course in computer science or a general computer science literacy course in science and engineering schools.Moreover,it can be used as supplementary reading in many kinds of computer-related educational activities,from basic programming courses to advanced graduate or undergraduate degree programs in computer science.The material covered herein,while not directly aimed at producing better programmers or system analysts,can aid people who work with computers by providing an overall picture of some of the most fundamental issues relevant to their work. The preliminary chapters discuss the concept of an algorithmic problem and the algorithm that solves it,followed by cursory discussions of the structure of algo- rithms,the data they manipulate,and the languages in which they are programmed. With the stage thus set,Part Two of the book turns to some general methods and paradigms for algorithmic design.This is followed by two chapters on the ana- lysis of algorithms,treating,respectively,their correctness and efficiency(mainly time efficiency),including techniques for establishing the former and estimating the latter.Part Three of the book is devoted to the inherent limitations of effectively executable algorithms,and hence of the computers that implement them.Certain precisely defined problems,including important and practical ones,are shown to be provably not solvable by any computers of reasonable size in any reasonable amount of time (say,the lifetime of a person),and never will be.Worse still,it is shown that some problems are provably not solvable by computers at all,even with unlimited time!In Part Four of the book'the requirements are relaxed,for example, by employing concurrent activities or coin tossing,in order to overcome some of these difficulties.These chapters also discuss reactive and distributed systems, and cryptography.Finally,the relationship of computers to human intelligence is discussed,emphasizing the"soft"heuristic,or intuitive,nature of the latter,and the problems involved in relating it to the"hard"scientific subject of algorithmics. The book is intended to be read or studied sequentially,not to be used as a reference.It is organized so that each chapter depends on the previous ones,but with smooth readability in mind.Most of the material in the preliminary Part One should be familiar to people with a background in programming.Thus,Chapters 1 and 2 and parts of Chapter 3 can be browsed through by such readers. Certain sections contain relatively technical material and can be skipped by the reader without too much loss of continuity.They are indented,set in smaller type and are prefixed by a small square.It is recommended,however,that even those sections be skimmed,at least to get a superficial idea of their contents. Whenever appropriate,brief discussions of the research topics that are of current interest to computer scientists are included.The text is followed by a section of detailed bibliographic notes for each chapter,with"backward"pointers connecting the discussions in the text with the relevant literature. ■ 1 See the section below,"New to the third edition,"as there is now a fifth Part and the division is somewhat different

P1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 Preface xiii The book could be used as the basis of a one-semester introductory course in computer science or a general computer science literacy course in science and engineering schools. Moreover, it can be used as supplementary reading in many kinds of computer-related educational activities, from basic programming courses to advanced graduate or undergraduate degree programs in computer science. The material covered herein, while not directly aimed at producing better programmers or system analysts, can aid people who work with computers by providing an overall picture of some of the most fundamental issues relevant to their work. ■ ■ The preliminary chapters discuss the concept of an algorithmic problem and the algorithm that solves it, followed by cursory discussions of the structure of algorithms, the data they manipulate, and the languagesin which they are programmed. With the stage thus set, Part Two of the book turns to some general methods and paradigms for algorithmic design. This is followed by two chapters on the analysis of algorithms, treating, respectively, their correctness and efficiency (mainly time efficiency), including techniques for establishing the former and estimating the latter. Part Three of the book is devoted to the inherent limitations of effectively executable algorithms, and hence of the computers that implement them. Certain precisely defined problems, including important and practical ones, are shown to be provably not solvable by any computers of reasonable size in any reasonable amount of time (say, the lifetime of a person), and never will be. Worse still, it is shown that some problems are provably not solvable by computers at all, even with unlimited time! In Part Four of the book1 the requirements are relaxed, for example, by employing concurrent activities or coin tossing, in order to overcome some of these difficulties. These chapters also discuss reactive and distributed systems, and cryptography. Finally, the relationship of computers to human intelligence is discussed, emphasizing the “soft” heuristic, or intuitive, nature of the latter, and the problems involved in relating it to the “hard” scientific subject of algorithmics. The book is intended to be read or studied sequentially, not to be used as a reference. It is organized so that each chapter depends on the previous ones, but with smooth readability in mind. Most of the material in the preliminary Part One should be familiar to people with a background in programming. Thus, Chapters 1 and 2 and parts of Chapter 3 can be browsed through by such readers. Certain sections contain relatively technical material and can be skipped by the reader without too much loss of continuity. They are indented, set in smaller type and are prefixed by a small square. It is recommended, however, that even those sections be skimmed, at least to get a superficial idea of their contents. Whenever appropriate, brief discussions of the research topics that are of current interest to computer scientists are included. The text is followed by a section of detailed bibliographic notes for each chapter, with “backward” pointers connecting the discussions in the text with the relevant literature. ■ ■ 1 See the section below, “New to the third edition,” as there is now a fifth Part and the division is somewhat different

xiv Preface It is hoped that this book will facilitate communication between the various groups of people who are actively involved in the computer revolution,and between that group,and those who,for the time being,are observers only. David Harel Pittsburgh,Pennsylvania February,1987 New to the Second Edition See,this is new;but it has already been ECCLESIASTES 1:10 The first edition of this book was intended to be read from beginning to end,and could be used as supplementary reading in a number of courses.Teaching a course based exclusively on it was possible,but would have required the instructor to prepare exercises and add examples and more detail in certain places.The present edition contains numerous exercises,as well as solutions to about a third of them. The solved exercises can thus be used to supplement the text.Three chapters have not been supplied with exercises.Chapter 1 is an introduction,the bulk of Chapter 3 is really just a brief survey of several programming languages,and Chapter 12 is a nontechnical account of some topics in artificial intelligence.2 In a sense,the three are not integral parts of the topic of the book-algorithmics-and hence in teaching a course based on the book these should probably be assigned as homework reading. The text itself remains largely without change,except for a new section in Chapter 11 describing the recent topics of interactive proofs and zero-knowledge. The reader may wonder why a more extensive revision of the text was not called for.Have computer scientists been idle during the five years since the first edition was written?Rather than taking this as a criticism of the field,I think that it shows that the topics selected for inclusion in the book are really of fundamental nature, so that no significant changes had to be made.The issues discussed herein are thus probably basic and lasting.Maybe the term"classical"is most fitting David Harel Rehovot,Israel May,1991 New to the Third Edition they three iere of one measure EZEKIEL 40:10 This time around,a significant revision was carried out.There are several important changes in this edition of the book,compared to the first and second editions, including two brand new chapters,new sections,and more 2 Again,see the section below,"New to the third edition."as some of these chapter numbers have changed

P1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 xiv Preface It is hoped that this book will facilitate communication between the various groups of people who are actively involved in the computer revolution, and between that group, and those who, for the time being, are observers only. David Harel Pittsburgh, Pennsylvania February, 1987 ■ New to the Second Edition See, this is new; but it has already been ECCLESIASTES 1: 10 The first edition of this book was intended to be read from beginning to end, and could be used as supplementary reading in a number of courses. Teaching a course based exclusively on it was possible, but would have required the instructor to prepare exercises and add examples and more detail in certain places. The present edition contains numerous exercises, as well as solutions to about a third of them. The solved exercises can thus be used to supplement the text. Three chapters have not been supplied with exercises. Chapter 1 is an introduction, the bulk of Chapter 3 is really just a brief survey of several programming languages, and Chapter 12 is a nontechnical account of some topics in artificial intelligence.2 In a sense, the three are not integral parts of the topic of the book—algorithmics—and hence in teaching a course based on the book these should probably be assigned as homework reading. The text itself remains largely without change, except for a new section in Chapter 11 describing the recent topics of interactive proofs and zero-knowledge. The reader may wonder why a more extensive revision of the text was not called for. Have computer scientists been idle during the five years since the first edition was written? Rather than taking this as a criticism of the field, I think that it shows that the topics selected for inclusion in the book are really of fundamental nature, so that no significant changes had to be made. The issues discussed herein are thus probably basic and lasting. Maybe the term “classical” is most fitting. David Harel Rehovot, Israel May, 1991 ■ New to the Third Edition they three were of one measure EZEKIEL 40: 10 This time around, a significant revision was carried out. There are several important changes in this edition of the book, compared to the first and second editions, including two brand new chapters, new sections, and more. 2 Again, see the section below, “New to the third edition,” as some of these chapter numbers have changed

Preface XV The first noticeable difference is that for this revision I needed real help..., and was fortunately joined by Yishai Feldman.He has taken part in all aspects of the revision,but most significantly took upon himself the thorough revision of the material on programming languages and the writing of the new chapter on software engineering. The main changes are as follows: The book now has five Parts,rather than four.In Part I(Preliminaries)Chapter 3 has been completely rewritten,and is now titled"Programming Languages and Paradigms."The list of languages discussed has been revised and is organized into paradigms,thus giving a more informative and updated exposition of the media we use when we program computers.Discussions of some languages (e.g.,APL and SNOBOL)have been dropped altogether and those of others (e.g.,C,C++and JAVA) have been added. Part II(Methods and Analysis)and Part III(Limitations and Robustness),i.e., Chapters 4 through 9,required no sweeping changes.This can again be attributed to the "classical"nature of the topics chosen for these,as mentioned in the "New to the second edition"section above. The first chapter of Part IV (Relaxing the Rules)was previously titled"Paral- lelism and Concurrency"and is now called"Parallelism,Concurrency,and Alterna- tive Models."It incorporates new sections on quantum computing,including Shor's factoring algorithm,and a discussion of molecular computing.These topics may be considered to be additional forms of parallelism,albeit more radical ones.The re- maining two chapters of Part IV were constructed by separating out the material on probabilistic algorithms(Chapter 11)from that on cryptography(now Chapter 12) presented together in a single chapter in the previous editions-and extending both by discussions of some of the new developments in these fields. Part V(The Bigger Picture)ends with the closing chapter of the previous edi- tions,"Algorithmics and Intelligence,"which is now Chapter 15.However,this is now preceded by two new chapters:Chapter 13,"Software Engineering,"and Chapter 14,"Reactive Systems."The first of these is an attempt to provide a general introduction to the issues and problems arising in the development of large soft- ware systems.The second new chapter zeros in on the particular difficulties arising in the special case of reactive systems,as a result of their complex behavior over time. Besides these more noticeable changes,the entire text has been brought up to date in many less subtle and more subtle ways.There are discussions on abstract data types,on the nonapproximability of certain NP-complete problems,on proba- bilistically checkable proofs,and on the brand new AKS polynomial-time algorithm for primality.The final chapter has been modified in many places too,e.g.,with a discussion added on the Chinese room argument. While we have left the exercises and solutions essentially as they were in the second edition,the bibliographic notes were a completely different story.Twelve years in Computer Science is almost an eternity...The format of the notes is the same as in the previous editions;i.e.,a general section at the start of each chapter, which lists relevant books and periodicals,followed by detailed notes that progress with the text of the chapter itself and point back to its page numbers.In revising them,we had to prepare new notes for the large amount of newly added material, of course,but we also had to painstakingly reconsider and thoroughly revise the entire set of existing notes.Hopefully,the result of all of this will turn out to be a

P1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 Preface xv The first noticeable difference is that for this revision I needed real help ... , and was fortunately joined by Yishai Feldman. He has taken part in all aspects of the revision, but most significantly took upon himself the thorough revision of the material on programming languages and the writing of the new chapter on software engineering. The main changes are as follows: The book now has five Parts, rather than four. In Part I (Preliminaries) Chapter 3 has been completely rewritten, and is now titled “Programming Languages and Paradigms.” The list of languages discussed has been revised and is organized into paradigms, thus giving a more informative and updated exposition of the media we use when we program computers. Discussions of some languages (e.g., APL and SNOBOL) have been dropped altogether and those of others (e.g., C, C++ and JAVA) have been added. Part II (Methods and Analysis) and Part III (Limitations and Robustness), i.e., Chapters 4 through 9, required no sweeping changes. This can again be attributed to the “classical” nature of the topics chosen for these, as mentioned in the “New to the second edition” section above. The first chapter of Part IV (Relaxing the Rules) was previously titled “Parallelism and Concurrency” and is now called “Parallelism, Concurrency, and Alternative Models.” It incorporates new sections on quantum computing, including Shor’s factoring algorithm, and a discussion of molecular computing. These topics may be considered to be additional forms of parallelism, albeit more radical ones. The remaining two chapters of Part IV were constructed by separating out the material on probabilistic algorithms (Chapter 11) from that on cryptography (now Chapter 12)— presented together in a single chapter in the previous editions—and extending both by discussions of some of the new developments in these fields. Part V (The Bigger Picture) ends with the closing chapter of the previous editions, “Algorithmics and Intelligence,” which is now Chapter 15. However, this is now preceded by two new chapters: Chapter 13, “Software Engineering,” and Chapter 14, “Reactive Systems.” The first of these is an attempt to provide a general introduction to the issues and problems arising in the development of large software systems. The second new chapter zeros in on the particular difficulties arising in the special case of reactive systems, as a result of their complex behavior over time. Besides these more noticeable changes, the entire text has been brought up to date in many less subtle and more subtle ways. There are discussions on abstract data types, on the nonapproximability of certain NP-complete problems, on probabilistically checkable proofs, and on the brand new AKS polynomial-time algorithm for primality. The final chapter has been modified in many places too, e.g., with a discussion added on the Chinese room argument. While we have left the exercises and solutions essentially as they were in the second edition, the bibliographic notes were a completely different story. Twelve years in Computer Science is almost an eternity ... The format of the notes is the same as in the previous editions; i.e., a general section at the start of each chapter, which lists relevant books and periodicals, followed by detailed notes that progress with the text of the chapter itself and point back to its page numbers. In revising them, we had to prepare new notes for the large amount of newly added material, of course, but we also had to painstakingly reconsider and thoroughly revise the entire set of existing notes. Hopefully, the result of all of this will turn out to be a