Algorithm. Its types and properties. What are algorithms and why are they needed? What is an algorithm concept?

Solving a problem using a computer begins with drawing up an algorithm. What is an algorithm?

The origin of the term “algorithm” is associated with the name of the great mathematician Muhammad al-Khwarizmi (763–850), who developed the rules for performing four arithmetic operations.

According to GOST 19781-74:

An algorithm is a precise prescription that defines a computational process leading from varying initial data to the desired result.

That is algorithm – this is a clear instruction to the executor of the algorithm to perform a certain sequence of actions to solve the task and obtain the result.

Developing an algorithm means breaking down a problem into a specific sequence of steps. The algorithm developer is required to know the features and rules of composing algorithms.

Main features of the algorithms:

Availability input source data.

Availability output the result of executing the algorithm, since the goal of executing the algorithm is to obtain a result that has a very specific relationship to the original data.

The algorithm must have discrete structure , i.e. the algorithm is presented as a sequence of steps, and the execution of each next step begins after the completion of the previous one.

Unambiguity – each step of the algorithm must be clearly defined and should not allow arbitrary interpretation by the performer.

Limb – execution of the algorithm must be completed in a finite number of steps.

Correctness – the algorithm must specify the correct solution to the problem.

Mass character (generality) – an algorithm is developed to solve a certain class of problems that differ in the initial data.

Efficiency - the algorithm must execute in a reasonable finite time. In this case, the simplest and shortest way to solve the problem is selected, subject, of course, to all restrictions and requirements for the algorithm.

Ways to write algorithms

The developed algorithm can be presented in several ways:

in natural language (verbal recording of the algorithm);

in the form of block diagrams (graphic form);

in a programming language.

Verbal recording of the algorithm. The verbal form is usually used to describe algorithms designed performer - person. The commands are written in plain language and executed in order. Commands may use formulas and special notations, but each command must be understandable to the performer. The natural order of commands can be disrupted (if, for example, a transition to the previous command is required or it is necessary to bypass the next command under some condition), in this case the commands can be numbered and the command to which you want to go is indicated. For example, go to step 3 or repeat from step 4.

Graphic form. Algorithms are presented in the form of block diagrams. There are special standards for constructing block diagrams, where graphic images of blocks are defined. Algorithm commands are written inside blocks in ordinary language or using mathematical formulas. Blocks are connected according to certain rules by communication lines that show the order in which commands are executed.

In a programming language. If an algorithm is developed to solve a problem on a computer, then in order for it to be executed performer - computer, it must be recorded in a language understandable to this performer. For this purpose, many programming languages ​​have been developed to solve problems of different classes. Writing an algorithm in a programming language is called program.

