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

1.Introduction and Historical Review 15 Figure 1.4 any legal The algorithmic problem and its input solution. characterization of all legal inputs algorithm and A characterization of desired outputs as a function desired of inputs output Algorithmic problem Algorithmic solution Later we shall address such issues as the efficiency and practicality of algorithms. Here we claim the minimal requirement that an algorithm does,in fact,solve the problem,even though it might do so inefficiently.Of course,the problem itself can specify the required behavior of a potential algorithm on undesirable inputs, but then these inputs,although undesirable,are still legal.For example,the salary summation problem could conceivably contain the requirement that for an employee whose record does not show a number in the salary area but,say,a question mark, or some other nonsensical data the algorithm should add that employee's name to a special list,which will be forwarded to the payroll office for further action.Such an unorthodox list of employees is nevertheless legal;it just is not dealt with in the standard way,but is given some special treatment that befits its abnormal nature. Thus,keeping illegal inputs separate is the responsibility of the algorithmic problem, while treating special classes of unusual or undesirable inputs is the responsibility of the algorithm itself. Bounds on Basic Actions There is one other important matter that we need to address at this point concerning the execution of the basic actions,or operations,prescribed by an algorithm.It is obvious that each of these actions must be carried out in a finite amount of time, otherwise,of course,the algorithm will never reach an end.Thus,infinitely long actions are bad.Actions that can take infinitesimally small amounts of time are outlawed too,a fact that needs little justification.It is unthinkable that a machine will ever be able to perform actions in diminishing amounts of time.The speed of light,for one,would always serve as a limit on the speed of any machine.Similar limits on the resources (that is,utensils)used in performing basic actions have to be enforced too,but we shall not discuss the reasons here

P1: GIG PE002-01drv PE002-Harel PE002-Harel-v4.cls February 25, 2004 14:38 1. Introduction and Historical Review 15 characterization of all legal inputs and any legal input desired output Algorithmic problem Algorithmic solution algorithm A characterization of desired outputs as a function of inputs Figure 1.4 The algorithmic problem and its solution. Later we shall address such issues as the efficiency and practicality of algorithms. Here we claim the minimal requirement that an algorithm does, in fact, solve the problem, even though it might do so inefficiently. Of course, the problem itself can specify the required behavior of a potential algorithm on undesirable inputs, but then these inputs, although undesirable, are still legal. For example, the salary summation problem could conceivably contain the requirement that for an employee whose record does not show a number in the salary area but, say, a question mark, or some other nonsensical data the algorithm should add that employee’s name to a special list, which will be forwarded to the payroll office for further action. Such an unorthodox list of employees is nevertheless legal; it just is not dealt with in the standard way, but is given some special treatment that befits its abnormal nature. Thus, keeping illegal inputs separate is the responsibility of the algorithmic problem, while treating special classes of unusual or undesirable inputs is the responsibility of the algorithm itself. ■ Bounds on Basic Actions There is one other important matter that we need to address at this point concerning the execution of the basic actions, or operations, prescribed by an algorithm. It is obvious that each of these actions must be carried out in a finite amount of time, otherwise, of course, the algorithm will never reach an end. Thus, infinitely long actions are bad. Actions that can take infinitesimally small amounts of time are outlawed too, a fact that needs little justification. It is unthinkable that a machine will ever be able to perform actions in diminishing amounts of time. The speed of light, for one, would always serve as a limit on the speed of any machine. Similar limits on the resources (that is, utensils) used in performing basic actions have to be enforced too, but we shall not discuss the reasons here

