What is an algorithm and what does it mean. Algorithms

Today, computer technology has become an integral part of our lives. They introduced many terms into the vocabulary of the average person, the meanings of which are not always clear to him. But everyone uses them. For example, what is an algorithm? An ordinary user will not be able to give you a clear answer, but it is necessary to know this, since we encounter this every day.

History of the origin of the term

The concept of an algorithm was first developed by a mathematician named Muhammad Al-Khwarizmi. He lived in the East in the 8th and 9th centuries and wrote two great works. The first of them gave rise to the word “algebra”, and the second - to the concept of “algorithm”. It stood for the arithmetic operations we know as addition, subtraction, multiplication and division. In 1957, in one of the editions of the English dictionary, the authors considered that an algorithm is an outdated concept. Again it actively came into use only with the advent of computers. They denoted actions that were part of a certain process. But it does not have to be only mathematical. This implies an algorithm for actions of any nature, for example, preparing a dish. Since that time, this concept has been on the lips of almost all people.

Attempts to define the term

For a long time, this term was considered exclusively as an algorithm for numbers and operations with them. After all, mathematics itself was for the most part an applied science. The formulas that are used for calculations were considered algorithms at that time. The steps that were followed in solving were elementary, but the calculations themselves were very cumbersome and took a lot of time and effort. Mathematicians did not even think about defining this concept. But over time, science developed more and more and objects appeared that had not been encountered before (matrices, vectors, sets, etc.). All of them needed to be operated on. This gave impetus to the understanding that an algorithm is a complex concept, and it needs to be precisely defined for further use. Scientists are divided on this issue. Some believed that the algorithm could be applied to everything, while others doubted that every problem could be solved with its help. The last point of view turned out to be correct, but it could only be substantiated by giving a precise definition of the concept of “algorithm”.

What does the term "algorithm" mean?

Every day a person has to solve problems that have varying complexity. We are so accustomed to simple ones that we take actions to solve them automatically. The complex ones require a lot of thought. When a problem arises, we solve it in stages, taking steps. So in mathematics, for example, to find the unknown in an equation, you need to act step by step. These operations, gradually leading to the solution of the problem, are called an algorithm. An algorithm is a sequence of actions, which individually are its steps. They have a specific place and must strictly follow each other. There are classes of algorithms, they are called complexity classes. Each of them includes a certain set of problems that have approximately the same complexity of solution.

Properties common to all algorithms

In addition to algorithms, there are many other instructions in our world. But thanks to some properties we can distinguish it from the rest. These include:

Discreteness - the algorithm scheme foresees the solution of the task through sequential actions that are performed in strict order.
Certainty - all the conditions set are clear and do not have any ambiguity. The algorithm of actions, therefore, does not provide room for any improvisation. This allows you to do everything mechanically without needing additional prompts.
Efficiency - within a certain number of steps, the algorithm always gives the correct solution to the problem.
Massiveness - an algorithm is a solution to a problem that has a general form. That is, it is applicable to all problems of a certain class, regardless of the source data. They are selected from a certain field called “scope of applicability of the algorithm.”

Types of algorithms

Depending on various conditions, such as the goal, solution path, initial data, algorithms are divided into:

Mechanical - a rigid, only correct sequence to achieve the required result (ensuring engine operation, etc.).
Flexible: 1) probabilistic - have several ways to achieve the right decision; 2) heuristic - an algorithm scheme that does not have an unambiguous program of action (prescriptions, etc.), because it is based on a person’s personal qualities and experience.
Auxiliary - previously developed and fully intended to solve a specific problem.

Algorithms in computer science

For computer science, algorithms are of particular importance. In this science they are divided into the following types:

Linear - all actions are performed sequentially, one after another.
A branching algorithm is one in which the fulfillment of a certain condition leads to the choice of one of two possible options for further actions.
Cyclic - the same actions are repeated on different source data, thus selecting the most suitable ones.

Algorithm structure

Algorithms have their own structure, which is usually displayed in a diagram. An algorithm diagram is a graphical representation of it in the form of interconnected blocks. Each of them displays one of the steps of the algorithm. A description of a specific action is contained within each block. Such diagrams are usually drawn to facilitate programming, since they are visual and make it possible to visually perceive the amount of work that needs to be done. A person can comprehend the process and correct it even before errors occur.

Rules for compiling algorithms