a l g o r i f m) is one of the basic concepts of logic and mathematics. By A. we mean an exact instruction that specifies the calculation. a process leading from initial data, which may vary, to the desired result. The words “computing” and “computational” that appear above should not be understood in the narrow sense of digital computing. Thus, already in the school algebra course they talk about letter calculations, and although here letters also play the role of substitutes for numbers, already in arithmetic. In calculations, symbols appear that do not denote any quantities: brackets, equal signs, arithmetic signs. actions. We can go further and consider calculations with arbitrary symbols and their combinations; It is in this broad sense that the term “computation” is understood when describing the concept “A.”. So, we can talk about A. translation from one language to another, about A. the work of a train dispatcher (processing information about the movement of trains into orders), and other examples of algorithmic. descriptions of control processes studied by cybernetics. MEANING OF A. The word “A” itself. dates back to the 9th century. (it comes from Algoritmi, which in turn is a Latin transliteration, apparently made in the 12th century, of the Arabic name of the Khorezmian mathematician al-Khwarizmi). Nowadays, the simplest A. appear already in elementary school - this is A. arithmetic. actions (in mid-century Europe A. was precisely what modern school arithmetic was called, i.e. the decimal positional number system and the art of counting in it, since al-Khwarizmi’s treatise was one of the first, if not the very first, thanks In addition, Europe became acquainted with the positional system). Let us emphasize that in elementary school it is A. accounts that are taught. When talking about a person’s ability to add numbers, what is meant is not that for any two numbers he will sooner or later be able to find their sum, but that he knows a certain uniform method of addition applicable to any two specific records of numbers, i.e. e., in other words, A. addition (an example of such A. is the well-known A. addition of numbers in a “column”). A. are found in science at every step; the ability to solve a problem “in general form” always means, in essence, mastery of a certain A. The concept of a problem “in general form” is clarified using the concept of a mass problem. The term “problem” can be understood as the task of finding an object that has certain properties; this object is called solution to a problem (in particular, for the problem of finding an answer to a question, the solution is the answer “yes” or “no” to the question posed). A problem is insoluble if it has no solution, i.e. there is no object that has the required properties. It is clear, therefore, that the unsolvability of the problem does not provide grounds for agnosticism. conclusions; on the contrary, establishing the unsolvability of a specific problem is an important cognition. Act. A mass problem is defined by a series of separate, “single” problems and consists of the requirement to find a general method (i.e. A.) for solving them. The unsolvability of a mass problem means the impossibility of finding correspondences. A. Mass problems are extremely characteristic and important for logic and mathematics. Even the solution of single problems is often valuable precisely because it simultaneously provides a general method for solving a whole class of problems; at the same time, the formulation of a mass problem means the transformation of a certain class of problems into a single problem - the problem of finding an answer to solve all the problems of this class; here the connection between such categories of dialectics as the individual, the particular and the universal is manifested. The role of mass problems determines the meaning of A. Establishing the unsolvability of a particular mass problem (i.e., the absence of a single algorithm that allows one to find solutions to all individual problems of a given series) is the most important cognitive act, showing that To solve specific individual problems, methods specific to each such problem are fundamentally needed. The existence of insoluble mass problems serves, therefore, as a concrete embodiment of the inexhaustibility of the cognition process. Contain. the phenomena that formed the basis for the formation of the concept “A.” have long occupied an important place in science. Many problems that arose in mathematics and logic consisted in the search for certain constructive methods. The search for such methods, especially intensified in connection with the creation of convenient mathematical and logical symbolism, as well as understanding the fundamental absence of these methods in a number of cases - all this was a powerful factor in the development of science. knowledge. The realization of the impossibility of solving any problem by direct calculation led to the creation in the 19th century. set-theoretic. concepts. Only after a period of rapid development of this concept (within the framework of which the question of constructive methods in their modern understanding does not arise at all) it became possible in recent decades to return again to questions of constructivity, but at a new level, enriched by the crystallized concept of “A.” (another illustration of Lenin’s position on the spiral-shaped nature of the development of knowledge). And although the concept "A." is not such a far-reaching abstraction as, say, the concept of “set”, it cannot be considered accidental that historically the first of these concepts arose later than the second. EXAMPLES A. Similar to the concepts “set”, “correspondence”, “natural number”, “relation”, etc., the concept “A.” is the primary logical-mathematical concept (one of the categories of logic and mathematics). It does not allow formal definition through simpler concepts, but (like other mathematical categories) is abstracted directly from experience. Concept "A." can only be learned through examples. Example 1. Possible initial data are finite non-empty combinations made up of sticks (I), i.e. objects I, II, III, etc. A. consists of the following. rules (which must be followed starting from rule 1°): 1°. Underline the leftmost stick below and proceed to the 2° rule. 2°. Place the rightmost stick on top and proceed to the 3° rule. 3°. Examine the underlined stick and, if it is not underlined, proceed to the 4° rule. 4°. Consider the stick immediately following the underlined one; if it is not underlined, proceed to the 5° rule; if it is underlined, proceed to the implementation of the 7° rule. 5°. Move the bottom line from the underlined stick to the next one immediately after it and proceed to the 6° rule. 6°. Move the top line from the crossed stick to the one immediately preceding it and proceed to the implementation of the 7° rule. 7°. Erase the crossed stick and all the sticks following it and proceed to the 8° rule. 8°. Erase the bottom line of the underlined stick; what happened is the result. Applying this A. to the combination ||||, taken as the initial data, we obtain sequentially: by rule 1° – |||, by rule 2° – ? || , according to the rules 3°, 4°, 5° – | ? | , according to the rules 6°, 3°, 4° – | ? | according to the 7° rule – | ?, according to the 8° rule – || (result). If we try to apply A. to the combination |||, we get: according to the 1° rule – ? ||, according to the 2° rule – ? | , according to the rules 3°, 4°, 5° – | ? , according to the 6° rule – | I |, then you need to proceed to the implementation of the 3° rule, but the 3° rule is feasible only on the condition that the underlined stick is not underlined. Thus, for the current situation, A. does not contain instructions on how to proceed; the so-called ineffective stop (a stop that is not accompanied by a result). It is easy to notice that in general it was formulated. A. gives the result when applied to any combination of an even number of sticks, and the result in this case is a combination consisting of half the number of sticks; A. does not give any result when applied to any combination consisting of an odd number of sticks. Example 2. In logic and mathematics, any finite set of signs is called. “alphabet”, the signs included in it are “letters” of the alphabet, and the final (including empty) sequence of letters written one after another k.-l. alphabet called "word" in this alphabet. For example, Arabic numerals form an alphabet, and every decimal representation of an integer is a word in this alphabet. Consider the alphabet (a, b) of two letters: a and b. Examples of words in this alphabet are: v, aw, vva aaavavv, etc. Let us agree to call the transition from a word in this alphabet to another word in the same alphabet “admissible” according to one of the following. two rules: 1) if the word has the form aP, where P is an arbitrary word, go to the word Pb; 2) if the word looks like va?, where? – any word, go to the word Rava. Next, a trace, an instruction, is formulated: “starting from a k.-l. word (taken as initial data), make admissible transitions until you get a word of the form aa?; when a word of this type is obtained, discard the first two letters, and what remains is the result." Since at most one transition rule is feasible each time, we formulate the prescription forms an alphabet, the possible initial data of which are words in the alphabet (a, b). Let's take the word vavaa as initial data. According to rule 2 we get waaava. Applying rule 2 again, we get aavaava. By virtue of our instructions, we must stop; the result (of applying A. to the word vavaa) is vavaa. Let's take the word vaava as initial data. By rule 2 we get avaava. By rule 1 we get vaavav. Next we get sequentially avavava, vavavav, vavavava, etc. It can be proven that the process will never end (i.e., a word starting with two letters a will never appear, and for each of the resulting words it will be possible to make a valid transition). Thus, A. does not give any result when applied to the word vaava. Let's take the word vaav as initial data. We get vaavv, avvav, vvavav in sequence. Further, none of the rules 1 and 2 are feasible, and at the same time the result did not work out. Therefore, when applied to the word awaav, A. also does not produce results. The main features of A. According to A. A. Markov, A. is characterized by the following main features. features: a) definiteness of algorithmic. prescription, which consists in its accuracy and general intelligibility that leaves no room for arbitrariness (due to this certainty of prescription, the algorithmic process is deterministic: each stage of the process uniquely determines the next stage); b) the mass, which consists in the possibility for each A. proceed from initial data varying within certain limits; c) effectiveness, which consists in its focus on obtaining the desired result. The determinism of A. ensures the possibility of communication by one person to another person so that this other person will be able to perform A. without the participation of the first; This same property of determinism makes it possible to transfer the execution of A. to a machine. The mass nature of analysis presupposes that there is a certain set (for each analysis its own) of possible initial data. How this totality is set is another question. We can assume that the set of possible initial data corresponding to any A. is not specified separately from the A., but is indicated by natural. image by the very content of this A. (for example, for A. addition by a column, the corresponding set consists of all pairs of records of numbers in the decimal system). When a specific object is selected as the initial data of A., then we talk about applying A. to this object. If A. gives a result when applied to a certain object, then they say that it is applied to this object. The effectiveness of A. does not mean at all that A. must be applicable to any object from the corresponding set of possible initial data (see examples 1 and 2). It is appropriate to note here that it is possible to construct such an algorithm for which there is no A. which would recognize from arbitrary initial data of the first A. whether the first A. is applicable to them or not. Basic abstractions of the theory of A. In scientific. In practice, a number of specific features have developed. for mathematics and logic abstractions. These are, first of all, the abstraction of actual infinity, the abstraction of identification, the abstraction of potential realizability. Sov. scientist A. A. Markov showed that the last two are necessary when considering A. Algorithm. the process is divided into departments. steps, each of which is assumed to be so elementary that its possibility is factual. implementation is beyond doubt. At the same time, the number of these elementary steps required to obtain a result can be so large that achieving the result can be considered practically impossible. However, the idea of ​​practical the feasibility or impracticability of a particular number of steps is relative. It changes with the development of computing. means (in principle, the idea of ​​the elementary nature of a particular step may also change). In the theory of A., therefore, they abstract from “practical feasibility” and consider any finite number of steps feasible. Thus, when studying A. allow the abstraction of potential feasibility, which consists in abstraction from the real boundaries of our capabilities. The development of high-speed electronic computing. machines are quickly pushing these boundaries further and further. What was only potentially feasible yesterday becomes practically feasible today. This brings the theory of arithmetic closer to the practice of computing. machines and allows these two disciplines to mutually enrich each other. Transferring tasks to the machine to s/l. series is impossible without preliminary. drawing up A. decisions. The compilation of such an A., as a rule, is of fundamental importance (for example, in the problem of machine translation, the main thing is the compilation of an A. translation). Abstraction of potential feasibility is necessary when considering not only algorithmic ones. processes, but also the objects themselves participating in these processes (including “initial data” and “results”). So, in order to talk about any natural number (more precisely, about writing this number, say, in the decimal system), we must allow ourselves to consider the records of numbers so large that these records would not fit on the globe; thus, and here, abstracting from the physical. feasibility of such a record, use the abstraction of potential feasibility. In general, it is necessary to resort to the abstraction of potential feasibility in order to reason about arbitrarily long words in a given alphabet. Objects, the construction and consideration of which are possible within the framework of the abstraction of potential feasibility (when contrasted with the abstraction of actual infinity), called. constructive objects. These are the natural numbers represented by their entries in k.-l. their notation system, words in a given alphabet, etc., as well as pairs, triplets and generally finite sequences made up of records of numbers, words in the alphabet, etc.; rational numbers (which can be represented as triplets of natural numbers), etc. So-called expressions are also constructive objects. calculus, or formal systems, which makes it possible to apply the apparatus of the theory of A to the latter. Any A. (understood as a prescription) can (after writing this prescription in the form of a combination of some symbols) be considered as a constructive object. On the contrary, objects, the consideration of which is impossible without involving the abstraction of actual infinity, are not among the constructive objects. So, for example, constructive objects are not real numbers (in the sense of Cantor, Dedekind or Weierstrass), geometric. points (since the analysis of such an abstraction as “point” leads to the idea of ​​a point as an actually infinite system of small bodies), etc. Structural objects are grouped naturally. way in the aggregate, examples of which are the collection of all words in a given alphabet and, in general, any collection of all objects of a class. "type" from the list. above types of structural objects. Each such set of structural objects is specified by the method of constructing the objects belonging to it. Other basic The abstraction used when considering constructive objects and architecture is the abstraction of identification. In some cases, two objects are spoken of as identical. The conditions of “sameness” are established each time in relation to a given situation. So, for example, when a person makes calculations on paper, the font in which the numbers are written is usually indifferent, and the entries 1647 and 1647 are considered the same; however, one can imagine situations where the difference between roman and italic fonts is significant (as, for example, in the perception of words found in this Philosophical Encyclopedia). Then the two records will already be considered as unequal, but records 1647 and 1647 will still - in ordinary cases - be the same (although physically these are different objects). It is usually accepted that constructive objects consist of certain fairly simple “elementary parts” (just as words are made of letters) and two constructive objects are considered the same if they consist of identical elementary parts arranged in the same order. Without the concept of “sameness”, on the basis of which, for example, numbers written in chalk on a blackboard and numbers written in ink in a notebook are considered the same, learning is impossible. The abstraction of identification allows us to talk about identical objects as one and the same object. It leads to the formation of the concept of an “abstract object”: namely, two identical concrete objects are considered representatives of the same abstract object. Each A. applied to identical objects also leads to identical objects. Therefore, we can assume that each A. specifies the process of transforming abstract constructive objects. This property of A. (together with determinism) determines their repeatability or reproducibility: having been developed in the form of A. over abstract constructive objects, A. can be repeatedly reproduced for any specific constructive objects permissible for a given A. From the above it should become clear that the initial data is the same as the end data. results arising from the implementation of k.-l. A., they are always constructive objects (every “state” algorithmic. process is a constructive object!). The impossibility of even potentially feasible processes on non-constructive objects is also associated with the lack of a way to recognize them as identical or different (cf. the well-known position of cybernetics about the advantages of discrete forms of information storage over continuous ones). There are various views. regarding the methods permissible in the study of A. One of them, put forward by representatives of the constructive direction in mathematics and logic, is that since for the formation of the concept of A. the abstractions of identification and potential feasibility are sufficient, then the development of the theory of A. should be carried out within the framework of these abstractions. Another view allows for the study of A. any methods generally permitted in logic and mathematics, incl. and requiring the abstraction of actual infinity. Thus, one can imagine a case when, in order to prove that a certain A., when applied to a certain object, will give a result, it will be necessary to use the law of excluded middle, which is closely related to the abstraction of actual infinity. Basic concepts of the theory of A. Among the basic ones. concepts that arise on the basis of the concept of arithmetic include the concepts of a computable function, a solvable set, and an enumerable set. The function is called computable, as long as there is an algorithm that calculates this function in the following way. sense: a) A. is applicable to any object included in the domain of definition of the function, and gives as a result the value of the function that it takes for this object taken as its argument; b) A. is not applicable to any object not included in the scope of the function. A set located in a certain collection of constructive objects (i.e. a set composed of some objects of this collection) is called. solvable (relative to the enclosing set), as long as there is an A. that resolves this set (relative to the specified set) into the next. sense: A. is applicable to any object from the encompassing set and gives as a result an answer to the question whether this object belongs to the set under consideration or not. Finally, a non-empty set (see empty) is called. enumerable, as long as there is an A that enumerates this set in the next. sense: a) the result of applying A. to any natural number exists and belongs to the set under consideration; b) each element of the set under consideration can be obtained as a result of applying arithmetic to some natural number. By definition, the empty set is also usually classified as enumerable. The same computable function (respectively, a solvable set, an enumerable set) can be calculated (respectively, resolved, enumerated) by means of different A. From the definitions it follows that the arguments and values ​​of a computable function, elements of a solvable or enumerable set are always constructive objects. Replacing constructive objects (a certain swarm of fixed aggregates) with their numbers in an arbitrary algorithmic numbering (i.e., such a numbering for which there is an algorithm for obtaining its number from an object and vice versa), one can, as is often done in the theory of arithmetic, limit ourselves to considering only such computable functions, the arguments and values ​​of which are natural numbers, and only such solvable and enumerable sets, the elements of which are also natural numbers. It can be proven that every solvable set is enumerable. At the same time, it was possible to construct an enumerable but not solvable set. This first concrete example (published by the American scientist A. Church in 1936 in the article “One Unsolvable Problem in Elementary Number Theory”) of the absence of an algorithm (namely, an algorithm resolving the constructed set) was the source or example of almost all further examples of this kind. It turned out that a set is solvable if and only if both it and its complement (to the enclosing set of objects) are enumerable. Thus, there are complements to enumerable sets that are themselves non-enumerable. The connection between the theory of logic and logic. The concepts of decidable and enumerable sets are closely related to the classification of definitions (we limit ourselves here to only such definitions, each of which defines objects of a certain type or, what is the same, a certain class of objects). As you know, there are two main ones. definition schemes: “through genus and species difference” and “by induction”. When defining “through genus and specific difference,” a certain encompassing set of objects (“genus”) is specified and a feature (“species difference”) is indicated that distinguishes among the objects a decree, a collection of the class of defined objects. If; consider that this definition is constructive, i.e. that objects are constructive and that the presence or absence of species difference in an element of the genus is algorithmically recognizable, then the defined set turns out to be decidable (and every decidable set can be defined in this way). Thus, soluble sets are identified with sets that are constructively defined through genus and specific difference. The definition “by induction” consists of two parts: the basic part, containing a certain list of objects that are declared to belong to the class being defined, and the inductive part, which states that if objects of such and such a kind belong to the class being defined , then objects of such and such a type, connected with the first objects by a certain relation, also belong to the defined class. (More complex cases of so-called cross definitions are also possible, when several classes of objects are simultaneously defined through each other). If we assume the definition is constructive, i.e. objects are constructive, the list of initial objects contained in the basic part is finite, and the rules for transition from already defined objects to new algorithmic ones contained in the inductive part (in the sense that the presence or absence of the relation discussed in the inductive part is recognized through some kind of A.), then we come to the concept of a set constructively defined by induction, or (synonym) an effectively generated set (since such a definition specifies an effective generating process, at certain stages of the development of which defined objects "emerge" or "are generated"). An example of a constructive definition by induction is the definition of admissible chess positions (that is, positions that can appear on the board during the game). The base part contains one unit. starting position. The inductive part contains the rules for the moves of the pieces. The set of admissible positions is thus effectively generated. Another example of an effectively generated set is the set of all provable formulas of a k.-l. formal system or calculus: the basic part of the definition of provable formulas contains axioms, the inductive part contains rules of inference (axioms are declared provable by definition and then it is said that if any formulas are provable, then the formulas obtained from them according to the rules of inference are also provable). The generating process here is the process of proving all provable formulas. Finally, the process of refuting all falsifiable formulas in calculus is also an example of an effective generative process. The concept of an effective generative process is very closely related to the concept of A. We have given a definition (approximate) of an effective generative process based on the concept of A. In turn, the concept of a generative process allows us to define on its basis, if not the concept of A itself, then, in any case , the concept of a computable function. Indeed, let a certain generating process be capable of “generating” objects that have the form of pairs (x, y), and let any two “generated” pairs with coinciding first terms also have the same second terms. Then the process follows. defines the function y = f(x) in this way: the function is defined for the object x0 if and only if x0 is the first member of the c.-l. generated pair: the value of the functions for the argument x0 is in this case equal to the second member of this pair. The function defined in decree. in the sense of an effective generating process, it is obviously computable [to find f(x0), we need to expand the process until we find pairs with x0 as the first term]. Conversely, every computable function can be defined by an efficient generating process. Algorithmic processes and generating processes are close to each other logically. points of view. Each of them is based only on constructive concepts. The difference between them is that the algorithmic the process unfolds on the basis of a requirement, and the generative process unfolds on the basis of permission to act in a certain way. Here the difference between the necessary and the possible is manifested (in an algorithmic process, each stage is uniquely, i.e. necessarily, determined by the previous stage, while when the generative process unfolds after each stage, only a multitude of possibilities arise for the next stage). With proper refinements of the concept of an effective generating process, it turns out that every effectively generated set is enumerable, and vice versa. This circumstance, combined with the above relationships between enumerable and decidable sets, allows us to conclude the following. Any class of objects that admits a constructive definition through genus and specific difference also admits a constructive definition by induction, but not vice versa: there is a class of objects that is constructively defined by induction, but does not allow a constructive definition through genus and specific difference; addition to this class of objects (over the enclosing set of structural objects) does not allow for effective inductive definition. Each constructive generative process can be represented as a process for obtaining provable formulas of a suitable calculus. Therefore, an example of a class that has the properties just described can be constructed as a class of all provable formulas of a certain calculus. Moreover, it turned out that this circumstance occurs for anyone who is sufficiently contained. calculus (for example, for the calculus of predicates or for calculi that formalize arithmetic), because if the calculus is sufficiently meaningful, then any effective generating process can be expressed in it. The class of all provable formulas of such a calculus (being, of course, enumerable) is not decidable, so there is no algorithm recognizing the provability of calculus formulas; in this sense the calculus is said to be undecidable. Since the class of all provable calculus formulas is not decidable, it will complement. to it, the class of all unprovable formulas is not enumerable and, therefore, cannot be obtained by any generating process; in particular, it is impossible to construct such a calculus, which would “refute” all unprovable formulas of the original. calculus and only them; Moreover, all these unprovable formulas cannot be refuted by the means of the original. calculus, so in the beginning. in calculus there are so-called undecidable (i.e., neither provable nor refutable) formulas. In these considerations we can limit ourselves only to such formulas, which contain. interpretations of calculus express meaningful (i.e., either true or false) propositions, and, therefore, find undecidable ones among such formulas. It follows from this that it is possible to present a formula that expresses a true judgment, but cannot be proven in calculus; in this sense the system is said to be incomplete. We emphasize that due to the general nature of the reasoning being carried out, the property of incompleteness is inherent in any sufficiently contained. calculus. The concept of undecidability of calculus is based on the concept of arithmetic, and it is not surprising that the fact of undecidability is established on the basis of research in the field of calculus theory. Very significant (and perhaps unexpected at first glance) is the fact that such a general logic. a fact like the incompleteness of calculations (a fact expressing the fundamental impossibility of completely formalizing the process of logical inference and first strictly proven by the Austrian scientist K. Gödel back in 1931, before the concept of “A.”) was clarified, can be obtained, as we have just seen, by means of the theory of arithmetic. This circumstance alone shows the enormous possibilities of applying the theory of arithmetic to questions of logic. These applications are not limited to the example given. Back in 1932 the Soviets. scientist A. N. Kolmogorov proposed an interpretation of the constructive logic created by intuitionists using contain. means that have nothing to do with the attitudes of intuitionism; namely, Kolmogorov proposed to interpret each sentence of constructive logic as a problem. The concept of a problem, however, required specification, which could only be given on the basis of the already developed theory of A. Two specific classes of problems suitable for the interpretation of constructive logic were proposed, respectively, by the Amer. scientist S.K. Kleene in 1945 and owls. scientist Yu. T. Medvedev in 1955. In 1956 owls. scientist N.A. Shanin put forward a new concept, according to which not every statement of constructive logic requires interpretation in the form of a problem. This circle of ideas includes the questions of “constructivization”, or “finding constructive analogues”, classical. mathematical concepts and proposals; the solution to these issues is also possible only on the basis of theory A. Constructivization of the basic. mathematical concepts analysis led to the so-called now being developed. constructive mathematical analysis. Ways of constructivization and other mathematical are outlined. theories. One of the main techniques used in constructivization is the transition from the objects being studied to their names, which are always constructive objects. SOLUTION PROBLEMS. A special case of mass problems are problem resolutions. Problems of resolving k.-l. of a set is the problem of constructing an algorithm that resolves this set. Corresponding a series of individual problems here consists of problems of answering the question of membership in a set posed for each object from the encompassing set of constructive objects. Conversely, any mass problem, respectively. a series of individual problems of answering a question, can be considered as a problem of solving a certain set, namely, the set of those individual problems, the answer to which is “yes”. This makes clear the important role of resolution problems. They were the ones who were studied from the point of view. their solvability. Among the solution problems, the problems posed for classes of provable calculus formulas stand out. The problem of resolving the class of all provable formulas of k.-l. calculus called also the problem of resolving the calculus itself. (In Russian texts, the problem of resolution is usually called the “problem of solvability”; however, the “problem of solvability” is better called the problem: “to answer whether a given problem has a solution.”). Unsolvable mass problems. The problem of permission for k.-l. In calculus there is always the problem of resolving an enumerable set. In general, all problems of resolution that naturally arose in mathematics turned out to be problems of resolution of enumerable sets. This is the above-mentioned first example of an insoluble solution problem (and at the same time the first example of an insoluble mass problem in general), published by Church in 1936. This is the so-called the identity problem for associative systems, proofs of the undecidability of the form were published in 1947 independently of each other by A. A. Markov and Amer. scientist E. L. Post; this result is of interest as the first example of proof of the unsolvability of a mass problem that arose (back in 1914) outside logic and theory. Such is the famous problem of identity for groups, posed back in 1912, the unsolvability of which was proven in 1952. scientist P. S. Novikov (Lenin Prize, 1957). Each of the problems of identity consists of finding an algorithm that establishes the equivalence or non-equivalence of two words in a given alphabet (whether we are dealing with an associative system or a group depends on one or another definition of equivalence). Therefore, the identity problem can be considered as a problem of resolving the set of all pairs of words equivalent to each other (relative to the set of all possible pairs of words). Moreover, since it is possible to specify a generative process for obtaining all pairs of words equivalent to each other, the set of all such pairs is enumerable. Consistency. Beginning with Church's example in 1936 and continuing through 1944, all proofs of the unsolvability of mass problems were carried out or could be carried out in the following way. uniform method. The obviously unsolvable problem studied by Church was reduced to the mass problem under consideration, so that if the mass problem in question were solvable, then Church's problem would also be solvable (in this sense, we can say that the proof of the undecidability of the problem under consideration was reduced to the proof of the undecidability of Church's problem). The question arose whether for any insoluble problem of solution its unsolvability can be established in this way. This question, called the reducibility problem, was posed by Post in 1944; At the same time, Post gave several examples of unsolvable problems of solution, the unsolvability of which was established by him using a method different from that described above (these examples did not yet solve the problem of reducibility, since the question remained open whether it was impossible for them to find such proofs of unsolvability, which were reduced to prove the unsolvability of Church's problem; subsequently, for some of the above examples, such proofs were actually found). The problem of reducibility was at the center of research on the theory of arithmetic until 1956, when it was solved independently by the Soviet Union. scientist A.A. Muchnik and Amer. scientist R. M. Friedberg. He constructed an example of an undecidable solution problem (for an enumerable set), the undecidability of which cannot be proven by reducing Church's problem to this problem. Muchnik showed even more, namely, that not only the Church problem, but no other problem can serve as a “standard undecidable problem” in the sense that the proof of the undecidability of any undecidable solution problem for an enumerable set could