16 I.Preliminaries Clearly,these assumptions about basic actions indeed hold for real computers. The basic bit-manipulation actions,for example,are precise and unambiguous,and take bounded amounts of time and resources.Thus,as promised,the theory of algorithmics described herein will be directly applicable to problems intended for computer-based solution. The Problem and Its Solution:Summary To summarize,an algorithmic problem consists of: 1.a characterization of a legal,possibly infinite,collection of potential input sets, and 2.a specification of the desired outputs as a function of the inputs. It is assumed that either a description of the allowed basic actions or a hardware configuration together with its built-in basic actions are also provided in advance A solution to an algorithmic problem consists of an algorithm,composed of el- ementary instructions prescribing actions from the agreed-on set.This algorithm, when executed for any legal input set,solves the problem,producing the output as required.Starting in Chapter 10 we shall be generalizing these notions,but until then the present definition will suffice. It is important to recognize the considerable difficulty involved in solving algo- rithmic problems satisfactorily.By starting out with a mousse recipe and then giving a simple summation algorithm,a certain amount of injustice has been done,as it might appear that things are easy.Nothing is further from the truth.Algorithmic problems,in practice,can be incredibly complex,and can take years of work to solve successfully.Worse still,as we shall see in later chapters,many problems do not admit satisfactory solutions,while others do not admit any solutions at all.For many problems the status,as far as good algorithmic solutions are concerned,is as yet unknown,despite extensive work by many talented people. Obviously,we shall not be able to illustrate the issues treated in this book with overly lengthy and complex examples,but we can get a feel for the difficulty in designing algorithms by thinking about the following (informally described)algo- rithmic problems.In the first problem the input is a legal chess position (that is,a description of the situation reached at some point during a chess game),while the output is the best move for White (that is,the description of a move that maximizes White's chances of winning the game).The second problem concerns newspa- per distribution.Suppose 20,000 papers are to be distributed to 1000 locations in 100 towns using 50 trucks.The input contains the road distances between the towns and between the locations within each town,the number of papers required at each location,the present location of each truck,each truck's newspaper-carrying ability, as well as its gasoline capacity and miles-per-gallon performance,and details of available drivers,including their present whereabouts.The output is to be a list, matching drivers to trucks,and containing detailed itineraries for each of the trucks so that the total number of miles driven is minimized.Actually,the problem calls

P1: GIG PE002-01drv PE002-Harel PE002-Harel-v4.cls February 25, 2004 14:38 16 I. Preliminaries Clearly, these assumptions about basic actions indeed hold for real computers. The basic bit-manipulation actions, for example, are precise and unambiguous, and take bounded amounts of time and resources. Thus, as promised, the theory of algorithmics described herein will be directly applicable to problems intended for computer-based solution. ■ The Problem and Its Solution: Summary To summarize, an algorithmic problem consists of: 1. a characterization of a legal, possibly infinite, collection of potential input sets, and 2. a specification of the desired outputs as a function of the inputs. It is assumed that either a description of the allowed basic actions or a hardware configuration together with its built-in basic actions are also provided in advance. A solution to an algorithmic problem consists of an algorithm, composed of elementary instructions prescribing actions from the agreed-on set. This algorithm, when executed for any legal input set, solves the problem, producing the output as required. Starting in Chapter 10 we shall be generalizing these notions, but until then the present definition will suffice. It is important to recognize the considerable difficulty involved in solving algorithmic problems satisfactorily. By starting out with a mousse recipe and then giving a simple summation algorithm, a certain amount of injustice has been done, as it might appear that things are easy. Nothing is further from the truth. Algorithmic problems, in practice, can be incredibly complex, and can take years of work to solve successfully. Worse still, as we shall see in later chapters, many problems do not admit satisfactory solutions, while others do not admit any solutions at all. For many problems the status, as far as good algorithmic solutions are concerned, is as yet unknown, despite extensive work by many talented people. Obviously, we shall not be able to illustrate the issues treated in this book with overly lengthy and complex examples, but we can get a feel for the difficulty in designing algorithms by thinking about the following (informally described) algorithmic problems. In the first problem the input is a legal chess position (that is, a description of the situation reached at some point during a chess game), while the output is the best move for White (that is, the description of a move that maximizes White’s chances of winning the game). The second problem concerns newspaper distribution. Suppose 20,000 papers are to be distributed to 1000 locations in 100 towns using 50 trucks. The input contains the road distances between the towns and between the locations within each town, the number of papers required at each location, the present location of each truck, each truck’s newspaper-carrying ability, as well as its gasoline capacity and miles-per-gallon performance, and details of available drivers, including their present whereabouts. The output is to be a list, matching drivers to trucks, and containing detailed itineraries for each of the trucks so that the total number of miles driven is minimized. Actually, the problem calls

P1: GIG PE002-02drv PE002-Harel PE002-Harel-v4.cls March 18, 2004 13:47 CHAPTER 2 Algorithms and Data or, Getting It Done And this is the fashion of which thou shalt make it GENESIS 6: 15 We already know that algorithms contain carefully selected elementary instructions that prescribe the basic actions to be performed. We have not yet discussed the arrangement of these instructions in the algorithm that enables a human or a computer to figure out the precise order of the actions to be performed. Nor have we discussed the objects manipulated by these actions. An algorithm can be thought of as being executed by a little robot, or a processor (who might appropriately be named Runaround). The processor receives orders to run around doing this and that, where the “this and thats” are the basic actions of the algorithm. In the salary summation algorithm of the previous chapter, little Runaround is told to make a note of 0 and then to start working its way through the employee list, finding salaries and adding them to the noted number. It should be quite obvious that the order in which the basic actions are carried out is crucial. It is of paramount importance not only that the elementary instructions of the algorithm be clear and unambiguous, but that the same should apply to the mechanism that controls the sequence in which those instructions are carried out. The algorithm must therefore contain control instructions to “push” the processor in this or that direction, telling it what to do at each step and when to stop and say “I’m done.” ■ Control Structures Sequence control is usually carried out with the aid of various combinations of instructions called control-flow structures, or simply control structures. Even the chocolate mousse recipe contains several typical ones, such as the following: ■ Direct sequencing, of the form “do A followed by B,” or “do A and then B.” (Every semicolon or period in the recipe hides an implicit “and then” phrase, for example, “gently fold in chocolate; [and then] reheat slightly ...”) 19

20 I.Preliminaries Conditional branching,of the form"if O then do A otherwise do B,"or just"if o then do A,"where O is some condition.(For example,in the recipe"reheat slightly to melt chocolate,if necessary,"or"serve with whipped cream,if desired.") As it happens,these two control constructs,sequencing and branching,do not ex- plain how an algorithm of fixed-maybe even short-length can describe processes that can grow increasingly long,depending on the particular input.An algorithm containing only sequencing and branching can prescribe processes of some bounded length only,since no part of such an algorithm is ever executed more than once.Con- trol constructs that are responsible for prescribing ever-longer processes are indeed hidden even in the mousse recipe,but they are far more explicit in algorithms that deal with many inputs of different sizes,such as the salary summation algorithm They are generically called iterations,or looping constructs,and come in many flavors.Here are two: Bounded iteration,of the general form"do A exactly N times,"where N is a number. Conditional iteration,sometimes called unbounded iteration,of the form"re- peat A until O,"or"while o do A,"where o is a condition.(For example,in the recipe "beat egg whites until foamy.") When describing the salary summation algorithm in Chapter 1,we were quite vague about the way the main part of the algorithm was to be carried out;we said "proceed through the list,adding each employee's salary to the noted number,"and then"having reached the end of the list,produce the noted number as output."We should really have used an iteration construct,that not only makes precise the task of the processor proceeding through the list,but also signals the end of the list.Let us assume then that the input to the problem includes not only the list of employees,but also its length;that is,the total number of employees,designated by the letter N.It is now possible to use a bounded iteration construct,yielding the following algorithm: (1)make a note of 0;point to the first salary on the list; (2)do the following N-1 times: (2.1)add the salary pointed at to the noted number: (2.2)point to the next salary: (3)add the salary pointed at to the noted number: (4)produce the noted number as output. The phrase "the following"in clause (2)refers to the segment consisting of subclauses (2.1)and(2.2).This convention,coupled with textual indentation to emphasize the"nested"nature of(2.1)and(2.2),will be used freely in the sequel. You are encouraged to seek the reason for using N-1 and adding the final salary separately,rather than simply using N and then producing the output and halting. Notice that the algorithm fails if the list is empty (that is,if N is 0),since the second part of clause (1)makes no sense. If the input does not include N,the total number of employees,we must use a conditional iteration that requires us to provide a way by which the algorithm can

P1: GIG PE002-02drv PE002-Harel PE002-Harel-v4.cls March 18, 2004 13:47 20 I. Preliminaries ■ Conditional branching, of the form“if Q then do A otherwise do B,” or just “if Q then do A,” where Q is some condition. (For example, in the recipe “reheat slightly to melt chocolate, if necessary,” or “serve with whipped cream, if desired.”) As it happens, these two control constructs, sequencing and branching, do not explain how an algorithm of fixed—maybe even short—length can describe processes that can grow increasingly long, depending on the particular input. An algorithm containing only sequencing and branching can prescribe processes of some bounded length only, since no part of such an algorithm is ever executed more than once. Control constructs that are responsible for prescribing ever-longer processes are indeed hidden even in the mousse recipe, but they are far more explicit in algorithms that deal with many inputs of different sizes, such as the salary summation algorithm. They are generically called iterations, or looping constructs, and come in many flavors. Here are two: ■ Bounded iteration, of the general form “do A exactly N times,” where N is a number. ■ Conditional iteration, sometimes called unbounded iteration, of the form “repeat A until Q,” or “while Q do A,” where Q is a condition. (For example, in the recipe “beat egg whites until foamy.”) When describing the salary summation algorithm in Chapter 1, we were quite vague about the way the main part of the algorithm was to be carried out; we said “proceed through the list, adding each employee’s salary to the noted number,” and then “having reached the end of the list, produce the noted number as output.” We should really have used an iteration construct, that not only makes precise the task of the processor proceeding through the list, but also signals the end of the list. Let us assume then that the input to the problem includes not only the list of employees, but also its length; that is, the total number of employees, designated by the letter N. It is now possible to use a bounded iteration construct, yielding the following algorithm: (1) make a note of 0; point to the first salary on the list; (2) do the following N − 1 times: (2.1) add the salary pointed at to the noted number; (2.2) point to the next salary; (3) add the salary pointed at to the noted number; (4) produce the noted number as output. The phrase “the following” in clause (2) refers to the segment consisting of subclauses (2.1) and (2.2). This convention, coupled with textual indentation to emphasize the “nested” nature of (2.1) and (2.2), will be used freely in the sequel. You are encouraged to seek the reason for using N − 1 and adding the final salary separately, rather than simply using N and then producing the output and halting. Notice that the algorithm fails if the list is empty (that is, if N is 0), since the second part of clause (1) makes no sense. If the input does not include N, the total number of employees, we must use a conditional iteration that requires us to provide a way by which the algorithm can