Almost everything in our world is subject to some laws and rules. Modern science does not stand still, thanks to which mankind knows a lot of formulas and algorithms, following which, you can calculate and recreate many actions and structures created by nature, and bring to life the ideas invented by man.
In this article, we will analyze the basic concepts of the algorithm.
The history of the emergence of algorithms
Algorithm - a concept that appeared in the XII century. The very word "algorithm" comes from the Latin interpretation of the name of the famous mathematician of the Middle East, Muhammad al-Khwarizmi, who wrote the book "On Indian Counting". This book describes how to correctly write natural numbers using Arabic numerals, and a description of the algorithm of actions with a column over such numbers.
In the XII century, the book "On the Indian Account" was translated into Latin, and then this definition appeared.
Algorithm Interaction with Human and Machine
Creating an algorithm requires a creative approach, so only a living being can create a new list of sequential actions. But for the execution of existing instructions, it is not necessary to have a fantasy, even a soulless technique can handle this.
An excellent example of the exact execution of a given instruction is an empty microwave oven that continues to work despite the absence of food inside it.
The subject or object, which does not have to delve into the essence of the algorithm, is called a formal executor. A person can also become a formal executor, but in the event that one or another action is unprofitable, a thinking executor can do everything in his own way. Therefore, the main performers are computers, microwave ovens, telephones and other equipment. The concept of an algorithm in computer science is of the utmost importance. Each algorithm is compiled with the expectation of a specific subject, taking into account the permissible actions. Those objects to which the subject can apply instructions constitute the environment of the executor.
Almost everything in our world is subject to some laws and rules. Modern science does not stand still, thanks to which mankind knows a lot of formulas and algorithms, following which you can calculate and recreate many actions and creations of nature and bring to life the ideas invented by man. In this article, we will analyze the basic concepts of the algorithm.
What is an algorithm?
Most of the activities that we perform during our lives require the observance of a number of rules. The quality and result of fulfilling the tasks assigned to him depends on how accurate a person’s idea is about what, how and in what sequence he should do. Since childhood, parents have been trying to develop an algorithm for the main actions in their child, for example: wake up, make the bed, wash and brush your teeth, do exercises, have breakfast, etc., the list that a person does all his life in the morning can also be considered a kind of algorithm.
Algorithm - denoting a set of instructions that a person must follow in order to solve a specific problem.
In general, the algorithm has many definitions, several scientists characterize it in different ways.
If the algorithm used by a person every day is different for everyone, and can change depending on the age and situations in which the performer finds himself, then the set of actions that need to be performed to solve a mathematical problem or to use technology is the same for everyone and always remains unchanged.
There is a different concept, too, they differ - for example, for a person who pursues a goal, and for technology.
In our age of information technology, people daily follow a set of instructions created before them by other people, because technology requires precise execution of a series of actions when used. Therefore, the main task of teachers in schools is to teach children how to use algorithms, quickly grasp and change existing rules in accordance with the current situation. The structure of the algorithm is one of those concepts that is studied in the lesson of mathematics and computer science in every school.
Basic properties of the algorithm
1. Discreteness (sequence of individual actions) - any algorithm should be represented as a series of simple actions, each of which should begin after the completion of the previous one.
2. Certainty - each action of the algorithm should be so simple and clear that the performer does not have questions and does not have freedom of action.
3. Efficiency - the description of the algorithm should be clear and complete, so that after the execution of all instructions, the task reaches its logical end.
4. Mass character - the algorithm should be applicable to a whole class of problems, which can be solved only by changing the numbers in the algorithm. Although there is an opinion that the last point does not apply to algorithms, but to all mathematical methods in general.
Often in schools, in order to give children a more understandable description of the algorithms, teachers use the example of cooking from a cookbook, making medicine from a prescription, or making a soap-making process based on a master class. However, taking into account the second property of the algorithm, which says that each item of the algorithm must be so clear that it can be performed by absolutely any person and even a machine, we can conclude that any process that requires at least some kind of imagination, the algorithm cannot be named. And cooking and needlework require certain skills and a well-developed imagination.
There are different types of algorithms, but there are three main ones.
Cyclic algorithm
In this type, some items are repeated several times. The list of actions that must be repeated to achieve the goal is called the body of the algorithm.
Loop iteration is the execution of all items included in the body of the loop.
Parts of a loop that are constantly executed a certain number of times are called a loop with a fixed number of iterations.
Those parts of the cycle, the repetition frequency of which depends on a number of conditions, are called indefinite.
The simplest type of cycle is the fixed one.
There are two types of cyclic algorithms:
Loop with precondition. In this case, the body of the loop checks its condition before it is executed.
Loop with postcondition. The condition check occurs after the end of the loop execution.
Linear types of algorithms
The instructions of such circuits are executed once in the order in which they are presented. For example, you can consider the process of making a bed or brushing your teeth. This type also includes mathematical examples, where there are only addition and subtraction operations.
Branching Algorithm
There are several options in a branching type, which one will be applied depends on the condition.
Example. Question: "Is it raining?" Answer options: "Yes" or "No". If "yes" - open the umbrella, if "no" - put the umbrella in the bag.
Helper Algorithm
An auxiliary algorithm can be used in other algorithms by specifying only its name.
Terms used in algorithms
Condition located between the words "if" and "then".
For example: if you know English then press one. In this sentence, the condition will be the part of the phrase "you know English".
Data- information that carries a certain semantic load and is presented in such a way that it can be transmitted and used for this algorithm.
Algorithmic process- solving the problem according to the algorithm using certain data.
Structure of the algorithm
The algorithm may have a different structure. In order to describe an algorithm, the concept of which also depends on its structure, one can use a number of different methods, for example: verbal, graphic, using a specially developed algorithmic language.
Which of the methods will be used depends on several factors: on the complexity of the task, on how detailed the process of solving the problem needs to be, etc.
Graphical version of the algorithm construction
A graphical algorithm is a concept that implies a decomposition of actions that need to be performed to solve a specific problem, according to certain geometric shapes.
They are not depicted randomly. In order for anyone to understand them, flowcharts and Nassi-Schneiderman structograms are most often used.
Also, block diagrams are shown in accordance with GOST-19701-90 and GOST-19.003-80.
Graphic figures used in the algorithm are divided into:
Basic. The main images are used to indicate the operations needed to process data when solving a problem.
Auxiliary. Auxiliary images are needed to indicate individual, not the most important, elements of solving the problem.
In a graphical algorithm, those used to represent data are called blocks.
All blocks go in sequence "from top to bottom" and "from left to right" - this is the correct flow direction. With the correct sequence, the lines connecting the blocks to each other do not show the direction. In other cases, the direction of the lines is indicated by arrows.
The correct scheme of the algorithm should not have more than one exit from the processing blocks and less than two exits from the blocks responsible for and checking the conditions.
How to build an algorithm?
The structure of the algorithm, as mentioned above, must be built according to GOST, otherwise it will not be understandable and accessible to others.
The general recording methodology includes the following points:
The name by which it will be clear what problem can be solved using this scheme.
Each algorithm must have a clearly marked beginning and end.
Algorithms should clearly and clearly describe all the data, both input and output.
When compiling the algorithm, it should be noted the actions that will allow you to perform the actions necessary to solve the problem on the selected data. Approximate view of the algorithm:
- Schema name.
- Data.
- Start.
- Teams.
- End.
The correct construction of the circuit will greatly facilitate the calculation of algorithms.
Geometric shapes responsible for different actions in the algorithm
Horizontally located oval - the beginning and the end (a sign of completion).
Horizontally located rectangle - calculation or other actions (process sign).
Horizontally located parallelogram - input or output (data sign).
A horizontally located rhombus is a test of a condition (a sign of a solution).
An elongated, horizontally located hexagon is a modification (a sign of preparation).
Models of algorithms are shown below in the figure.
Formula-verbal version of the construction of the algorithm.
Formula-word algorithms are written in an arbitrary form, in the professional language of the area to which the task belongs. The description of actions in this way is carried out using words and formulas.
The concept of an algorithm in computer science
Everything in the computer world is based on algorithms. Without clear instructions entered in the form of a special code, not a single technique or program will work. At computer science lessons, students are trying to give the basic concepts of algorithms, teach them how to use them and create them on their own.
The creation and use of algorithms in computer science is a more creative process than, for example, following instructions for solving a problem in mathematics.
There is also a special program "Algorithm", which helps people who are ignorant in the field of programming to create their own programs. Such a resource can become an indispensable assistant for those who are taking their first steps in computer science and want to create their own games or any other programs.
On the other hand, any program is an algorithm. But if the algorithm carries only the actions that need to be performed by inserting its data, then the program already carries the finished data. Another difference is that the program can be patented and private property, but the algorithm is not. An algorithm is a broader concept than a program.
Output
In this article, we analyzed the concept of an algorithm and its types, learned how to write graphic diagrams correctly.
Algorithm
Often, some mechanism acts as an executor (computer, lathe, sewing machine), but the concept of an algorithm does not necessarily apply to computer programs, for example, a clearly described recipe for preparing a dish is also an algorithm, in which case the executor is a person.
The concept of an algorithm refers to the original, basic, basic concepts of mathematics. Computational processes of an algorithmic nature (arithmetic operations on integers, finding the greatest common divisor of two numbers, etc.) have been known to mankind since ancient times. However, in an explicit form, the concept of an algorithm was formed only at the beginning of the 20th century.
Partial formalization of the concept of an algorithm began with attempts to solve the resolution problem (Germ. Entscheidungsproblem), which was formulated by David Hilbert in 1928. The following steps of formalization were necessary to define efficient computation or "efficient method"; among such formalizations are Gödel-Herbran-Kleene recursive functions, and gg., Alonzo Church's λ-calculus, Emil Post's 1936 "Formulation 1" and the Turing machine. In methodology, the algorithm is a basic concept and receives a qualitatively new concept as optimality as it approaches the predicted absolute. In the modern world, the algorithm in a formalized expression forms the basis of education by examples, in likeness. Based on the similarity of algorithms in various fields of activity, the concept (theory) of expert systems was formed.
History of the term
The modern formal definition of the algorithm was given in the 30-50s of the XX century in the works of Turing, Post, Church (Church-Turing thesis), N. Wiener, A. A. Markov.
The very word "algorithm" comes from the name of the Khorezm scientist Abu Abdullah Muhammad ibn Musa al-Khwarizmi (algorithm - al-Khwarizmi). Around 825, he wrote an essay in which he first gave a description of the positional decimal number system invented in India. Unfortunately, the Persian original of the book has not been preserved. Al-Khwarizmi formulated the rules for computing in the new system and probably for the first time used the number 0 to indicate the missing position in the notation of the number (its Indian name was translated by the Arabs as as-sifr or simply sifr, hence words such as "number" and "cipher"). Around the same time, other Arabic scholars began to use Indian numerals. In the first half of the 12th century, the book of al-Khwarizmi in Latin translation penetrated Europe. The translator, whose name has not come down to us, gave her the name Algorithmi de numero Indorum("Algorithms about Indian counting"). In Arabic, the book was called Kitab al-jabr wal-muqabala("The Book of Addition and Subtraction"). From the original title of the book comes the word Algebra (algebra - al-jabr - completion).
Thus, we see that the Latinized name of the Central Asian scientist was placed in the title of the book, and today it is believed that the word "algorithm" got into European languages precisely thanks to this work. However, the question of its meaning for a long time caused fierce debate. Over the centuries, the origin of the word has been given a variety of explanations.
Some led out algorism from Greek algiros(sick) and arithmos(number). From such an explanation it is not very clear why the numbers are “sick”. Or did linguists think people who had the misfortune to do calculations seemed sick? The Encyclopedic Dictionary of Brockhaus and Efron also offered its explanation. In him algorithm(by the way, before the revolution, the spelling was used algorithm, through fita) is produced "from the Arabic word Al-Goretm, that is, the root." Of course, these explanations can hardly be considered convincing.
The translation of al-Khwarizmi's work mentioned above became the first sign, and over the next few centuries many other works appeared devoted to the same issue - teaching the art of counting with the help of numbers. And they all had the word in their title algorithms or algorismi.
Later authors did not know anything about al-Khwarizmi, but since the first translation of the book begins with the words: “Dixit algorizmi: ...” (“Al-Khwarizmi said: ...”), they still associated this word with the name of a particular person. The version about the Greek origin of the book was very common. In a 13th-century Anglo-Norman manuscript, written in verse, we read:
Algorithm is the art of counting with numbers, but at first the word "number" referred only to zero. The famous French truver Gautier de Coincy (Gautier de Coincy, 1177-1236) in one of his poems used the words algorismus-cipher(which meant the number 0) as a metaphor for characterizing an absolutely worthless person. Obviously, the understanding of such an image required the appropriate preparation of the listeners, which means that the new number system was already quite well known to them.
For many centuries, the abacus was actually the only means for practical calculations; it was used by merchants, money changers, and scientists. The merits of calculations on a counting board were explained in his writings by such an outstanding thinker as Herbert of Avrilaksky (938-1003), who became pope in 999 under the name of Sylvester II. The new made its way with great difficulty, and the history of mathematics included a stubborn opposition between the camps of algorismists and abacists (sometimes called herbekists), who advocated the use of an abacus instead of Arabic numerals for calculations. Interestingly, the famous French mathematician Nicolas Chuquet (1445-1488) was entered in the register of taxpayers of the city of Lyon as an algoriste. But more than one century passed before the new method of counting was finally established, it took so much time to develop generally recognized notations, improve and adapt calculation methods for writing on paper. In Western Europe, teachers of arithmetic continued to be called "masters of the abacus" until the 17th century, such as the mathematician Niccolò Tartaglia (1500-1557).
So, essays on the art of counting were called Algorithms. Of the many hundreds, one can single out such unusual ones as a treatise written in verse Carmen de Algorismo(Latin carmen and means poetry) by Alexander de Villa Dei (d. 1240) or the textbook of the Viennese astronomer and mathematician Georg Purbach (Georg Peurbach, 1423-1461) Opus algorismi jocundissimi("The funniest essay on the algorithm").
Gradually, the meaning of the word expanded. Scientists began to apply it not only to purely computational, but also to other mathematical procedures. For example, around 1360, the French philosopher Nicolaus Oresme (1323/25-1382) wrote a mathematical treatise Algorism proportionum(“Calculation of Proportions”), in which he first used degrees with fractional exponents and actually came close to the idea of logarithms. When the abacus was replaced by the so-called counting on the lines, numerous manuals on it began to be called Algorithmus linearis, that is, the rules for counting lines.
It can be noted that the original form algorismi after some time, she lost the last letter, and the word acquired a more convenient form for European pronunciation algorism. Later, it, in turn, was subjected to distortion, most likely associated with the word arithmetic.
Turing machine
The basic idea behind the Turing machine is very simple. A Turing machine is an abstract machine (automaton) that works with a tape of individual cells in which symbols are written. The machine also has a head for writing and reading characters from the cells, which can move along the tape. At each step, the machine reads a character from the cell pointed to by the head and, based on the character read and the internal state, takes the next step. In this case, the machine can change its state, write another character to the cell, or move the head one cell to the right or left.
Based on the study of these machines, Turing's thesis (the main hypothesis of algorithms) was put forward:
This thesis is an axiom, a postulate, and cannot be proved by mathematical methods, since the algorithm is not an exact mathematical concept.
Recursive functions
Each algorithm can be associated with a function that it calculates. However, the question arises whether it is possible to associate a Turing machine with an arbitrary function, and if not, for which functions is there an algorithm? Research into these questions led to the creation of the theory of recursive functions in the 1930s.
The class of computable functions was written in an image resembling the construction of some axiomatic theory based on a system of axioms. First, the simplest functions were chosen, the calculation of which is obvious. Then the rules (operators) for constructing new functions based on existing ones were formulated. The necessary class of functions consists of all the functions that can be obtained from the simplest application of operators.
Similar to Turing's thesis in the theory of computational functions, a conjecture has been put forward, which is called Church's thesis:
The proof that the class of computable functions coincides with Turing calculable functions takes place in two steps: first, the computation of the simplest functions on a Turing machine is proved, and then the computation of functions obtained as a result of applying operators.
Thus, informally, an algorithm can be defined as a clear system of instructions defining a discrete deterministic process that leads from initial data (input) to the desired result (output), if it exists, in a finite number of steps; if the desired result does not exist, the algorithm either never terminates or reaches a dead end.
Normal Markov Algorithm
The normal Markov algorithm is a system of successive applications of substitutions that implement certain procedures for obtaining new words from the base ones, built from the characters of some alphabet. Like a Turing machine normal algorithms do not perform the calculations themselves: they only perform the transformation of words by replacing letters according to given rules.
normally computable is a function that can be implemented by a normal algorithm. That is, an algorithm that turns each word from the set of valid data of the function into its initial values ..
The creator of the theory of normal algorithms A. A. Markov put forward a hypothesis, which was called the Markov normalization principle:
Like the theses of Turing and Church, the Markov normalization principle cannot be proved by mathematical means.
Stochastic Algorithms
However, the above formal definition of the algorithm may be too strict in some cases. Sometimes there is a need to use random variables. An algorithm whose operation is determined not only by the initial data, but also by the values obtained from the random number generator is called stochastic(or randomized, from English. randomized algorithm) . Formally, such algorithms cannot be called algorithms, since there is a probability (close to zero) that they will not stop. However, stochastic algorithms are often more efficient than deterministic ones, and in some cases - the only way to solve the problem.
In practice, instead of a random number generator, a pseudo-random number generator is used.
However, one should distinguish between stochastic algorithms and methods that give a correct result with a high probability. Unlike the method , the algorithm gives correct results even after a long run.
Some researchers admit the possibility that the stochastic algorithm will give an incorrect result with some predetermined probability. Then stochastic algorithms can be divided into two types:
- algorithms like Las Vegas always give the correct result, but their running time is not defined.
- algorithms Monte Carlo type, unlike the previous ones, can give incorrect results with a known probability (they are often called Monte Carlo methods).
Other formalizations
For some tasks, the formalizations mentioned above can make it difficult to find solutions and carry out research. To overcome obstacles, both modifications of the "classical" schemes were developed, and new models of the algorithm were created. In particular, one can name:
- multi-tape and non-deterministic Turing machines;
- register and RAM machine - a prototype of modern computers and virtual machines;
and others.
Formal properties of algorithms
Various definitions of the algorithm, explicitly or implicitly, contain the following set of general requirements:
Types of algorithms
A special role is played by applied algorithms designed to solve certain applied problems. An algorithm is considered correct if it meets the requirements of the problem (for example, it gives a physically plausible result). An algorithm (program) contains errors if for some initial data it gives incorrect results, failures, failures, or does not give any results at all. The last thesis is used in algorithmic programming competitions to evaluate the programs compiled by the participants.
The case when the result of the evaluation of a function is the logical expression "true" or "false" (or the set (0, 1)) is called a problem that can be solved or unsolvable depending on the computability of the function.
It is important to accurately specify the allowable set of input data, since a problem may be solvable for one set and unsolvable for another.
One of the first problems for which unsolvability was proven is the halting problem. It is formulated as follows:
The proof of the unsolvability of the halting problem is important because other problems can be reduced to it. For example, a simple halting problem can be reduced to a halting problem on an empty line (when you need to determine for a given Turing machine whether it will stop when it is started on an empty line), thereby proving the latter's undecidability. .
Algorithm Analysis
Along with the spread of information technology, the risk of software failures has increased. One of the ways to avoid errors in algorithms and their implementations is to prove the correctness of systems by mathematical means.
The use of mathematical apparatus for the analysis of algorithms and their implementations is called formal methods. Formal methods involve the use of formal specifications and usually a set of tools for parsing and proving the properties of the specifications. Abstraction from implementation details allows you to set the properties of the system independently of its implementation. In addition, the precision and unambiguity of mathematical statements avoids the ambiguity and inaccuracy of natural languages.
According to the hypothesis of Richard Mace, "avoiding errors is better than eliminating errors." According to Hoare's conjecture, "proof of programs solves the problem of correctness, documentation, and compatibility". The proof of the correctness of programs allows us to reveal their properties in relation to the entire range of input data. To do this, the concept of correctness was divided into two types:
- Partial correctness- the program gives the correct result for those cases when it terminates.
- Full correctness- the program terminates and produces the correct result for all elements from the input range.
During proof of correctness, the text of the program is compared with the specification of the desired ratio of input-output data. For Hoare-type proofs, this specification takes the form of statements, which are called preconditions and postconditions. Together with the program itself, they are also called the Hoare triplet. These statements are written
P{Q} Rwhere P is a precondition that must be met before running the program Q, but R is a postcondition that is true after the program terminates.
Formal methods have been successfully applied to a wide range of problems, in particular: the development of electronic circuits, artificial intelligence, automatic systems on the railway, verification of microprocessors, specification of standards, and specification and verification of programs.
Working hours
A common criterion for evaluating algorithms is the running time and the order in which the running time grows depending on the amount of input data.
For each specific task, they make up a certain number, which is called its size. For example, the size of the task of calculating the product of matrices can be the largest size of matrix factors, for tasks on graphs, the size can be the number of graph edges.
The time an algorithm spends as a function of task size is called the time complexity of that algorithm. T(n). The asymptotic behavior of this function as the size of the problem increases is called asymptotic time complexity, and a special notation is used to denote it.
It is the asymptotic complexity that determines the size of the problems that the algorithm is able to handle. For example, if the algorithm processes input data of size in time cn², where c- some constant , then they say that the time complexity of such an algorithm O(n²).
Often, during the development of an algorithm, one tries to reduce the asymptotic time complexity for the worst cases. In practice, there are cases when an algorithm that "usually" runs fast is sufficient.
Roughly speaking, the analysis of the average asymptotic time complexity can be divided into two types: analytical and statistical. The analytical method gives more accurate results, but is difficult to use in practice. But the statistical method allows you to quickly analyze complex problems.
The following table lists common commented asymptotic complexities.
Complexity A comment Examples O(1) Sustainable running time does not depend on task size Expected lookup time in hash table O(log log n) Very slow growth of required time Expected running time of interpolating search n elements O(log n) Logarithmic growth - doubling the task size increases the running time by a constant amount calculation x n; Binary search in an array of n elements O(n) Linear growth - doubling the task size will also double the time required Add/subtract numbers from n numbers; Linear search in an array of n elements O(n log n) Linear Growth - Doubling the task size will slightly more than double the time required Merge sort or heap sort n elements; matching sort lower bound n elements O(n²) Quadratic Growth - Doubling the task size quadruples the time required Elementary sorting algorithms O(n³) Cubic Growth - Doubling the task size increases the required time by eight times Ordinary matrix multiplication O(c n) Exponential growth - increasing the task size by 1 results in c- a multiple increase in the required time; doubling the task size squares the required time Some traveling salesman problems, brute-force search algorithms The presence of initial data and some result
An algorithm is a precisely defined instruction, applying it sequentially to the initial data, you can get a solution to the problem. For each algorithm, there is a certain set of objects that can be used as input data. For example, in the algorithm for dividing real numbers, the dividend can be anything, and the divisor cannot be equal to zero.
The algorithm serves, as a rule, to solve not one specific problem, but a certain class of problems. So, the addition algorithm is applicable to any pair of natural numbers. This expresses its mass property, that is, the ability to repeatedly apply the same algorithm for any task of the same class.
For the development of algorithms and programs is used algorithmization- the process of systematic compilation of algorithms for solving the applied problems. Algorithmization is considered an obligatory stage in the process of developing programs and solving problems on a computer. It is for applied algorithms and programs that determinism, efficiency and mass character, as well as the correctness of the results of solving the tasks set, are fundamentally important.
An algorithm is a clear and precise instruction to execute a sequence of actions aimed at achieving a goal.
Presentation of algorithms
Algorithm notation forms:
- verbal or verbal (language, formula-verbal);
- pseudocode (formal algorithmic languages);
- schematic:
- structurograms (Nassi-Schneiderman schemes);
- graphic (block diagrams).
Usually, at first (at the idea level), the algorithm is described in words, but as it approaches implementation, it acquires more and more formal outlines and formulation in a language understandable to the performer (for example, machine code).
Algorithm Efficiency
Although the definition of the algorithm requires only a finite number of steps required to achieve a result, in practice, even even a billion steps is too slow. Also, there are usually other restrictions (on the size of the program, on the allowed actions). In this regard, such concepts as the complexity of the algorithm (time, program size, computational, etc.) are introduced.
For each task, there can be many algorithms that lead to the goal. Increasing the efficiency of algorithms is one of the tasks of modern computer science. In the 50s. In the 20th century, even its separate area appeared - fast algorithms. In particular, in the problem of multiplying decimal numbers, known to everyone since childhood, a number of algorithms have been discovered that can significantly (in the asymptotic sense) speed up finding the product. See quick multiplication
Euclid's algorithm is an efficient method for calculating the greatest common divisor (gcd). Named after the Greek mathematician Euclid; one of the oldest algorithms still in use today.
Described in the "Beginnings" of Euclid (about 300 BC), namely in books VII and X. In the seventh book, an algorithm for integers is described, and in the tenth - for the lengths of segments.
There are several variants of the algorithm, below is a recursive version written in pseudocode:
function node(a, b) if b = 0 return a otherwise return node(b, a mod b)GCD of numbers 1599 and 650:
Step 1 1599 = 650*2 + 299 Step 2 650 = 299*2 + 52 Step 3 299 = 52*5 + 39 Step 4 52 = 39*1 + 13 Step 5 39 = 13*3 + 0
see also
Notes
- Kleene 1943 in Davis 1965:274
- Rosser 1939 in Davis 1965:225
- (Igoshin, p. 317)
- Basics: The Turing Machine (with an interpreter! . Good Math, Bad Math(February 9, 2007). Archived from the original on February 2, 2012.
- (Igoshin, section 33)
- Encyclopedia of Cybernetics, vol. 2 , c. 90-91.
- (Igoshin, section 34)
- “Probabilistic algorithms should not be mistaken with methods (which I refuse to call algorithms), which produce a result which has a high probability of being correct. It is essential that an algorithm produces correct results (discounting human or computer errors), even if this happens after a very long time.” Henri Cohen A Course in Computational Algebraic Number Theory. - Springer-Verlag, 1996. - P. 2. - ISBN 3-540-55640-0
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rives "t, Clifford Stein. - ISBN 0-262-03293-7
According to the author, the identified similarity between the concepts of “algorithm” and “technological process” is fundamental and has far-reaching consequences. Unfortunately, this similarity has not yet attracted the attention of scientists, which led to negative results and to a large extent contributed to the division of science into “isolated cells”, creating unjustified obstacles to interdisciplinary and interdisciplinary contacts. Today, programmers and technologists (in the broad sense of the word, including agronomists, doctors, teachers, managers, etc.) are different “castes” who receive different education and speak different professional languages. Such barriers greatly complicate mutual understanding between specialists when solving automation problems and working on interdisciplinary projects.
In this way, technolanguage is a new type of language that combines the mathematical rigor of an algorithmic language with the convenience of a language of cross-industry and interdisciplinary communication, suitable for a visual description of technologies and mutual understanding between specialists.
For our purposes, it would be convenient to define technology as an activity (sequence of actions) leading to the goal. Agreeing with this approach, we get the opportunity to consider the algorithm and the technical process as special cases of technology, which acquires the status of a generic concept.
It is known that the term “algorithm” is also used in a broader sense to represent human activity in the form of a strict sequence of individual elementary actions or procedures, and a technological process can be defined as “a sequence of actions (technological operations) aimed at creating a given object, each of which is based on any natural processes (physical, chemical, biological, etc.) and human activity” . A careful analysis of these and many other definitions shows that the concepts under study coincide to a large extent, and the existing differences are in a certain sense insignificant. In other words, the technological process and the algorithm are twin concepts, or at least “close relatives”. To make this idea more convincing, we will try to move away from the traditional point of view and propose new definitions.
The mentioned shortcoming (difficulties in mutual understanding) can be weakened or eliminated by creating a single language that is equally convenient for technologists, programmers and other specialists. The term for this language is technological language(technical language). The first candidate for the role of a technological language is DRAKON.
It should be emphasized that the goals of using a technological language in the development of computer programs and technical processes are different. In the first case (creation of programs), the language allows translation into machine codes. In the second case (description of technologies), two situations are possible. If there is an automated control system and the description of the technology is intended for a computer that controls the process, the description automatically turns into a computer program, and the matter is reduced to the previous case. If an automated control system and a control computer are not available or are not required, and therefore translation is not needed, the language is used as a means of unambiguously solving problems and ensuring mutual understanding between people, which in itself is an extremely valuable property of the language.
Difference Between Algorithm and Program
Program(computer, first of all) - a record of a sequence of instructions executed by a computer.
Algorithm- an instruction that includes a certain clear sequence of actions performed to complete the task. The number of actions is always finite.
The average user's understanding of programs is very limited and is based on the experience of launching and working in applications. We know that there are programmers who write programs, and our job is to take advantage of the results of their work. Algorithms are remembered by people who graduated from school a certain time ago in the context of the theory of algebra, vaguely imagining that this knowledge will certainly not be useful. And if you have to face the intersection of these concepts, most of us are lost, not finding connections between algorithms and programs, and, therefore, not understanding the task. Sometimes these concepts are combined, considering that “algorithm” is a more professional and accurate designation of “program”. To fill in the gaps in the views, let's see what is behind the terminology.
Another difference between a program and an algorithm is the operation of specific data during execution. If the algorithm is only a description of the actions required to achieve the goal, then the program contains a description of the data as well. An algorithm can be massive, that is, it can be designed to solve not one problem, but a class of problems. However, its properties also include discreteness and certainty. The algorithm implies the performance of elementary actions on elementary objects, however, elementarity will be different for different performers.
What is the difference between an algorithm and a program is clear from the terminology. It would seem that in both cases we see ordered actions leading to the final result. As is clear from the definitions, a program can consist of several algorithms, but the “general - particular” hierarchy is not traced here. An algorithm is generally any instruction that clearly lists actions. For example, to assemble a cabinet. Of course, it will not be a program. An algorithm can exist in any form: it can be memorized, written down in a notebook, sketched in the form of a diagram, dictated, since it is based on a logical component, not a formal one. The program is a formal concept. It is precisely a record of a set of algorithms, moreover, a record in one of the programming languages understandable to a computer. It can be not only our usual computer, but also the control unit of any device. Thus, an algorithm can be defined as a method or scheme for implementing an idea, a program as its implementation by specific means.
The concept of an algorithm is much broader than programs: the basic concept of mathematics. A computer program is an object of intellectual property rights, but an algorithm is not one of them.
The main differences between labor protection and labor safety
- assess the risk of a hazardous situation in the workflow, develop steps to prevent it;
- draw up safety instructions;
- teach safe methods and techniques of work;
- provide training to employees.
The question of how the labor protection of personnel differs from labor safety was of interest to many people who were instructed for the first time at a new place of work. These two terms are often used together, but they have different meanings. To understand what their similarities and differences are, it is necessary to find out the tasks of labor protection and safety, to determine the methods for solving them.
- workplace safety standards;
- building regulations;
- sanitary norms and rules;
- technological design standards;
- other rules and instructions developed by supervisory authorities.
Labor protection is aimed at preserving the most important resources of the state - human. It is considered one of the elements of social protection, allowing citizens to exercise their rights. At the same time, it is necessary to comply with the guarantees established by the state.
The task of labor safety is protection from harmful physical effects in the workplace.
- The right to work in conditions that meet established standards. Fixing these requirements in the labor agreement.
- Suspension of work for the period of elimination of labor protection violations that appeared through the fault of the enterprise. During this time, the employee must be paid wages, save the workplace.
- If there are factors hazardous to health, providing the citizen with another place of work or paying for idle time.
- Prohibition to engage in work without the provision of protective equipment.
- Compensation for damage to health caused at work through the fault of the employer.
Futsal and futsal are two similar, but at the same time different sports games. Before you understand what they are, it is extremely important to pay increased attention to the numerous nuances.
Game projectile is one of the most important attributes in sports. For futsal, the following parameters of the ball used are assumed:
Futsal is played by two teams of four players. The additional participant is the goalkeeper. Teams must play 2 halves, and the duration, as in futsal, is 20 minutes.
How prepositions differ from prefixes (main differences)
Examples of words with the prefix under-: boletus, boletus, cup holder, chin, undergrowth, underground, window sill, suspension, bedding, stand, fit, support, entrance, approach, delivery, filed, undercut, suspension, etc.
- A prefix is the part of a word that comes before the root and serves to form a new word.
- A preposition is an official part of speech that connects words with each other.
5) Turn phrases with a preposition into words with a prefix:
- The next day everyone came on time(did you come on time when?) - the meaning of the adverb.
- The meeting is scheduled for tomorrow(appointed for what time?) - the meaning of a noun.
- genus. n. - coped (without what?) without errors;
- wines n. - paid (for what?) for electricity;
- dates n. - went (for what?) For bread;
- tv. n. - met (with whom?) With a friend;
- pr. p. - I thought (about what?) About the case.
Being completely different units of the language, prefixes and prepositions are defined as follows:
What is the difference between futsal and futsal
- The length of the field should be from twenty-eight to forty meters.
- The width can be from sixteen to twenty meters.
- The penalty area is a semi-circular area. It must be remembered that you cannot enter this territory, otherwise the rules of the game of futsal are violated.
- From the goal line must be extended six meters.
- On all edges of the penalty area has special rounding.
- Gate dimensions can be as follows: height - 2 meters, length - 3 meters.
In each case, futsal involves a certain strategy of the gameplay. Only if all the rules are taken into account, you can expect to achieve the best results.
It is assumed the possibility of using a smaller ball. In addition, the characteristics of a sports equipment can be much less, as a result of which the rebound becomes weaker.
A small field immediately dictates a certain rhythm of the gameplay. There is no time for any reflection. The gameplay should be fast and technical. A low level of contact is assumed, as a result of which mini-football can approach indoor sports. The distance from classical football is largely due to the need for gameplay on a small field, the constant movement of all players. It is assumed that the player must feel confident in the attack and in the defense of personal territory. For this reason, representatives of classical football, which always takes place over a large area, note a pronounced discomfort in the hall.
- The circumference should not exceed 58 - 60 centimeters.
- Weight can be 430 - 460 grams. If women or children participate in futsal, the weight can be reduced to 380 grams.
- The pressure should be 0.6 - 0.7 atmospheres, so that the first bounce of the ball used will contribute to the correct game process.
Futsal is a team game, which makes the gameplay immediately exciting. The number of participants on each side reaches 5. Each player must perform only their specific duties.
Insulin injection technique: algorithm and calculation, dose set in insulin therapy
It has been established that, in general, the need per day for patients with diabetes mellitus does not exceed one unit of the hormone per kilogram of its body weight. If this threshold is exceeded, then the likelihood of complications increases.
But since its functionality is impaired, the internal organ can no longer work in the previous, full-fledged mode, the production of the hormone is slow, while it is produced in small quantities. A person's condition worsens, and over time, the content of one's own insulin approaches zero.
Today, computer technology has become an integral part of our lives. They have introduced many terms into the dictionary of an ordinary 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 are faced with this every day.
History of the origin of the term
The concept of an algorithm was first formed by a mathematician named Mohammed 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 denoted 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 the algorithm is an outdated concept. Again, it actively came into use only with the advent of computers. They denoted the actions that were part of a certain process. But it doesn't have to be just mathematical. This implies an algorithm of actions of any nature, for example, the preparation of a dish. Since that time, this concept has not left the lips of almost all people.
Attempts to define the term
For a long time, this term was considered solely as an algorithm for numbers and actions with them. After all, mathematics itself was for the most part an applied science. Formulas that are used for calculations were considered algorithms at that time. The steps that were taken in the solution were elementary, and 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 seen before (matrices, vectors, sets, etc.). They all needed to be operated on. This gave impetus to the understanding that the algorithm is not an easy concept, and it needs to be precisely defined for further use. Scholars are divided on this issue. Some believed that the algorithm applied to everything, while others doubted that every problem could be solved with its help. The latter point of view turned out to be correct, but it could be substantiated only 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 different complexity. We are so used to simple ones that we perform actions to solve them automatically. Complex ones require a lot of thought. When a problem appears, we solve it in stages, acting in steps. So in mathematics, for example, to find the unknown in the 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 tasks 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 scheme of the algorithm provides for the solution of the problem 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 give room for any improvisation. This allows you to do everything mechanically, without the need for additional prompts.
- Efficiency - for a certain number of steps, the algorithm always gives the correct solution to the problem.
- Mass character - an algorithm is a solution to a problem that has a general form. That is, it is applicable to all tasks of a certain class, regardless of the source data. They are selected from a certain field called "algorithm applicability area".
Types of algorithms
Depending on different conditions, such as the goal, the solution path, the initial data, the algorithms are divided into:
- Mechanical - tough, the only true sequence to achieve the desired result (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 actions (prescriptions, etc.), because it is based on the personal qualities of a person, his experience.
- Auxiliary - previously developed and fully designed 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 over different source data, thus the most suitable ones are selected.
Structure of algorithms
Algorithms have their own structure, which is usually displayed in a diagram. An algorithm scheme is its graphic representation 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, as they are illustrative and provide a visual perception of the amount of work that needs to be done. A person can comprehend the process, correct it even before errors occur.
Rules for compiling algorithms
- The first rule is that you need to define a large number of objects that can succumb to the constructed algorithm. The programmer converts them into data using encoding. They are input and output. 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, it will not be possible to place the input data, work with them and get the output. Memory is made up of cells. If one of them is given 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 separate operations, or steps.
- The fourth rule recalls the determinism of the algorithm. That is, after each action, you need to specify which one will be next, or stop the process.
- The last rule says that after a certain number of steps, the algorithm ends its work with one result or another. 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 is computer science.
Today we will give an answer to the question of what an algorithm is.
It is often customary to call an algorithm a set of instructions that describe the necessary actions (as well as the order in which they are performed) in order to solve a given problem. Nowadays, algorithms are used not only in engineering and science, but also in other areas of life.
What is an algorithm
The concept of an algorithm is quite ancient and belongs to one of the main and also basic concepts in mathematics. The term comes from the Latin spelling of the name of the famous oriental mathematician of 787-850, Muhammad al-Khwarizmi - Algorithmi. This scientist was the first to formulate exact rules for writing natural numbers, as well as rules for summing up readings in a column. A rather interesting fact is that, despite the ancient roots, the concept itself was precisely formulated only at the beginning of the 20th century. Now the algorithm is the main component of modern business, any educational process or research. That is why every modern person simply needs to know exactly what the algorithm means.
Algorithm - often precise formulated instructions, the order of certain actions that should ensure the achievement of the goal.
What are properties of algorithms
But it is worth remembering that not every sequence of actions can be called an algorithm. A sequence is an algorithm only if it has certain properties. Let's list them:
- One of the most important properties is discreteness. We'll take a look at it below.
- Equally important is certainty. According to this property, each command must be unambiguous and direct the performer to a specific action.
- It is worth remembering about the clarity of the algorithm. The algorithm should use only the necessary commands that are relevant to the task.
- An important property is the effectiveness (also often called finiteness) of the algorithm. The “efficiency” property indicates that the algorithm has a certain, previously indicated number of steps, the execution of which will lead to the completion of the task.
- Also, any algorithm must necessarily have such a property as mass character. If the algorithm ensures the execution of all tasks of a certain type, then it has the property of mass character.
What is an algorithm in computer science
All scientists agree that the concept of an algorithm is fundamental in modern computer science. When creating software, the first step is always to create an algorithm.
An algorithm written in a formal language is called a program. Very often, the concept of an algorithm is closely associated with the process of writing it into a program. That is why the terms algorithm and program are often considered synonymous.
How to create an algorithm
In order to create an effective and high-quality algorithm, several rules should be observed:
- The algorithm must be written in a formal and clear language. Ambiguity or ambiguity of instructions is unacceptable.
- When compiling an algorithm, it is necessary to take into account the for whom it is compiled. The performer must understand all the points of the algorithm and be able to implement them.
- It is desirable to make the algorithm short, precise and clear.
What is a linear algorithm
Among all algorithms, linear and non-linear are distinguished. An algorithm is said to be linear if it follows a consistent order of operations throughout the execution process.
In computer science, the programming language with which an algorithm is described is usually called an operator. There are simple and structured operators. Simple statements describe only one action.
It is simple operators that are most often used in linear algorithms.
Algorithm discreteness property and its meaning
Earlier we mentioned that any algorithm has such a property as discreteness. Now let's consider the concept of discreteness in more detail.
Often, discreteness is replaced by such terms as discontinuity and separation of the algorithm. In fact, all three terms mean the same thing, namely, the sequential (alternate) execution of all the commands of the algorithm. When discreteness is observed, each action is performed only after the completion of the previous one, and the fulfillment of all the set points leads to the previously indicated final result (to the complete solution of the problem).
Now we have considered the main terms and concepts that relate to our today's topic. Surely for you now it is not a problem to answer the question of what is an algorithm. The acquired knowledge will be useful more than once both in your professional field and in everyday life. As always, you can clarify the details or find the answer to your question using the convenient comment system below.