a system of rules, formulated in a language understandable to the performer, which determines the process of transition from acceptable initial data to a certain result and has the properties of mass, finiteness, certainty, and determinism.

The word “algorithm” comes from the name of the great Central Asian scientist of the 8th-9th centuries. Al-Khorezmi (Khorezm historical region in the territory of modern Uzbekistan). Of Al-Khorezmi’s mathematical works, only two have reached us: algebraic (from the title of this book the word algebra was born) and arithmetic. The second book was considered lost for a long time, but in 1857 its translation into Latin was found in the library of Cambridge University. It describes four rules of arithmetic operations, almost the same ones that are used now. The first lines of this book were translated as follows: “Said Algorithm. Let us give due praise to God, our leader and protector.” So the name Al-Khorezmi became Algorithm, which is where the word algorithm came from. The term algorithm was used to designate four arithmetic operations, and it was in this meaning that it entered some European languages. For example, in the authoritative English dictionary Webster's New World Dictionary, published in 1957, the word algorithm is labeled "obsolete" and is explained as performing arithmetic operations using Arabic numerals.

The word “algorithm” again became used with the advent of electronic computers to denote a set of actions that make up a certain process. This implies not only the process of solving a certain mathematical problem, but also a culinary recipe and instructions for using a washing machine, and many other sequential rules that are not related to mathematics; all these rules are algorithms. The word “algorithm” is known to everyone these days; it has entered colloquial speech so confidently that now the expressions “algorithm of behavior”, “algorithm of success”, etc. are often found on the pages of newspapers and in the speeches of politicians.