The first rule is that you need to identify a large number of objects that can be amenable to the constructed algorithm. The programmer converts them into data using encoding. They come in and out. The first serve to start work, the second become its result. This is called data transformation.
The second rule says that working with the algorithm requires free memory. After all, without it there will be no way to place input data, work with them and get output. Memory consists of cells. If you give one of them a name, it becomes a variable.
The third rule has already been described above as one of the characteristics of the algorithm, namely discreteness. That is, the algorithm consists of individual operations, or steps.
The fourth rule reminds us of the determinism of the algorithm. That is, after each action you need to indicate what will be next, or stop the process.
The last rule states that after a certain number of steps the algorithm completes its work, having one or another result. And which one, the programmer himself indicates.

Thus, an algorithm is a complex concept that, before the advent of computers, was used only in mathematics and was considered obsolete. Today it is used in all spheres of life, one of the most important being computer science.

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.

In computer science, an action plan is called algorithm.
The algorithm consists of separate steps - teams. None of them can be skipped, most often no teams can be swapped.
Executor- a person, animal or machine capable of understanding and executing certain commands.
Artist Environment– objects that surround the performer and with which he works.
List of Executor Commands (SKI)– a set of commands understandable to the performer. The performer can only execute those commands that are included in his SKI.

To solve most problems, it is not enough to give one command to the performer; you need to create an algorithm for him - an action plan consisting of commands that he understands (included in his SKI).
Algorithm- a precisely defined plan of action for the performer, aimed at solving a problem. The algorithm can only include those commands that are in the SKI.

What are the algorithms?

Linear algorithm
In a linear algorithm, commands are executed sequentially, one after another. An example of a linear algorithm is the tea brewing algorithm.

Branching algorithm

In a branching algorithm, the order of commands may be different depending on the environment. An example of a branching algorithm is the street crossing algorithm.

Round robin algorithm
In a cyclic algorithm, some actions are repeated several times (in computer science they say that a loop is executed). There are two types of cyclic algorithms. In one of them we know in advance how many times we need to do these actions, in the other we must stop only when we complete the work, that is, our actions stop when some condition is met.
An example of a cycle of the first type is our life on weekdays (from Monday to Saturday) - we perform almost the same actions 6 times.
An example of a cycle of the second type is the algorithm for sawing a log: we cannot say in advance how many times we need to move the saw away from us and towards ourselves - it depends on the density of the tree, the quality of the saw and our efforts. However, we know for sure that we need to finish the job when the next sawn log falls to the ground.

Ways to write algorithms

There are three most common methods of writing algorithms in practice:

verbal(recording in natural language);
graphic(recording using graphic symbols);
program(texts in programming languages).

Verbal way of writing algorithms

Verbal method - a way to write an algorithm in natural language. This method is very convenient if you need to approximately describe the essence of the algorithm. However, with a verbal description it is not always possible to clearly and accurately express the logic of actions.

As an example of a verbal way of writing an algorithm, consider an algorithm for finding the area of a rectangle

where S is the area of the rectangle; a, b – the lengths of its sides.

Obviously, a, b must be specified in advance, otherwise the problem cannot be solved.

The verbal way of writing the algorithm looks like this:

The beginning of the algorithm.
Set the numerical value of side a.
Set the numerical value of side b.
Calculate the area S of the rectangle using the formula S=a*b.
Output the result of calculations.
End of the algorithm.

Graphical way to describe algorithms

For a more visual representation of the algorithm, a graphical method is used. There are several ways to describe algorithms graphically. The most widely used graphical description of algorithms in practice is the use of flowcharts. The undoubted advantage of block diagrams is the clarity and simplicity of writing the algorithm.

Each action of the algorithm corresponds to a geometric figure (block symbol). A list of the most commonly used symbols is given in the table below.

Since in the linear algorithm the commands are executed sequentially, the block diagram will look like:

Since in a branching algorithm the order of commands can be different depending on what the environment is, the flowchart will take the form:

In a cyclic algorithm, some actions are repeated several times and for it the flowchart will take the form:

Software method of writing algorithms

In order for an algorithm to be understandable to a robot, computer or other machine, it is not enough just to write commands; it is also necessary to formalize the algorithm in a form in which the machine understands it (write a program), i.e. write it using commands from SKI, following the design rules.

Program design rules:

any algorithm has a name;
the algorithm begins with an opening curly brace “(“ and ends with a closing curly brace “)”; the commands located between these brackets are called the body of the algorithm;
the algorithm can only include those commands that are in the executor’s SKI;
each command ends with a “;” sign, which indicates the end of the command;
To make it easier for us to understand programs, we use comments - text explanations that begin with the signs “/*” and end with the signs “*/”; the performer does not pay attention to the comments in the algorithm.

Practical tasks:

Create a flowchart to find the perimeter of a square.
Make a block diagram for brewing tea.
Make a block diagram for crossing an intersection with a traffic light.

Material used from books:

"Modern information technologies", authors: teachers of the "Turbo" center
"Algorithms and executors", author Polyakov K.

Before we start writing super programs, let's figure out what a program is? A program is a specific algorithm that your computer must execute.

Well, now the main question: What is an algorithm?

Properties of algorithms

I will not reinvent the wheel, but will simply list the properties of the algorithm that have been known for many years.

Extremity (effectiveness) algorithm means that a result must be obtained in a finite number of steps;
Discreteness algorithm means that the algorithm must be broken down into a sequence of steps;
Understandability algorithm means that the algorithm must contain only those commands that are included in the set of commands that a specific executor can execute;
Accuracy algorithm means that each command must be understood unambiguously;
Mass character algorithm means that, once compiled, the algorithm must be suitable for solving similar problems with different initial data.
Determinism (certainty). An algorithm has the property of determinism if for the same sets of initial data it produces the same result, i.e. the result is uniquely determined by the initial data.

Thus, Algorithm- this is a clear and precise instruction to the performer to perform a final sequence of steps leading from the initial data to the desired result.

Imagine that I have to cut an orange with a knife. To perform this action I need an algorithm.

I want to cut an orange. How to do it?

Types of algorithms

Linear (Commands are sequential without repetitions or transitions);

Algorithm example:

Start
take out the knife
cut an orange (It’s an orange, not any other fruit. ACCURACY is responsible for this)
eat an orange
end

Cyclic (There is a group of actions that are repeated according to some condition);

Algorithm example:

Start
take out the knife
UNTIL the oranges are gone
cut an orange
eat all the oranges
end

Branching (Command execution depends on a condition).

Algorithm example:

Start
take out the knife
IF the knife is dull, sharpen it
cut an orange
eat an orange
end

That's all. In the next lesson we will look at the structure of a program in Pascal.

Algorithm concept

The concept of an algorithm is a central concept in computer science. The word “algorithm” comes from the name of the Uzbek mathematician al-Khorezmi, who formulated the rules for performing arithmetic operations back in the 9th century. In modern mathematics and computer science, the term algorithm has the following definitions:

- a sequence of actions with strictly defined execution rules;
- a prescription that determines the content and sequence of operations that transform the initial data into the desired result;
- an exact description of a certain computational process or any other sequence of actions;
- an exact and complete prescription of the sequence of execution of a finite number of actions necessary to solve any problem of a given type.

The algorithm can be designed to be executed by a person or by an automatic device - a formal executor. The performer's task is to accurately implement an existing algorithm. The formal executor is not obliged to delve into the essence of the algorithm, and may even be unable to understand it.

An example of a formal performer is an automatic washing machine, which strictly performs the actions prescribed to it, even if you forgot to put powder in it. A person can also act as a formal performer, but first of all, various automatic devices, including a computer, are formal performers. Each algorithm is created based on a specific performer.

Each executor can execute commands only from a certain strictly defined list - the system of executor commands. For each command, the conditions of applicability must be specified (in which environmental states the command can be executed) and the results of executing the command must be described. After calling the command, the performer performs the corresponding elementary action.

In computer science, the universal executor of algorithms is the computer.

Types of algorithms

An algorithm in relation to a computer is an exact prescription, that is, a set of operations and rules for their alternation, with the help of which, starting with some initial data, it is possible to solve any problem of a fixed type.

Algorithms, depending on the goal, initial conditions of the problem, ways of solving it, and determining the actions of the performer, are divided as follows:

Probabilistic (stochastic) algorithm gives a program for solving a problem in several ways or methods leading to the probable achievement of a result.
Heuristic algorithm(from the Greek word “eureka”) is an algorithm in which the achievement of the final result of the action program is not clearly predetermined, just as the entire sequence of actions is not indicated, and all the actions of the performer are not identified. Heuristic algorithms include, for example, instructions and prescriptions. These algorithms use universal logical procedures and decision-making methods based on analogies, associations, and past experience in solving similar problems.
Linear algorithm- a set of commands (instructions) executed sequentially one after another.
Branching algorithm- an algorithm containing at least one condition, as a result of checking which the computer provides a transition to one of two possible steps.
Round robin algorithm- an algorithm that involves repeated repetition of the same action (the same operations) on new initial data. Most methods of calculation and enumeration of options are reduced to cyclic algorithms. A program cycle is a sequence of commands (series, cycle body) that can be executed repeatedly (for new source data) until a certain condition is satisfied.
Auxiliary (slave) algorithm (procedure)- an algorithm previously developed and entirely used in the algorithmization of a specific problem. In some cases, if there are identical sequences of instructions (commands) for different data, an auxiliary algorithm is also allocated in order to reduce the recording.

The algorithm can be specified in several ways:

- verbal, that is, recording a sequence of actions in natural language;
- graphic, using special graphic symbols;
- formulaic, that is, using mathematical formulas that determine the order of calculations;
- tabular, and in the form of a table in which the stages of execution of the algorithm and the results of execution are recorded.

Algorithm flowchart

Specifying algorithms using flowcharts has proven to be a very convenient means of depicting algorithms and has become widespread.

Algorithm flowchart - a graphical representation of the algorithm in the form of interconnected arrows (transition lines) and blocks- graphic symbols, each of which corresponds to one step of the algorithm. Inside the block a description of the corresponding action is given.

The table shows the most commonly used symbols.

Flowchart Symbols
Symbol name	Designation and example of filling	Explanation
Process		Computational action or sequence of actions
Solution		Checking conditions
Modification		Start of the cycle
Predefined process		Calculations by subroutine, standard subroutine
Input Output		I/O in General
Start-stop		Beginning, end of the algorithm, entry and exit to the subroutine
Document		Output of results

Block " process" is used to denote an action or sequence of actions that changes the meaning, form of presentation or placement of data. To improve the clarity of the diagram, several individual processing blocks can be combined into one block. The presentation of individual operations is quite free.

Block " solution" is used to indicate conditional control transitions. Each "solution" block must identify the question, condition, or comparison it defines.

Block " modification» used to organize cyclic structures. (The word “modification” means “modification, transformation”). A cycle parameter is written inside the block, for which its initial value, boundary condition and step of changing the parameter value are indicated for each repetition.

Block " predefined process" is used to indicate calls to auxiliary algorithms that exist autonomously in the form of some independent modules, and for calls to library routines.

For example, here is a block diagram of the algorithm for finding the maximum of two values:

Rules for constructing the algorithm

For an algorithm to fulfill its purpose, it must be built according to certain rules. Therefore, we need to talk not about the properties of the algorithm, but about the rules for constructing the algorithm, or about the requirements for the algorithm.

First rule- when constructing an algorithm, first of all, it is necessary to specify a set of objects with which the algorithm will work. The formalized (coded) representation of these objects is called data. The algorithm begins to work with a certain set of data, which are called input, and as a result of its work produces data, which is called output. Thus, the algorithm converts input data into output data. Until we have formalized input data, we cannot build an algorithm.

Second rule- memory is required for the algorithm to work. The memory stores the input data with which the algorithm begins to work, intermediate data and output data that are the result of the algorithm. Memory is discrete, i.e., consisting of individual cells. A named memory location is called a variable. In the theory of algorithms, memory sizes are not limited, i.e., it is believed that we can provide the algorithm with any amount of memory necessary for operation.

Third rule- discreteness. The algorithm is built from individual steps (actions, operations, commands). More precisely, from many steps.

Fourth rule- determinism. After each step, you must indicate which step is performed next, or give a stop command.

Fifth rule- convergence (effectiveness). The algorithm must terminate after a finite number of steps. In this case, it is necessary to indicate what is considered the result of the algorithm.

Algorithm properties

Discreteness(discontinuity, separateness) - the algorithm must represent the process of solving a problem as a sequential execution of simple (or previously defined) steps. Each action provided by the algorithm is executed only after the previous one has completed execution.

Certainty- each rule of the algorithm must be clear and unambiguous. Due to this property, the execution of the algorithm is mechanical in nature and does not require any additional instructions or information about the problem being solved.

Efficiency(finiteness) - the algorithm must lead to solving the problem in a finite number of steps.

Mass character- the algorithm for solving the problem is developed in a general form, that is, 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, which is called the area of applicability of the algorithm.