| § 2.1. Algorithms and Executors
Lesson 14
§ 2.1. Algorithms and Executors
Keywords:
Algorithm
properties of the algorithm (discreteness; understandability; certainty; effectiveness; mass character)
executor
performer characteristics (range of tasks to be solved; environment; mode of operation; system of commands)
formal execution of the algorithm
2.1.1. The concept of an algorithm
Each person in everyday life, in school or at work, solves a huge number of tasks of very different complexity. Difficult problems require much thought to find a solution; simple and familiar tasks a person solves without thinking, automatically. In most cases, the solution of each problem can be broken down into simple stages (steps). For many of these tasks (installing software, assembling a cabinet, creating a website, operating a technical device, buying an air ticket via the Internet, etc.), step-by-step instructions have already been developed and are offered, with sequential execution of which you can achieve the desired result.
Example 1 The task "Find the arithmetic mean of two numbers" is solved in three steps:
1) think of two numbers;
2) add two conceived numbers;
3) Divide the amount received by 2.
Example 2 The task "Deposit money to the phone account" is divided into the following steps:
1) go to the payment terminal;
2) choose a telecom operator;
3) enter a phone number;
4) check the correctness of the entered number;
5) insert a banknote into the bill acceptor;
6) wait for a message about crediting money to the account;
7) get a check.
Example 3 The stages of solving the problem "Draw a funny hedgehog" are presented graphically:
Finding the arithmetic mean, depositing money into a phone account, and drawing a hedgehog are, at first glance, completely different processes. But they have a common feature: each of these processes is described by a sequence of brief instructions, the exact following of which allows you to get the desired result. The sequences of indications given in examples 1-3 are algorithms for solving the corresponding problems. The executor of these algorithms is a person.
The algorithm can be a description of some sequence of calculations (example 1) or non-mathematical steps (examples 2-3). But in any case, before its development, the initial conditions (initial data) and what is to be obtained (result) should be clearly defined. We can say that an algorithm is a description of a sequence of steps in solving a problem that leads from the initial data to the desired result.
In general, the scheme of the algorithm can be represented as follows (Fig. 2.1).
Rice. 2.1. General scheme of the algorithm
Algorithms are the rules of addition, subtraction, multiplication and division of numbers studied at school, many grammar rules, rules of geometric constructions, etc.
The animations "Working with the algorithm" (193576), "Greatest common divisor" (170363), "Least common multiple" (170390) will help you remember some of the algorithms learned in the Russian language and mathematics lessons (http://sc.edu.ru /).
Example 4 Some algorithm leads to the fact that from one string of characters a new string is obtained as follows:
1. The length (in characters) of the original character string is calculated.
2. If the length of the original chain is odd, then the number 1 is assigned to the original chain on the right, otherwise the chain does not change.
3. The symbols are swapped in pairs (the first - with the second, the third - with the fourth, the fifth - with the sixth, etc.).
4. On the right, the number 2 is assigned to the received chain.
The resulting chain is the result of the algorithm.
So, if the original chain was A # B, then the result of the algorithm will be the chain # A1B2, and if the original chain was ABC @, then the result of the algorithm will be the chain BA @ B2.
2.1.2. Algorithm performer
Each algorithm is designed for a specific performer.
An executor is some object (a person, an animal, a technical device) capable of executing a certain set of commands.
Distinguish formal and informal performers. A formal executor always executes the same command in the same way. An informal executor can execute a command in different ways.
Let us consider in more detail the set of formal executors. Formal executors are extremely diverse, but for each of them the following characteristics can be indicated: the range of tasks to be solved (appointment), environment, command system, and mode of operation.
Range of tasks to be solved. Each executor is created to solve a certain range of tasks - building symbol chains, performing calculations, drawing pictures on a plane, etc.
Executor environment. The area, environment, conditions in which the performer operates are usually called the environment of this performer. The input data and results of any algorithm always belong to the environment of the executor for which the algorithm is intended.
Executor command system. The instruction to the performer to perform a separate completed action is called a command. The set of all commands that can be executed by a certain performer forms a command system of this performer (CIS). The algorithm is compiled taking into account the capabilities of a particular performer, in other words, in the command system of the performer who will execute it.
Performer operating modes. For most performers, direct control and program control modes are provided. In the first case, the performer expects commands from a person and immediately executes each incoming command. In the second case, the performer is first given a complete sequence of commands (program), and then he executes all these commands in automatic mode. A number of performers work only in one of these modes.
Consider examples of performers.
Example 5 Performer Turtle moves on the computer screen, leaving a trail in the form of a line.
The command system of the Turtle consists of the following commands:
1. Forward n (where n is an integer) - causes the Turtle to move n steps in the direction of movement - in the direction where its head and body are turned;
2. Right m (where m is an integer) - causes the Turtle to change direction by m degrees clockwise.
Recording Repeat k[<Команда1> <Команда2> ... <Командаn>]
means that the sequence of commands in brackets will be repeated k times.
Think about what figure will appear on the screen after the Turtle executes the following algorithm.
Repeat 12 [Right 45 Forward 20 Right 45]
Example 6 Command system of the executor The calculator consists of two commands, which are assigned numbers:
1 - subtract 1
2 - multiply by 3
The first of them reduces the number by 1, the second increases the number by 3 times. When writing algorithms, for brevity, only the numbers of commands are indicated. For example, algorithm 21212 means the following sequence of commands:
Multiply by 3
subtract 1
multiply by 3
subtract 1
multiply by 3
With this algorithm, the number 1 will be converted to 15:
((1 3 - 1) 3 - 1) 3 = 15.
Example 7 The Executor Robot operates on a checkered field, between adjacent cells of which there can be walls. The robot moves through the cells of the field and can execute the following commands, which are assigned numbers:
1 - up
2 - down
3 - right
4 - left
When each such command is executed, the Robot moves to the next cell in the specified direction. If there is a wall between the cells in this direction, then the Robot is destroyed.
What will happen to the Robot if it executes the sequence of commands 32323 (here the numbers indicate the command numbers) starting from cell A? What sequence of commands should the Robot execute in order to move from cell A to cell B without colliding with the walls?
When developing an algorithm:
1) the objects appearing in the task are distinguished, the properties of the objects, the relations between the objects and possible actions with the objects are established;
2) the initial data and the required result are determined;
3) the sequence of actions of the performer is determined, which ensures the transition from the initial data to the result;
4) the sequence of actions is recorded using commands included in the executor's command system.
We can say that an algorithm is a model of the activity of an executor of algorithms.
2.1.3. Algorithm Properties
Not any instruction, sequence of prescriptions or plan of action can be considered an algorithm. Each algorithm necessarily has the following properties: discreteness, comprehensibility, certainty, efficiency and mass character.
Discrete property means that the way to solve the problem is divided into separate steps (actions). Each action corresponds to a prescription (command). Only after executing one command, the executor can start executing the next command.
comprehensibility property means that the algorithm consists only of commands included in the executor's command system, i.e., of such commands that the executor can perceive and on which he can perform the required actions.
Definiteness property means that there are no commands in the algorithm, the meaning of which can be interpreted by the performer ambiguously; Situations are unacceptable when, after executing the next command, it is not clear to the executor which command to execute next. Due to this, the result of the algorithm is uniquely determined by the set of input data: if the algorithm is applied several times to the same set of input data, then the output is always the same result.
performance property means that the algorithm must ensure that the result is obtained after a finite, possibly very large, number of steps. In this case, the result is considered not only the answer due to the formulation of the problem, but also the conclusion that it is impossible to continue for any reason the solution of this problem.
Mass property means that the algorithm must provide the possibility of its application to solve any problem from a certain class of problems. For example, an algorithm for finding the roots of a quadratic equation must be applicable to any quadratic equation, a street crossing algorithm must be applicable to any place on the street, a medicine preparation algorithm must be applicable to the preparation of any amount of it, etc.
Example 8 Consider one of the methods for finding all prime numbers not exceeding some natural number n. This method is called the "sieve of Eratosthenes" after the ancient Greek scientist Eratosthenes (3rd century BC) who proposed it.
To find all prime numbers not greater than a given number n, following the method of Eratosthenes, you need to perform the following steps:
1) write out in a row all natural numbers from 2 to n (2, 3, 4, ..., n);
2) to enclose in a frame 2 - the first prime number;
3) delete from the list all numbers divisible by the last found prime number;
4) find the first unmarked number (marked numbers are crossed out numbers or numbers enclosed in a frame) and enclose it in a frame - this will be the next prime number;
5) repeat steps 3 and 4 until there are no unmarked numbers left.
You can get a better idea of the method of finding prime numbers with the help of the animation "Sieve of Eratosthenes" (180279) posted in the Unified Collection of Digital Educational Resources.
The considered sequence of actions is an algorithm, since it satisfies the following properties:
discreteness- the process of finding prime numbers is divided into steps;
intelligibility- each command is understandable to a 8th grade student who performs this algorithm;
certainty- each command is interpreted and executed by the performer unambiguously; there are instructions on the order of execution of commands;
performance- after a certain number of steps, the result is achieved;
mass character- the sequence of actions is applicable for any natural n.
The considered properties of the algorithm allow us to give a more precise definition of the algorithm.
An algorithm is a description of a sequence of actions intended for a specific performer, leading from the initial data to the desired result, which has the properties of discreteness, understandability, certainty, effectiveness and mass character.
2.1.4. Ability to automate human activities
The development of an algorithm is, as a rule, a time-consuming task that requires deep knowledge, ingenuity and a lot of time from a person.
Solving the problem using a ready-made algorithm requires the performer only to strictly follow the given instructions.
Example 9 From a pile containing any, more than three, number of any items, two players take turns taking one or two items each. The winner is the one who can pick up all the remaining items with his next move.
Let's consider an algorithm, following which the first player will surely secure a win.
1. If the number of items in the pile is a multiple of 3, then give way to the opponent, otherwise start the game by taking 1 or 2 items so that the number of items left is a multiple of 3.
2. With your next move, each time add the number of items taken by the opponent to 3 (the number of remaining items must be a multiple of 3).
The performer may not delve into the meaning of what he is doing, and not reason why he acts this way and not otherwise, that is, he can act formally. The ability of the performer to act formally provides the possibility of automating human activities. For this:
1) the process of solving the problem is represented as a sequence of simple operations;
2) a machine (an automatic device) is created that is capable of performing these operations in the sequence specified in the algorithm;
3) a person is released from routine activities, the execution of the algorithm is entrusted to an automatic device.
THE MOST IMPORTANT THING
Executor- some object (human, animal, technical device) capable of executing a certain set of commands.
A formal executor always executes the same command in the same way. For each formal executor, you can specify: range of tasks to be solved, environment, command system and mode of operation.
Algorithm- a description of the sequence of actions intended for a specific performer, leading from the initial data to the required result, which has the properties of discreteness, understandability, certainty, effectiveness and mass character.
The performer's ability to act formally provides the possibility of automating human activities.
Questions and tasks
1. Familiarize yourself with the presentation materials for the paragraph contained in the electronic supplement to the textbook. Does the presentation complement the information contained in the text of the paragraph? What slides would you like to add to your presentation?
2. What is called an algorithm?
3. Pick up synonyms for the word "prescription".
4. Give examples of algorithms you study in school.
5. Who can be the executor of the algorithm?
6. Give an example of a formal performer. Give an example when a person acts as a formal performer.
7. What determines the range of tasks to be solved by the executor "computer"?
8. Consider a word processor on your computer as an executor. Describe the range of tasks solved by this executor and its environment.
9. What is a team, a system of commands for an executor?
10. What commands should the robot perform the following functions:
a) a cashier in a store;
b) janitor;
c) a security guard?
11. List the main properties of the algorithm.
12. What can the absence of any property of an algorithm lead to? Give examples.
13. What is the importance of the possibility of formal execution of the algorithm?
14. The sequence of numbers is built according to the following algorithm: the first two numbers of the sequence are taken equal to 1; each next number in the sequence is taken equal to the sum of the two previous numbers. Write down the first 10 terms of this sequence. Find out what this sequence is called.
15. Some algorithm obtains a new string from one string of characters as follows. First, the original chain of characters is written, after it the original chain of characters is written in reverse order, then the letter is written that follows in the Russian alphabet the letter that was in last place in the original chain. If the letter “I” is in the last place in the initial chain, then the letter “A” is written as the next letter. The resulting chain is the result of the algorithm. For example, if the original character string was "HOME", then the result of the algorithm will be the string "DOMMODN". Given a string of characters "KOM". How many letters "O" will be in the chain of characters that will result if we apply the algorithm to this chain, and then apply the algorithm again to the result of its work?
16. Find on the Internet an animation of the steps of the Eratosthenes algorithm. Use Eratosthenes' algorithm to find all prime numbers less than 50.
17. What will be the result of the execution of the algorithm by the Turtle (see example 5)?
18. Write an algorithm for the executor Calculator (see example 6), containing no more than 5 commands:
a) receiving from the number 3 the number 16;
b) obtaining from the number 1 the number 25.
19. Command system of the executor The constructor consists of two commands, which are assigned numbers:
1 - assign 2
2 - divide by 2
According to the first of them, 2 is assigned to the number on the right, according to the second, the number is divided by 2. How will the number 8 be converted if the performer executes the algorithm 22212? Make an algorithm in the command system of this performer, according to which the number 1 will be converted to the number 16 (there should be no more than 5 commands in the algorithm).
20. In what cell should the executor Robot be located (example 7) in order to return to it after the execution of algorithm 3241?
Free software:
KuMir system - A set of educational worlds (download the archive of the program from the site) or visit the KuMir page ((http://www.niisi.ru/kumir/)
The word "algorithm" comes from the name of the Arab mathematician of the 9th century al-Khwarizmi, who formulated the rules for performing arithmetic operations.
Algorithm- an exact and understandable instruction to the performer to execute a final sequence of commands leading from the initial data to the initial result.
Examples: daily routine, cooking order, instructions, etc.)
Algorithm performer is the one who executes the algorithm (human, animal, machine, computer).
Executor command system- this is the whole set of commands that the performer can execute (understand). The algorithm can be built only from commands included in the command system of the executor.
for example, the executor Robot can execute commands forward, backward, left, right, paint over. It moves across a cellular field bounded by a wall and containing walls. The robot cannot pass through the wall.
Algorithm properties:
1.Efficiency (finiteness)– the possibility of obtaining a result from the initial data in a finite number of steps. (For example, when executing the addition algorithm, 2 numbers should get the sum).
2.mass character– the possibility of applying the algorithm to a large number of different initial data. (For example, You can add any 2 numbers, knowing the addition algorithm.)
3.determinism(definiteness, accuracy) - each team must uniquely determine the action of the performer.
4.Clarity- the command must be written in a language understandable to the computer.
5.discreteness– splitting the algorithm into separate commands.
Algorithm writing methods:
1) In natural language - recording in the form of separate commands in a language understandable to a person.
2) Graphic - in the language of block diagrams, using geometric shapes (oval, rectangle, parallelogram, rhombus).
3) In an algorithmic language - a language for writing algorithms for teaching programming. Teams are written in Russian.
4) In a programming language, a program. Programming languages: Basic, Pascal, C, Visual Basic.
B7. Basic algorithmic structures: following, branching, loop; image on block diagrams. Splitting tasks into subtasks. Auxiliary algorithms.
Algorithmic constructions. Within the algorithms, groups of steps can be distinguished that differ in their internal structure - algorithmic constructions.
Basic algorithmic constructions are a linear sequence of steps (or following), a branch, and a loop.
An algorithm in which commands are executed sequentially one after another is called linear algorithm.
This is how a linear algorithm looks like in the flowchart language:
Example: algorithm for turning on the computer:
- Turn on the computer power (press the button on the surge protector).
- Turn on the monitor, printer.
- Press the Power button on the system unit.
- Wait for the operating system to load and the desktop to appear.
- Get to work.
In this algorithm, all actions must be performed sequentially one after another: you cannot start working if the power or monitor is not turned on.
into an algorithmic structure branching» included condition, depending on the truth of the condition, one or another sequence of commands (series) is executed.
A condition is a statement that can be true or false. In a condition, two numbers, two strings, two variables or string expressions are compared with each other using the comparison operators (>,<, =, >=, <=).
In algorithmic structures cycle includes a series of commands that are executed repeatedly. This sequence of commands is called loop body.
Cyclic algorithmic structures are of two types:
- cycles with counter, in which the loop body is executed a certain number of times;
- conditional loops, in which the loop body is executed as long as the condition is met.
Loop with counter- is used when it is known in advance how many repetitions of the loop body must be performed.
Please pause AdBlock on this site.
In this lesson, we will analyze some theoretical concepts that formalize the concept of programming. At the same time, we will more precisely formulate the main task of your training.
To get started, I suggest you play a little with the next children's toy. Go through the first five tasks, go back and continue reading the lesson.
Fig.1 Screenshot of the playing field on code.org
I hope everything worked out for you. Now, using this example, we will describe a few basic concepts:
- executor;
- executor's command system;
- algorithm.
In the toy we control a red bird. The task of each stage is to get the bird to the pig. The bird can perform certain commands, for example: move forward, turn left, turn right, etc.
A person, machine, or device that can execute some command is called an executor. In this toy, obviously, the performer is a bird. A set of commands that an executor understands and can execute is called executor's command system.
The sequence of commands that an executor must execute to solve a problem is called an algorithm.
It is necessary to focus on several points.
An executor can execute only those commands that are included in his command system.
This means, for example, that you cannot write to a bird performer: “Go to the pig!”. You can write it down more precisely, but nothing will happen, because. the executor of such commands does not know.
You can write the available commands in any order that you deem correct. Your task as a programmer is to divide a large complex task into small separate steps, each of which will be understandable to the performer. The principle of "divide and conquer" works again.
The performer performs exactly what the algorithm prescribes to him.
The performer-bird is very trusting. It doesn't question what you write in the program. If, for example, you forget to turn the bird around, it will crash into the wall. So you have to take care of everything yourself.
Your future programs will often not work the way you intended. Mistakes happen to everyone. It is important to understand here that this is not a computer fool, but you made a mistake in the algorithm. Do not be like bad programmers who always blame the program for everything.
Now let's move on from a visual example to computer realities. We write programs for the computer, which means that the computer in our case is the executor. The command system is the standard functions and constructs of the C language.
What is the main goal of your learning the basics of programming? Master the skill of algorithmic thinking. That is, to learn how to write down the solution of various problems in the form of an algorithm for a specific performer (in our case, a computer).
So let's recap:
computer program- an algorithm for solving a problem, written in a programming language.
An algorithm is a precise description of the order of actions that an executor must perform in order to solve a problem.
An executor is a person or some device that can understand and execute a certain set of commands.
The concept of an algorithm. Algorithm implementers. Properties of algorithms
The concept of an algorithm is as fundamental to computer science as the concept of information. There are many different definitions of the algorithm, since this concept is quite broad and is used in various fields of science, technology and everyday life.
An algorithm is a clear and precise sequence of actions that describes the process of transforming an object from an initial state to a final one.
An algorithm is an exact description of the sequence of actions aimed at solving a given problem intended for a specific performer.
Contractor An algorithm can be either a person (cooking recipes, various instructions, algorithms for mathematical calculations), or a technical device. Various machines (computers, industrial robots, modern household appliances) are formal executors algorithms. A formal executor is not required to understand the essence of the problem being solved, but the exact execution of a sequence of commands is required.
The algorithm can be written in various ways (verbal description, graphic description - block diagram, program in one of the programming languages, etc.). A program is an algorithm written inprogramming language .
To create an algorithm (program), you need to know:
a complete set of initial data of the task (the initial state of the object);
the purpose of creating the algorithm (the final state of the object);
the executor's command system (that is, the set of commands that the executor understands and can execute).
The resulting algorithm (program) must have the following set of properties:
discreteness (the algorithm is divided into separate steps - commands);
uniqueness (each command determines the only possible action of the performer);
intelligibility (all commands of the algorithm are included in the command system of the executor);
efficiency (the performer must solve the problem in a finite number of steps).
Most algorithms also have the property mass character (using the same algorithm, you can solve many problems of the same type).
Ways to describe algorithms
It was noted above that the same algorithm can be written in different ways. You can write an algorithm natural language. In this form, we use recipes, instructions, etc. To write algorithms intended for formal executors, special programming languages. Any algorithm can be described graphically in block diagram form. For this, a special notation system has been developed:
|
Designation |
Description |
Notes |
|
Beginning and end of the algorithm | ||
|
|
Data input and output. |
Data output is sometimes referred to differently:
|
|
|
Action |
In computational algorithms, this is the assignment |
|
|
Fork |
Fork - a component necessary for the implementation of branches and loops |
|
|
Starting a Loop with a Parameter | |
|
|
Sample Process |
In programming, procedures or subroutines |
|
|
Transitions between blocks |
Let us give an example of a description of the algorithm for summing two quantities in the form of a block diagram:
This way of describing the algorithm is the most clear and understandable to a person. Therefore, algorithms of formal executors are usually developed first in the form of a block diagram, and only then a program is created on one ofprogramming languages .
Typical algorithmic structures
The programmer has the ability to construct and use non-typical algorithmic structures, however, this is not necessary. Any arbitrarily complex algorithm can be developed on the basis of three typical structures: following, branching, and repeating. In this case, the structures can be located sequentially one after another or nested in each other.
Linear structure (following)
The simplest algorithmic structure is linear. In it, all operations are performed once in the order in which they are written.
branching
AT full branching there are two options for the executor's actions depending on the value of the logical expression (condition). If the condition is true, then only the first branch will be executed, otherwise only the second branch.
The second branch may be empty. Such a structure is called incomplete branching or traversal.
From several branches, you can construct the structure " choice” (multiple branching), which will choose not from two, but from more options for the performer, depending on several conditions. It is essential that only one branch is executed - in such a structure, the order of the conditions becomes important: if several conditions are met, then only one of them will work - the first from the top.
Cycle (repetition)
Cycleallows you to organize repeated repetition of the same sequence of commands- it is called the body of the cycle. In various types of cyclic algorithms, the number of repetitions may depend on the value of the logical expression (condition) or may be rigidly specified in the structure itself. There are cycles: before», « Bye», cycles with a counter. In "until" and "while" loops, a logical expression (condition) may precede the loop body ( loop with precondition) or terminate the loop ( loop with postcondition).
Cycles« before» - repetition of the loop body until the condition is met:
Cycles « Bye» - repetition of the loop body while the condition is met(true):
Cycles with a counter(with parameter)– repetition of the loop body a given number of times:
Auxiliary algorithm (subroutine, procedure)
Helper Algorithm is a module that can be repeatedly accessed from the main algorithm. The use of auxiliary algorithms can significantly reduce the size of the algorithm and simplify its development.
Methods for developing complex algorithms
There are two methods for developing complex algorithms:
Method of sequential detailing of the problem(“top-down”) is that the original complex task is divided into subtasks. Each of the subtasks is considered and solved separately. If any of the subtasks are complex, they are also broken down into subtasks. The process continues until the subtasks are reduced to elementary ones. The solutions of individual subtasks are then assembled into a single algorithm for solving the original problem. The method is widely used, as it allows several programmers to develop a common algorithm at the same time, solving local subtasks. This is a necessary condition for the rapid development of software products.
assembly method("bottom-up") is to create a set of software modules that implement the solution of typical tasks. When solving a complex problem, a programmer can use the developed modules as auxiliary algorithms (procedures). In many programming systems Similar sets of modules already exist, which greatly simplifies and speeds up the creation of a complex algorithm.
Algorithms and control processes
Control - purposeful interaction of objects, some of which are control, others are controlled.
In the simplest case, there are two such objects:
From a computer science point of view control actions can be considered as control information. The information may be transmitted in the form of commands. A sequence of commands to control an object, leading to a predetermined goal, is called control algorithm. Therefore, the control object can be called the executor of the control algorithm. In the considered example, the control object works "without looking" at what is happening with the control object ( open loop control open. Another control scheme can take into account information about the processes occurring in the control object:
In this case, the control algorithm must be flexible enough to analyze this information and decide on its further actions depending on the state of the control object ( feedback control). This control scheme is called closed.
In more detail, management processes are studied are considered cybernetics. This science claims that the most diverse management processes in society, nature and technology occur in a similar way, obey the same principles.
Topic start
MBOU "Glinnovskaya secondary school"
Novooskolsky district
Belgorod region
Plan - lesson summary
(grade 9)
“Algorithms, concepts of an algorithm, properties of an algorithm. Algorithm performers»
Prepared by:
Learn computer science
Tarasova N.G.
2011
Subject: The concept of algorithms, properties of the algorithm. Algorithm executors, executor's command system. Ways of writing algorithms. Formal execution of algorithms.
lesson type: introduction to new material.
Goals:
- Contribute to the development of algorithmic thinking;
- Give the concept of an algorithm, talk about its properties, give a classification of algorithms;
- To acquaint with the form of writing algorithms - a flowchart.
Equipment : projector, presentation.
During the classes
1 org. Moment
Greeting, landing, roll call.
2 Updating the reference material
Guys, tell me please, how do you understand the word algorithm? Where do we come across this concept?
3 Presentation of the material
The origin of the term "algorithm" is related to mathematics. The history of its origin is as follows. In the 9th century, the scientist al(al)-Khorezmi lived in Baghdad (full name - Mohammed bin Musa al-Khorezmi, i.e. Mohammed son of Musa from Khorezm), mathematician, astronomer, geographer. In one of his works, he described the decimal number system and for the first time formulated the rules for performing arithmetic operations on integers and ordinary fractions. The Arabic original of this book was lost, but the Latin translation of the 12th century remained, according to which Western Europe got acquainted with the decimal number system and the rules for performing arithmetic operations.
Al-Khwarizmi sought to ensure that the rules he formulated were understandable. It was difficult to achieve this in the 9th century, when mathematical symbols (signs of operations, brackets, letter designations, etc.) had not yet been developed. However, he manages to develop a clear style of strict verbal prescription that does not give the reader the opportunity to evade the prescribed or skip any actions.
The rules in the books of cm-Khorezmi in Latin translation began with the words "Algorizmi said." In other Latin translations, the author was referred to as Algoritmus. Over time, it was forgotten that Algorism (Algorithm) is the author of the rules, and these rules began to be called algorithms. For many centuries, algorithms have been developed to solve more and more new classes of problems, but the concept of an algorithm itself did not have an exact mathematical definition.
At present, the concept of an algorithm has been refined, and made in the 20th century in the framework of a science called the theory of algorithms.
Algorithm - precise and understandable instructions to the performer to perform a sequence of actions aimed at solving the task.
Algorithm - clearly organized sequential action leading to a certain result.
An executor of an algorithm is some abstract or reala system capable of performing an action prescribed by an algorithm (technical, biological or biotechnical).
Technical executor- ATM;
Biological - a person, a living organism;
Biotechnology - artificial intelligence.
Properties of algorithms
discreteness (separation, discontinuity) - the algorithm should be written as a sequence of steps or stages.
Clarity The executor of the algorithm must know how to execute this algorithm.
Certainty (determinism) each rule of the algorithm must be clear, unambiguous and leave no room for arbitrariness.
Due to this property, the execution of the algorithm is mechanical in nature and does not require additional instructions.
Efficiency(finiteness) the algorithm must lead to the solution of the problem in a finite number of steps.
mass character the algorithm is developed in a general form so that it can be applied to solve problems of the same type. In this case, the initial data are selected from some areas, which are called the scope of the algorithms.
Ways to write algorithms
If the properties of certainty and discreteness are preserved with a certain degree of accuracy i.e. the program can rearrange the steps or it contains desirable, but not mandatory steps, then this is not an algorithm, butalgorithmic prescription.
Every algorithm is designed for a certain performer. It can be a person, a robot, a computer, etc. each performer has his own command system. When compiling an algorithm, it is necessary to take into account which performer it is designed for. The performer can execute the algorithm without delving into the meaning of what he is doing, why he is doing it, and nevertheless he will get the desired result. In such cases, the algorithm is said to be executed formally.
Forms of writing algorithms:
Verbal is a description of the successive stages of data processing. The algorithm is an arbitrary presentation in natural language
Graphic - a sequence of interconnected blocks, each of which corresponds to the execution of one or more actions.
Such a graphical representation is called a block diagram - directed graph indicating the order of execution of the commands of the algorithm.
Graphical forms of writing algorithms:
Basic Algorithmic Structures
Following (linear algorithm) Loops
branching
following – commands are executed one after another in the order in which they are written in the algorithm.((Example. The algorithm for opening the door to the apartment: get the key, insert it intokeyhole, turn the required number of times, get the key, open the door. close the door)
branching - the data affects the course of the algorithm, i.e. depending on the conditioncertain actions of the algorithm are performed.(Example, Algorithm of "getting" into your apartment: call the apartment; if there is someone at home, wait until the door is opened andenter the apartment, if there is no one at home, get the key; ...)
Cycle (repetition)- in the process of executing the algorithm, a certaincommand set. (Example.(Washing 10 plates: take a plate, wash, dry, takeplate, wash, dry, etc. until the plates run out.)
4 Application of acquired knowledge
Task execute algorithm commands with a=1, b=2, c=3