Turing A. Can a machine think?? M., Mir, 1960
Uspensky V. Post's car. Science, 1988
Cormen T., Leiserson, Rives R. Algorithms. Construction and analysis. M., MTsNMO, 1999

Find "ALGORITHM" on

CONCEPT OF ALGORITHM. PROPERTIES OF THE ALGORITHM. TYPES OF ALGORITHMS. METHODS OF DESCRIBING ALGORITHMS

An algorithm is a precise and understandable instruction to a performer to perform a sequence of actions aimed at solving a given problem. The word “algorithm” comes from the name of the mathematician Al Khorezmi, who formulated the rules for performing arithmetic operations. Initially, an algorithm meant only the rules for performing four arithmetic operations on numbers. Later, this concept began to be used in general to denote the sequence of actions leading to the solution of any given task. When talking about the algorithm of the computational process, it is necessary to understand that the objects to which the algorithm was applied are data. An algorithm for solving a computational problem is a set of rules for converting source data into results.

Main properties algorithms are:

1. determinism (certainty). It assumes obtaining an unambiguous result of a computational process with given initial data. Due to this property, the process of executing the algorithm is mechanical in nature;
2. effectiveness. Indicates the presence of such initial data for which the computational process implemented according to a given algorithm must stop after a finite number of steps and produce the desired result;
3. mass character. This property implies that the algorithm should be suitable for solving all problems of a given type;
4. discreteness. It means the division of the computational process determined by the algorithm into separate stages, the ability of which to be performed by the performer (computer) is beyond doubt.

