Lecture
Это окончание невероятной информации про алгоритм.
...
thought through.}
A defining feature of a computational process is the possibility of dividing it into separate, discrete, actions, which cannot be said of a continuous process. In a discrete process, the Jackdaw cannot ask its fateful question while the knocking continues. Strictly speaking, "knock-knock" does not, from the algorithm's point of view, have any extension in time. This event is instantaneous; otherwise we would have divided it into k separate "knocks," and the step numbers, starting from the third, would have increased by k-1.
Fig. 1
Fig. 2
Thus, the second feature is the sequence of actions in the process, formulated as instructions of the algorithm. Here again there is an important limitation: so-called parallel algorithms remain outside the scope of discussion.
The number of instructions must be finite; in the algorithm given above there are seven. Each of them individually must be precise and admit no ambiguous interpretation. For instance, the question "who's there?" is addressed to a perfectly definite source of the knocking, located outside the house near the door.
A precise instruction invokes a step of the algorithm. Individual instructions may be executed repeatedly, so the finiteness of the set of instructions in an algorithm by no means guarantees that it will necessarily terminate. Thus, if the postman and/or his interlocutor have hearing problems, the number of steps of the algorithm will not only exceed the number of instructions but may even threaten to become infinite (of course, only theoretically: someone's nerves will give out before that). Therefore the mandatory requirement is that the entire process, including all steps from start to completion, must be finite. Let us note in passing that the theory of algorithms also considers so-called infinite algorithms, but they will not fall within our field of view.
Generally speaking, it is not so essential whether the process, according to the algorithm, is carried out specifically by a computer. The content of the instructions is such that they can be carried out by a human, and sometimes even, as we have seen, by almost ordinary jackdaws. The difference, if we bear in mind the actual achievement of the result, lies only in the time required for execution of the algorithm. Consequently, one needs to distinguish the theoretical "instantaneousness" of an algorithm's step from the real time of its execution by a computing device. And even a computer may find itself unable to cope with an algorithm consisting of a finite, but so large, number of steps that the "customer" will practically never live to see it finish.
Naturally, the process must pursue a specific goal, without which posing a problem with algorithmic content would be meaningless. Thus, we would not risk classifying an aimless process of "pouring from empty into void" as algorithmic.
Moreover, the goal must be achievable. The deaf Pechkin, as we have already established, is forced to knock on the door forever, never delivering the letter. Fortunately, when dealing with the range of problems of discrete mathematics, there is nothing to worry about, since for them the very fact of the existence of a solution, that is, of an algorithm for achieving the stated goal, is rarely called into question.
However, the developer should carry out an analysis of the algorithm in order to assess how large the number of steps turns out to be. The Jesuit order's motto - "the end justifies the means" - does not apply here.
As Knuth writes, "a programmer can learn a lot from a good cookbook." He probably meant that such reading would make for good practice in searching for errors and inaccuracies related, among other things, to the difference between everyday and "computer" notions of an algorithm. Well then, following the recommendation, let us do a bit of practicing.
I take from the shelf one of the books suitable for the occasion - I happened to get "Meat and Mushroom Dishes" (1984). I open it at random: page 45. The recipe, if you are not a vegetarian, looks appealing: "roast beef (roast beef)." It's not hard to guess that at the output of the culinary process a ready-to-eat roast beef is expected, which constitutes the goal formulated in the recipe's title.
It is difficult to imagine an algorithm without output data: what would be the point of it then? And yet let us take the risk. Let us recall the myth of Sisyphus: the goal of the process was not rolling the stone to the top of the mountain, but the punishment of the wicked man. Had Zeus shown a bit more humanity, the lifelong punishment could have been replaced by a fixed number of algorithm steps. If it is necessary to delay the main computational process, one can add inside it, as a separate step, a call to a procedure that performs a given number of some operations with an unclaimed result. This subprocess does not produce output data. However, you may disagree with the proposed interpretation, treating the very fact of the subprocess's completion as the output value, since that was precisely the purpose of launching it.
As for input information, it is indeed not required by every algorithm. In our recipe, input data is present - these are the listed ingredients: 1 kg of beef (fillet or loin), 50 g of fat, salt, pepper, 30 g of butter, horseradish, water. In Pechkin's bag one can also find them (not food products, but input data!) - this is the letter that the postman is going to hand to the addressee. But in the task "draw a square of arbitrary size using a compass and a straightedge," only the final result is specified, while at the input - there is nothing.
Besides input and output data, as a rule, an algorithm involves the temporary formation of intermediate data, which will again be submitted for processing. The original 50 g of fat, once the cook melts it in the pan, passes, according to the laws of physics and cooking, into an intermediate state.
The same recipe goes on for about half a page describing the technological process, which we will not quote here for fear the reader will forget the main subject of discussion while drooling. Let us dwell only on a few imprecise instructions that carry incomplete information. Here is one of them: "fry the fillet for 20-25 minutes." So is it 20 or 25? Without proper cooking experience, which is nowhere reflected in the description, there remains a definite risk of completing the "algorithmic processing" with an inedible result.
To rule out such an outcome of the computational process, an algorithm must be constructed so that each of its steps is strictly defined, anticipating every possible state of the process and the corresponding instructions for handling it. Only such an algorithm guarantees an unambiguous production of the required result and is classified as deterministic. Of such an algorithm one can assert that its repeated application to identical input data always leads to the same outcome.
In contrast to a deterministic algorithm, a stochastic algorithm contains a degree of uncertainty in the choice of the next instruction. Such was the random choice of the roast recipe: repeating the manipulation with the cookbook, I would most likely open it to a different page. But this does not mean that the computing device is threatened with the fate of Buridan's ass and might slip into a state of lethargic pause. On the contrary, the choice of a particular instruction certainly does occur, only on the basis of a probabilistic mechanism. Here the algorithm's designer plans that, regardless of the branch chosen, the final result will satisfy the conditions of the stated problem. Thus, our semi-finished piece of meat will not be harmed by either 20 minutes of frying, or 25 minutes, or any value in between, and in the end the customer will indeed get a roast beef.
When listing the essential properties of an algorithm, one often includes "mass character" among them, meaning the ability to apply it "to solving problems of the same type." The universality of this requirement is doubtful, since a "one-off" purpose for some algorithms seems quite reasonable. For example, having told your friends a joke, would you retell it to the same audience? Would you manage to repeat the process in another company without the slightest deviation? And I do not know how else to interpret "sameness of type" here.
If we speak only of computational procedures, then as a counterexample I propose a computer program that exists in a single copy on a hard drive. Once launched, it formats the drive, thereby erasing itself as well, which makes repeated execution of the algorithm impossible.
Finally, to skeptical readers who doubt the legitimacy of the above examples for refuting the property of "mass character," I propose carrying out the algorithmic
Exercise 1
As is known from the wonderful book by L. Lagin, Old Man Hottabych once had an unpleasant incident: he ate a great deal of ice cream and, as a result, caught a bad cold. Suppose, for simplicity, that one step of the algorithm is performed every 5 minutes: another portion is eaten (in reality, the old man polished off the entire stock of ice cream in five minutes). Calculate (the process is computational!) how many algorithmic steps you would need to achieve the same result (Hottabych was "satisfied" with 43 portions). If there turn out to be at least a couple of readers who have matched or surpassed Hottabych's glorious achievement, the author is prepared to grant the algorithm in question the property of mass character.
Часть 1 Algorithm: Concept, Terminology, Properties, and Notation
Часть 2 See also - Algorithm: Concept, Terminology, Properties, and Notation
Comments