Define an algorithm. Properties of the algorithm. Understandability - the algorithm must consist of commands that are “understandable” to the performer (included in the system of the performer’s commands). Why are algorithms needed?

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 the device itself, which 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 the environment, 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:

1. any algorithm has a name;
2. 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;
3. the algorithm can only include those commands that are in the executor’s SKI;
4. each command ends with a “;” sign, which indicates the end of the command;
5. 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:

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

Material used from books:

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

Yes, good algorithmic training is important for a programmer. And no, a good one is not at all memorizing algorithms from the list of “The Most Important Algorithms That Everyone Should Know.” In my opinion, good algorithmic training should strive to give the programmer the following three skills.

Firstly, this is the ability to solve incomprehensible problems. See possible strict interpretations in unclear formulations of life tasks. Based on strict interpretations, present solution options. Comprehensively analyze different options and choose the most suitable one.

Obviously, just knowing the algorithms is not enough for this. You need to be able to “see them” and recognize the possibilities of their application.

Secondly, algorithmic training should instill the habit of analyzing the effectiveness of each of your decisions. Do not omit quadratic or exponential algorithms in critical places, and do not introduce ideas into the program architecture that will then be impossible to implement effectively enough.

Thirdly, algorithmic training should help skillfully use ready-made tools. Databases are all data structures and algorithms. Moreover, at the conceptual level, they are quite simple and understandable - search trees, hashtables, SS-Table, ...

For example, knowing that an index in a database is just a search tree, it is easy to understand which queries can be executed quickly and which are doomed to full-scan.
Knowing how full-text search works in Lucene, on which algorithms, you can predict which queries to Elastic will produce relevant answers and which will not, and even how this can be improved.

To sum it up:

• In addition to the algorithms themselves, learn to recognize them in real-world problems.
• Get into the habit of analyzing the effectiveness of the code you write.
• Study the algorithms under the hood of the tools you use - this will come in handy when using them.

To compile a program intended to solve a problem on a computer, it is necessary to compile an algorithm for solving it.

An algorithm is a precise prescription that defines a process leading from input data to the desired end result. Algorithms, for example, are the rules of addition, multiplication, solving algebraic equations, matrix multiplication, etc. The word algorithm comes from algorithm, which is a Latin transliteration of the Arabic name of the Khorezmian mathematician of the 9th century al-Khwarizmi. Thanks to the Latin translation of the treatise al-Khwarizmi Europeans in the 12th century became acquainted with the positional number system, and in medieval Europe the algorithm was called the decimal positional number system and the counting rules in it.

In relation to a computer, an algorithm defines a computational process that begins with processing a certain set of possible initial data and is aimed at obtaining results determined by these initial data. Term computing process extends to the processing of other types of information, for example, symbolic, graphic or audio.

If the computational process ends with obtaining results, then the corresponding algorithm is said to be applicable to the considered set of initial data. Otherwise, they say that the algorithm is not applicable to the set of initial data. Any applicable algorithm has the following main properties :

effectiveness;

certainty;

mass character.

Efficiency means the possibility of obtaining a result after performing a finite number of operations.

Certainty consists in the coincidence of the results obtained, regardless of the user and the technical means used.

Mass character lies in the possibility of applying the algorithm to a whole class of similar problems that differ in specific values ​​of the initial data.

To specify an algorithm, it is necessary to describe its following elements:

a set of objects that make up the totality of possible initial data, intermediate and final results;

start rule;

rule for direct processing of information (description of the sequence of actions);

ending rule;

rule for extracting results.

The algorithm is always designed for a specific performer. In our case, such a performer is a computer. To ensure the possibility of implementation on a computer, the algorithm must be described in a language understandable to the computer, that is, in a programming language.

Thus, we can give the following definition of a program.

Computer program is a description of the algorithm and data in some programming language, intended for subsequent automatic execution.

Ways to describe algorithms

The main ways to describe algorithms include the following:

verbal-formular;

structural or block diagram;

using graph diagrams;

using Petri nets.

Before drawing up programs, verbal-formular and flowchart methods are most often used. Sometimes, before composing programs in low-level programming languages ​​such as Assembly language, the program algorithm is written using the constructs of some high-level programming language. It is convenient to use a software description of algorithms for the functioning of complex software systems. Thus, an Algol-like high-level programming language was used to describe the operating principles of the OS.

At verbal and formulaic way the algorithm is written in the form of text with formulas point by point that determine the sequence of actions.

Let, for example, you need to find the value of the following expression:

y = 2a – (x+6).

In a verbal and formulaic way, the algorithm for solving this problem can be written in the following form:

1. Enter values A And X.

2. Add x and 6.

3. Multiply a on 2.

4. Subtract from 2a sum (x+6).

5. Withdraw at as the result of evaluating the expression.

At block diagram In the description, the algorithm is depicted by geometric figures (blocks) connected by control lines (flow directions) with arrows. The blocks record a sequence of actions.

This method has a number of advantages compared to other methods of writing an algorithm. It is the most visual: each operation of the computational process is depicted as a separate geometric figure. In addition, a graphical representation of the algorithm clearly shows the ramifications of ways to solve the problem depending on various conditions, the repetition of individual stages of the computational process and other details.

The design of programs must meet certain requirements. Currently, there is a unified system of program documentation (USPD), which establishes the rules for the development, execution of programs and program documentation. The ESPD also defines the rules for the design of flowcharts of algorithms (GOST 10.002-80 ESPD, GOST 10.003-80 ESPD).

Data processing operations and storage media are depicted in the diagram accordingly blocks. Most of the blocks are conventionally inscribed in a rectangle with sides a and b. Minimum value A = 10 mm, increase A is made by a multiple of 5 mm. Size b=1.5a. For individual blocks, a relationship between a and b, equal to 1:2. Within the same diagram, it is recommended to depict blocks of the same size. All blocks are numbered. The types and purposes of the main blocks are given in table. 1.

Table 1. Symbols of block diagrams of algorithms

Understandability - the algorithm must consist of commands that are “understandable” to the performer (included in the system of the performer’s commands).

Discreteness (discontinuity, separateness) - the algorithm must represent the process of solving a problem as a sequential execution of simple (or previously defined) steps.

Certainty - i.e. Each rule of the algorithm must be clear, unambiguous and leave no room for arbitrariness. Thanks to this property, the execution of the algorithm is formal in nature and does not require any additional instructions or information about the problem being solved.

Effectiveness (or finiteness) - the algorithm must lead to a solution to the problem (or to the answer that there is no solution) in a finite number of steps.

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

The main feature of any algorithm is its formal execution, which allows specified actions (commands) to be performed not only by humans, but also by technical devices (performers). Thus, the executors of algorithms can be, for example, a person, a computer, a printer, a robotic manipulator, a machine tool with numerical control, a living cell, a trained animal, a computer program, a computer virus, a “turtle” in Logowriter or Logomirs (geometric executor) and etc.

The algorithm executor is a control device connected to a set of tools. The control device understands the algorithms and organizes their execution by commanding the appropriate tools. And the tools perform actions by executing commands from the control device. Before creating an algorithm for solving a problem, you need to find out what actions the proposed performer can perform.

These actions are called valid actions of the performer. Only they can be used.

The executor of computational algorithms is called a calculator. A calculator can deal with numbers and variables that represent numbers. Thus, an algorithm is an organized sequence of actions that are acceptable for some performer. The same performer can be simulated on a computer in many ways.

Algorithm complexity

The complexity of the algorithm allows us to estimate how quickly the complexity of the algorithm grows with an increase in the amount of input data. Labor intensity refers to the number of elementary operations that must be performed to solve a problem using a given algorithm. Typically, the algorithm's complexity estimate is expressed as O(f(N)), where O is the complexity function and N is the number of cases or examples processed. The least expensive are the algorithms for which the complexity function has the form f(N)=C and f(N)=C*N, where C is a constant. In the first case, computational costs do not depend on the amount of data processed, and in the second case they increase linearly. The most expensive are algorithms whose complexity has a power and factorial dependence on the number of processed observations.

SORTING

Sorting is the process of arranging many similar information objects in ascending or descending order of their values. For example, a list i of n elements will be sorted in ascending order of element values ​​if i<= i <= ... <= i.

There are two types of sorting algorithms: sorting arrays, which can be located either in operating memory or on disk as a direct access file, and sorting sequential files located on disks or magnetic tapes.

The main difference between array sorting and sequential file sorting is that each element of the array is accessible at any time. This means that at any time, any element of the array can be compared with any other element of the array, and any two elements of the array can swap places. In contrast, in a sequential file, only one element is available at a time. Because of these differences, sorting methods differ significantly between the two types of sorting.

In general, when sorting data, only part of the information is used as the sort key, which is used in comparisons. When an exchange is performed, the entire data structure is transferred.

SEARCH METHODS

Searching for information in an unsorted array requires sequential scanning of the array. The scan starts from the first element and ends either by finding an element or reaching the end of the array. This method should be used for unsorted data, but it can also be used for sorted data. If the data is sorted, then binary search can be used, which is much faster.