The algorithm must be formalized according to certain rules using specific visual means. These include the following methods of writing algorithms: verbal, formula-verbal, graphic, operator scheme language, algorithmic language.

The most widespread, due to its clarity, is the graphical (block diagram) method of recording algorithms.

Block diagram is a graphical representation of the logical structure of an algorithm, in which each stage of the information processing process is represented in the form of geometric symbols (blocks) that have a certain configuration depending on the nature of the operations performed. The list of symbols, their names, the functions they display, shape and dimensions are determined by GOSTs.

With all the variety of algorithms for solving problems, three main types of computational processes can be distinguished:

• linear;
• branching;
• cyclical.

Linear is a computational process in which all stages of solving a problem are performed in the natural order of recording these stages.

Branching is a computational process in which the choice of direction for processing information depends on the initial or intermediate data (on the results of checking the fulfillment of any logical condition).

A cycle is a section of calculations that is repeated many times. A computational process containing one or more cycles is called cyclical . Based on the number of executions, cycles are divided into cycles with a certain (predetermined) number of repetitions and cycles with an indefinite number of repetitions. The number of repetitions of the latter depends on the satisfaction of some condition specifying the need to execute the cycle. In this case, the condition can be checked at the beginning of the cycle - then we are talking about a cycle with a precondition, or at the end - then it is a cycle with a postcondition.

Every algorithm deals with data - input, intermediate and output.

Limb. It is understood in two ways: firstly, the algorithm consists of individual elementary steps, or actions, and there are many different steps that make up the algorithm, of course. Secondly, the algorithm must finish in a finite number of steps. If an infinite process is constructed that converges to the desired solution, then it breaks off at a certain step and the resulting value is taken as an approximate solution to the problem under consideration. The accuracy of the approximation depends on the number of steps.

Elementarity (understandability). Each step of the algorithm must be simple so that the device performing the operations can complete it in one step.

Discreteness. The process of solving a problem is represented as a finite sequence of individual steps, and each step of the algorithm is performed in a finite (not necessarily unit) time.

Determinism (certainty). Each step of the algorithm must be uniquely and unambiguously defined and should not allow arbitrary interpretation. After each step, it is either indicated which step to take next, or a stop command is given, after which the work of the algorithm is considered complete.

Productivity. The algorithm has a certain number of input quantities - arguments. The purpose of executing the algorithm is to obtain a specific result that has a very specific relationship to the original data. The algorithm must stop after a finite number of steps, depending on the data, with an indication of what to consider as the result. If a solution cannot be found, then it must be indicated what is considered the result in this case.

Mass character. The algorithm for solving the problem is developed in general form, i.e. it should be applicable for a certain class of problems that differ only in the initial data. In this case, the initial data can be selected from a certain area called area of ​​applicability of the algorithm.

Efficiency. The same problem can be solved in different ways and, accordingly, in different times and with different memory costs. It is desirable that the algorithm consists of a minimum number of steps and that the solution satisfies the accuracy condition and requires minimal expenditure of other resources.

The exact mathematical definition of the algorithm is complicated by the fact that the interpretation of the prescribed instructions should not depend on the subject performing them. Depending on his intellectual level, he may either not understand at all what is meant in the instructions, or, conversely, interpret it in an unintended way.

The problem of interpreting rules can be circumvented if, along with the wording of the regulations, the design and operating principle of the interpreting device are described. This avoids uncertainty and ambiguity in understanding the same instructions. To do this, it is necessary to specify a language in which many rules of behavior or a sequence of actions are described, as well as a device itself that can interpret sentences made in this language and carry out each precisely defined process step by step. It turns out that such a device (machine) can be implemented in a form that remains constant regardless of the complexity of the procedure in question.

Currently, three main types of universal algorithmic models can be distinguished. They differ in their starting assumptions regarding the definition of the concept of an algorithm.

First type connects the concept of an algorithm with the most traditional concepts of mathematics - calculations and numerical functions. Second type is based on the idea of ​​an algorithm as a certain deterministic device capable of performing only very primitive operations at any given moment. This representation ensures the unambiguity of the algorithm and the elementary nature of its steps. In addition, this idea corresponds to the ideology of building computers. The main theoretical model of this type, created in the 1930s. English mathematician Alan Turing, is a Turing machine.

Third type– these are transformations of words in arbitrary alphabets, in which the elementary operations are substitutions, i.e. replacing part of a word (a word is a sequence of alphabetic characters) with another word. The advantages of this type of model are its maximum abstraction and the ability to apply the concept of an algorithm to objects of arbitrary (not necessarily numerical) nature. Examples of models of the third type are the canonical systems of the American mathematician Emil L. Post and normal algorithms introduced by the Soviet mathematician A. A. Markov.

The models of the second and third types are quite close and differ mainly in heuristic accents, so it is no coincidence that they talk about Post’s machine, although Post himself did not talk about it.

A recording of an algorithm in some language is a program. If a program is written in a special algorithmic language (for example, PASCAL, BASIC or some other), then we talk about original program. A program written in a language that a computer can directly understand (usually binary codes) is called machine, or binary.

Any way of writing an algorithm implies that every object described with its help is specified as a specific representative of an often infinite class of objects that can be described in this way.

The means used to write the algorithms are largely determined by who will be the performer.

If the performer is a person, the recording may not be completely formalized; clarity and visibility come first. In this case, algorithm diagrams or verbal notation can be used for recording.

To write algorithms intended for automata performers, formalization is necessary, therefore, in such cases, formal special languages ​​are used. The advantage of the formal way of notation is that it makes it possible to study algorithms as mathematical objects; in this case, the formal description of the algorithm serves as the basis for intellectually grasping this algorithm.

A wide variety of means are used to write algorithms. The choice of tool is determined by the type of algorithm being executed. The following are distinguished: main ways to write algorithms:

■ verbal– the algorithm is described in human language;

■ symbolic– the algorithm is described using a set of symbols;

■ graphic– the algorithm is described using a set of graphic images.

The generally accepted ways of writing an algorithm are graphic recording using algorithm diagrams (flowcharts) and symbolic notation with using some algorithmic language.

To describe an algorithm, diagrams are used to depict a connected sequence of geometric figures, each of which implies the execution of a specific action of the algorithm. The order of actions is indicated by arrows.

The following types of graphic symbols are used in algorithm diagrams.

Start And end The algorithm is designated using the same symbols (Fig. 21.1).

Rice. 21.1.

An algorithm step associated with assigning a new value to a certain variable, transforming a certain value to obtain another value, is represented by the symbol "process"(Fig. 21.2).

Rice. 21.2.

The choice of direction for executing the algorithm depending on some variable conditions is represented by the symbol " solution"(Fig. 21.3).

Rice. 21.3.

Here R means predicate (conditional expression, condition). If the condition is satisfied (the predicate takes the value TRUE), then the transition is made to one step of the algorithm, and if not fulfilled, then to another.

There are primitives for data input and output operations, as well as other graphical symbols. Currently, they are defined by the GOST 19.701–90 (ISO 5807–85) standard “Unified system of program documentation. Schemes of algorithms, data programs and systems. Conventions and execution rules.” In total, the ESPD collection contains 28 documents.

Using the algorithm diagram, it is easy to compose an initial program in an algorithmic language.

Depending on the sequence of actions in the algorithm, algorithms of linear, branched and cyclic structure are distinguished.

In algorithms linear structure actions are performed sequentially one after another.

In algorithms branched structure Depending on the fulfillment or non-fulfillment of any condition, different sequences of actions are performed. Each such sequence of actions is called branch of the algorithm.

In algorithms cyclic structure depending on the fulfillment or non-fulfillment of any condition, a repeating sequence of actions is performed, called body of the cycle. A nested loop is one that is inside the body of another loop. An iterative cycle is a cycle whose number of repetitions is not specified, but is determined during the execution of the cycle.

In this case, one repetition of the cycle is called iteration.