>> Types of algorithms

In algorithms, commands are written one after another in a certain order. They are not necessarily executed in a written sequence: depending on the order in which the commands are executed, three types of algorithms can be distinguished:

Linear algorithms;
branching algorithms;
algorithms with repetitions.

Linear algorithms

In which commands are executed in the order they are written, that is, sequentially one after another, is called linear.

For example, the following tree planting algorithm is linear:

1) dig a hole in the ground;
2) lower the seedling into the hole;
3) fill the hole with the seedling with soil;
4) water the seedling with water.

Using a block diagram, this algorithm can be depicted as follows:

Algorithms about branching

Situations where the sequence of required actions is known in advance are extremely rare. In life, you often have to make decisions depending on the current situation. If it rains, we take an umbrella and put on a raincoat; if it's hot, wear light clothes. There are also more complex selection conditions. In some cases, the future fate of a person depends on the chosen decision.

The decision logic can be described as follows:

IF<условие>THAT<действия 1>OTHERWISE<действия 2>

Examples:

IF you want to be healthy, THEN toughen up, OTHERWISE lie on the couch all day;
IF swallows fly low, THEN it will rain, OTHERWISE there will be no rain;
IF you have learned your lessons, THEN go for a walk, OTHERWISE learn your lessons.

In some cases<действия 2>may be absent;

IF<условие>THAT<действия 1>

Example:

IF you call yourself a milk mushroom, THEN get into the back.

A form of organizing actions in which, depending on the fulfillment of some condition, one or the other is performed subsequence steps is called branching.

Let us depict in the form of a flowchart the sequence of actions of 6th grade student Mukhin Vasya, which he imagines as follows: “If Pavlik is at home, we will solve problems in mathematics. Otherwise, we should call Marina and prepare a report on biology together. If Marina is not at home, then you need to sit down and write."

And so, with the help of a flowchart, you can very clearly present the reasoning when solving the following problem.

Of three coins of the same denomination, one is counterfeit (lighter). How to find it using one weighing on a cup scale without weights?

Algorithms with repetitions

In practice, there are often problems in which one or more actions need to be repeated several times until some predetermined condition is met.

Algorithm containing cycles, is called a cyclic algorithm or an algorithm with repetitions.

A situation in which a loop never ends is called looping. Algorithms should be developed to prevent such situations.

Let's look at an example from mathematics.

A natural number is called prime if it has only two divisors: one and the number itself1.

2, 3, 5, 7 - prime numbers; 4, 6, 8 - no. In the 3rd century BC, the Greek mathematician Eratosthenes proposed the following algorithm to find all prime numbers less than a given number n:

1) write down all natural numbers from 1 to n;
2) cross out 1;
3) underline the smallest of the unmarked numbers;
4) cross out all numbers that are multiples of what was underlined in the previous step;
5) if there are unmarked numbers in the list, then go to step 3, otherwise all the underlined numbers are prime.

This is a cyclic algorithm. When it is executed, steps 3-5 are repeated until there are unmarked numbers in the original list.

This is what a flowchart of actions looks like for a schoolboy who needs to do his math homework before an evening walk:

Let us remember that the number 1 is neither a composite number (those with more than two divisors) nor a prime number.

The most important

Depending on the order in which commands are executed, three types of algorithms can be distinguished:

> linear algorithms;
> branching algorithms;
> algorithms with repetitions.

An algorithm in which commands are executed in the order they were written, that is, sequentially one after another, is called linear.

The form of organizing actions in which, depending on the fulfillment of some condition, one or another sequence of steps is performed is called branching.

A form of organizing actions in which the execution of the same sequence of commands is repeated until some predetermined condition is met is called a cycle (repetition).

Questions and tasks

1. What algorithms are called linear?
2. Give an example of a linear algorithm,
3. The “Calculator” performer can perform only two commands: multiply by 2 and add. Come up with the shortest plan for him to obtain the number 50 from O.
4. What form of organization of actions is called branching?
5. What conditions did the heroine of the story “Geese and Swans” have to fulfill?
6. Give an example of an algorithm containing branching"
7. Read an excerpt from the poem by J. Rodari “What do crafts smell like?”:

Each case has a special smell:
The bakery smells of dough and baked goods.
You walk past a carpentry workshop -
It smells like shavings and fresh boards.
The painter smells like turpentine and paint.
The glazier smells like window putty.
The driver's jacket smells like gasoline
Worker's blouse - machine oiled.

Rephraseabout professions using the words “IF... THEN”/

8. Remember which Russian heroes folk tales make choices that determine their fate.
9. Out of 9 coins of the same denomination, one is counterfeit (lighter). In how many weighings on a cup scale without weights can you determine it?
10. What form of organizing actions is called repetition?
11. Give an example of an algorithm containing repetition.
12. In which literary works do you know does a cyclical form of organization of actions take place?
13. Where will the performer be who has completed the following group of commands 16 times in a row?

walk 10 meters forward

rotate 90° clockwise

14. Which group of actions and how many times should be repeated when solving the next problem?

Forty soldiers approached the river along which two boys were riding a boat. How can soldiers cross to the other side if the boat can only accommodate one soldier or two boys, but can no longer accommodate a soldier and a boy?

15. Remember the problem of a Calculator that can only multiply by 2 and add 1. It will be much easier to develop rational algorithms for it if you use the following block diagram:

Using this flowchart, develop rational algorithms for obtaining the numbers 1024 and 500 from 0.

Bosova L. L. Computer Science: Textbook for 6th grade / L. L. Bosova. - 3rd ed., rev. and additional - M.: BINOM. Laboratory of Knowledge, 2005. - 208 pp.: ill.

Lesson content lesson notes and supporting frame lesson presentation interactive technologies accelerator teaching methods Practice tests, testing online tasks and exercises homework workshops and trainings questions for class discussions Illustrations video and audio materials photographs, pictures, graphs, tables, diagrams, comics, parables, sayings, crosswords, anecdotes, jokes, quotes Add-ons abstracts cheat sheets tips for the curious articles (MAN) literature basic and additional dictionary of terms Improving textbooks and lessons correcting errors in the textbook, replacing outdated knowledge with new ones Only for teachers calendar plans learning programs guidelines

Theoretical information

Algorithm is a description of a sequence of actions (plan), the strict execution of which leads to the solution of a given problem in a finite number of steps.

Properties of algorithms:

1. Discreteness (the algorithm must consist of specific actions following in a certain order);

2. Determinism (any action must be strictly and unambiguously defined in each case);

3. Finiteness (each action and the algorithm as a whole must be able to be completed);

4. Massiveness (the same algorithm can be used with different source data);

5. Efficiency (no errors, the algorithm should lead to the correct result for all valid input values).

Types of algorithms:

1. Linear algorithm (description of actions that are performed once in a given order);

2. Round robin algorithm(description of actions that must be repeated a specified number of times or until the task is completed);

3. Branching algorithm (an algorithm in which, depending on the condition, either one or another sequence of actions is performed)

Examples of problem solving

Performer The draftsman moves on the coordinate plane, leaving a trace in the form of a line. The draftsman can execute the command Move to (a, b)(where a,b are integers), moving the Draftsman from a point with coordinates (x, y) to a point with coordinates (x + a, y + b). If the numbers a, b are positive, the value of the corresponding coordinate increases; if negative, it decreases.

For example, if the Draftsman is at a point with coordinates (9, 5), then the command Shift to

(1, -2) will move the Draftsman to point (10, 3).

Repeat k times

Team1 Team2 Team3

End

means that the sequence of commands Team1 Team2 Team3 will be repeated k times. The draftsman was given the following algorithm to execute:

Repeat 3 times

Shift by (-2, -3) Shift by (3, 2) Shift by (-4, 0)

End

What one command can this algorithm be replaced with so that the Draftsman ends up at the same point as after executing the algorithm?

1) Move to (-9, -3)

2) Move to (-3, 9)

3) Move to (-3, -1)

4) Move to (9, 3)

Solution:

This task is best solved sequentially.

In a loop, the Drafter executes a sequence of commands

– Move by (-2, -3)

– Move to (3, 2)

– Move to (-4, 0),

which can be replaced with one command: Move by (-2+3-4, -3+2+0), i.e. Move to (-3, -1).

Since the loop is repeated 3 times, the resulting command Shift by (-3, -1) will be executed 3 times. This means that the cycle can be replaced with the command Shift by (-3*3, -1*3), i.e. Move to (-9, -3). Thus, we get the command Move to (-9, -3) with which the entire algorithm can be replaced.

Tasks for training

1. Performer The draftsman moves on the coordinate plane, leaving a trace in the form of a line. The draftsman can execute the command Move to (a, b)(where a, b are integers), moving the Draftsman from a point with coordinates (x, y) to a point with coordinates (x + a, y + b). If the numbers a, b are positive, the value of the corresponding coordinate increases; if negative, decreases.

For example, if the Draftsman is at a point with coordinates (4, 2), then the Move to (2, −3) command will move the Draftsman to the point (6, −1).

Repeat k times

Team1 Team2 Team3

End

means that the sequence of commands Team1 Team2 Team3 will happen again k once.

The draftsman was given the following algorithm to execute:

Repeat 2 times

Move by (−6, −4)

After completing this algorithm, the Draftsman returned to the starting point. What command should be put instead of the command Team1?

1) Shift by (−2, −1)

2) Move to (1, 1)

3) Shift by (−4, −2)

4) Move to (2, 1)

2. Move to (a, b)

For example, if the Draftsman is at coordinates (4, 2), then the Move to (2, −3) command will move the Draftsman to the point (6, −1).

Repeat k times

Team1 Team2 Team3

End

Team1 Team2 Team3 will happen again k once.

Repeat 4 times

Command1 Move to (3, 3) Move to (1,−2) End

Shift by (−8, 12)

Team1?

1) Shift by (−2, −4)

2) Shift by (4,−13)

3) Move to (2, 4)

4) Shift by (−8, −16)

3. Performer The draftsman moves on the coordinate plane, leaving a trace in the form of a line. The draftsman can execute the command Move to (a, b)(where a, b are integers), moving the Draftsman from a point with coordinates (x, y) to a point with coordinates (x + a, y + b). If the numbers a, b are positive, the value of the corresponding coordinate increases; if negative, decreases.

Repeat k times

Team1 Team2 Team3

End

means that the sequence of commands Team1 Team2 Team3 will happen again k once.

The draftsman was given the following algorithm to execute:

Repeat 3 times

Move to (3, 9)

After completing this algorithm, the Draftsman returned to the starting point. What command should be put instead of the command Team1?

1) Shift to (3, 4)

2) Shift by (−5, −10)

3) Shift by (−9, −12)

4) Shift by (−3, −4)

4. Performer The draftsman moves on the coordinate plane, leaving a trace in the form of a line. The draftsman can execute the command Move to (a, b)(where a, b are integers), moving the Draftsman from a point with coordinates (x, y) to a point with coordinates (x + a, y + b). If the numbers a, b are positive, the value of the corresponding coordinate increases; if negative, decreases.

For example, if the Draftsman is at coordinates (4, 2), then the Move to (2, −3) command will move the Draftsman to the point (6, −1).

Repeat k times

Team1 Team2 Team3

End

means that the sequence of commands Team1 Team2 Team3 will happen again k once.

The draftsman was given the following algorithm to execute:

Repeat 3 times

Command1 Move to (3, 2) Move to (2, 1) End

Move to (−9, −6)

After completing this algorithm, the Draftsman returned to the starting point. What command should be put instead of the command Team1?

1) Shift by (−6, −3)

2) Move to (4, 3)

3) Shift by (−2, −1)

4) Move to (2, 1)

5. Performer The draftsman moves on the coordinate plane, leaving a trace in the form of a line. The draftsman can execute the command Move to (a, b)(where a, b are integers), moving the Draftsman from a point with coordinates (x, y) to a point with coordinates (x + a, y + b). If the numbers a, b are positive, the value of the corresponding coordinate increases; if negative, decreases.

Repeat k times

Team1 Team2 Team3

End

means that the sequence of commands Team1 Team2 Team3 will happen again k once.

The draftsman was given the following algorithm to execute:

Repeat 2 times

Command1 Move to (3, 3) Move to (1, −2) End

Shift by (4, −6)

After completing this algorithm, the Draftsman returned to the starting point. What command should be put instead of the command Team1?

1) Shift by (6, −2)

2) Shift by (−8, 5)

3) Shift by (−12, 4)

4) Shift by (−6, 2)

6. Performer The draftsman moves on the coordinate plane, leaving a trace in the form of a line. The draftsman can execute the command Move to (a, b)(where a, b are integers), moving the Draftsman from a point with coordinates (x, y) to a point with coordinates (x + a, y + b). If the numbers a, b are positive, the value of the corresponding coordinate increases; if negative, decreases.

For example, if the Draftsman is at coordinates (4, 2), then the Move to (2, −3) command will move the Draftsman to the point (6, −1).

Repeat k times

Team1 Team2 Team3

End

means that the sequence of commands Team1 Team2 Team3 will happen again k once.

The draftsman was given the following algorithm to execute:

Repeat 4 times

Command1 Move to (1, 3) Move to (1, −2) End

Shift by (−4, −12)

After completing this algorithm, the Draftsman returned to the starting point. What command should be put instead of the command Team1?

1) Shift by (1,−2)

2) Shift to (12, 4)

3) Move to (2, 11)

4) Shift by (−1, 2)

7. Performer The draftsman moves on the coordinate plane, leaving a trace in the form of a line. The draftsman can execute the command Move to (a, b)(where a, b are integers), moving the Draftsman from a point with coordinates (x, y) to a point with coordinates (x + a, y + b). If the numbers a, b are positive, the value of the corresponding coordinate increases; if negative, decreases.

For example, if the Draftsman is at coordinates (4, 2), then the Move to (2, −3) command will move the Draftsman to the point (6, −1).

Repeat k times

Team1 Team2 Team3

End

means that the sequence of commands Team1 Team2 Team3 will happen again k once.

The draftsman was given the following algorithm to execute:

Repeat 4 times

Command1 Move to (3, 2) Move to (2, 1) End

Move to (−12, −8)

After completing this algorithm, the Draftsman returned to the starting point. What command should be put instead of the command Team1?

1) Shift by (−8, −4)

2) Shift by (−2, −1)

3) Move to (7, 5)

4) Move to (2, 1)

8. Forward n Right m

Repeat 9 [Forward 50 Right 60]

1) regular hexagon

2) regular triangle

3) open broken line

4) regular hexagon

9. Performer The turtle moves on the computer screen, leaving a trace in the form of a line. At each specific moment, the position of the performer and the direction of his movement are known. The performer has two commands: Forward n(where n is an integer), causing the Turtle to move n steps in the direction of movement; Right m(where m is an integer), causing a change in the direction of movement by m degrees clockwise. Record Repeat k [Command1 Command2 Command3] means that the sequence of commands in brackets will be repeated k times.

The turtle was given the following algorithm to execute: Repeat 7 [Forward 70 Right 120]. What shape will appear on the screen?

1) regular hexagon

2) open broken line

3) regular heptagon

4) regular triangle

10. Performer The turtle moves on the computer screen, leaving a trace in the form of a line. At each specific moment, the position of the performer and the direction of his movement are known. The performer has two commands: Forward n(where n is an integer), causing the Turtle to move n steps in the direction of movement; Right m(where m is an integer), causing a change in the direction of movement by m degrees clockwise. Record Repeat k [Command1 Command2 Command3] means that the sequence of commands in brackets will be repeated k times.

The turtle was given the following algorithm to execute: Repeat 9 [Forward 70 Right 90]. What shape will appear on the screen?

2) regular hexagon

3) regular octagon

4) regular quadrilateral

11. Performer The turtle moves on the computer screen, leaving a trace in the form of a line. At each specific moment, the position of the performer and the direction of his movement are known. The performer has two commands: Forward n(where n is an integer), causing the Turtle to move n steps in the direction of movement; Right m(where m is an integer), causing a change in the direction of movement by m degrees clockwise. Record Repeat k [Command1 Command2 Command3] means that the sequence of commands in brackets will be repeated k times.

The turtle was given the following algorithm to execute: Repeat 5 [Forward 80 Right 60]. What shape will appear on the screen?

1) regular pentagon

2) regular triangle

3) regular hexagon

4) open broken line

12. Performer The turtle moves on the computer screen, leaving a trace in the form of a line. At each specific moment, the position of the performer and the direction of his movement are known. The performer has two commands: Forward n(where n is an integer), causing the Turtle to move n steps in the direction of movement; Right m(where m is an integer), causing a change in the direction of movement by m degrees clockwise. Record Repeat k [Command1 Command2 Command3] means that the sequence of commands in brackets will be repeated k times.

The turtle was given the following algorithm to execute: Repeat 5 [Forward 80 Right 90]. What shape will appear on the screen?

1) open broken line

2) regular hexagon

3) regular pentagon

4) regular quadrilateral

Theoretical information

Examples of problem solving

Tasks for training

Theoretical information

Examples of problem solving

Tasks for training

Theoretical information

Examples of problem solving

Tasks for training

Theoretical information

Examples of problem solving

Tasks for training

Theoretical information

Examples of problem solving

Tasks for training

Theoretical information

Examples of problem solving

Tasks for training

Theoretical information

Examples of problem solving

Tasks for training

Theoretical information

Examples of problem solving

Tasks for training

Theoretical information

Examples of problem solving

Tasks for training

MBOU "Glinnovskaya Secondary School"

Novooskolsky district

Belgorod region

Plan - lesson summary

(9th grade)

“Algorithms, concepts of algorithm, properties of algorithm. Executors of the algorithm"

Prepared by:

Learn computer science

Tarasova N.G.

2011

Subject: The concept of algorithms, properties of the algorithm. Executors of algorithms, system of executor commands. Methods for recording algorithms. Formal execution of algorithms.

Lesson type: familiarization with new material.

Goals:

1. Promote the development of algorithmic thinking;
2. Give the concept of an algorithm, talk about its properties, give a classification of algorithms;
3. Introduce the form of recording algorithms - flowchart.

Equipment : projector, presentation.

During the classes

1 org. Moment

Greeting, boarding, roll call.

2 Updating support material

Guys, please tell me, how do you understand the word algorithm? Where do we encounter 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 (full name - Muhammad ben Musa al-Khorezmi, i.e. Muhammad son of Musa from Khorezm), mathematician, astronomer, geographer lived in Baghdad. 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 a Latin translation of the 12th century remained, through which Western Europe became familiar with decimal system numbers and 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 (operation signs, brackets, letter symbols, etc.) had not yet been developed. However, he manages to develop a clear style of strict verbal instructions, which did not give the reader the opportunity to evade the prescribed or skip any actions.

The rules in the books of cm-Khorezmi in the Latin translation began with the words “Algorizmi said.” In other Latin translations the author was referred to as Algorithmus. Over time, it was forgotten that Algorizmi (Algorithmus) is the author of the rules, and these rules began to be called algorithms. For many centuries, algorithms were developed to solve more and more new classes of problems, but the very concept of an algorithm did not have an exact mathematical definition.

Currently, the concept of an algorithm has been clarified, and was made in the 20th century within 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 specific result.

The executor of the algorithm is some abstract or reala system capable of performing an action prescribed by an algorithm (technical, biological or biotechnical).

Technical executive– ATM;

Biological - a person, a living organism;

Biotechnology - artificial intelligence.

Properties of algorithms

Discreteness (separateness, discontinuity) – the algorithm must be written in the form of a sequence of steps or stages.

Understandability 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 a solution to the problem in a finite number of steps.

Mass character the algorithm is being developed in general view, so that it can be used to solve similar problems. In this case, the initial data is selected from certain areas, which are called the area of ​​application of the algorithms.

Ways to write algorithms

If the properties of certainty and discreteness are preserved with some degree of accuracy, i.e. the program can rearrange steps or it contains desirable but not mandatory steps, then this is not an algorithm, butalgorithmic prescription.

Every algorithm is designed for a specific performer. It can be a person, a robot, a computer, etc. Each performer has his own command system. When composing an algorithm, you need to take into account which performer it is designed for. The performer can carry out the algorithm without delving into the meaning of what he is doing, why he is doing it, and still get the desired result. In such cases, the algorithm is said to be executed formally.

Algorithm recording forms:

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 - a oriented graph indicating the order of execution of the algorithm's commands.

Graphic forms of recording 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. Algorithm for opening the door to the apartment: take out the key, insert it intokeyhole, turn the required number of times, take out the key, open the door. close the door)

Branching - data influences the progress of the algorithm, i.e. depending on the conditioncertain actions of the algorithm are performed.(Example, Algorithm for “getting” into your apartment: call the apartment; if there is someone at home, wait until the door is opened andenter the apartment if no one is home, get the key; ...)

Cycle(repetition)- during the execution of the algorithm, a certainset of commands. (Example.(Washing 10 plates: take the plate, wash it, put it in the dryer, takeplate, wash it, put it in the dryer, etc. until you run out of plates.)

4 Application of acquired knowledge

Task execute algorithm commands with a=1, b=2, c=3

| § 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
characteristics of the performer (range of tasks to be solved; environment; operating mode; command system)
formal execution of the algorithm

2.1.1. Algorithm concept

Every person in everyday life, in study or at work solves a huge number of problems of varying complexity. Complex problems require a lot of thought to find a solution; A person solves simple and familiar tasks without thinking, automatically. In most cases, the solution to each problem can be divided into simple stages (steps). For many such tasks (installation software, assembling a cabinet, creating a website, operating a technical device, purchasing an airline ticket via the Internet, etc.) have already been developed and offered step by step instructions, which, when executed consistently, can lead to the desired result.

Example 1. The problem “Find the arithmetic mean of two numbers” is solved in three steps:

1) think of two numbers;
2) add two planned numbers;
3) divide the resulting amount by 2.

Example 2. The task “Deposit money into your 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 entered number is correct;
5) insert a banknote into the bill acceptor;
6) wait for a message about money being credited to your account;
7) receive 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 telephone 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 strict adherence to which allows you to obtain the required result. The sequences of instructions 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 a certain sequence of calculations (example 1) or steps of a non-mathematical nature (examples 2-3). But in any case, before its development, the initial conditions (initial data) and what is to be obtained (result) must be clearly defined. We can say that an algorithm is a description of the sequence of steps in solving a problem, leading from the initial data to the required result.

In general, the algorithm’s operation diagram 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 in school, many grammatical rules, rules of geometric constructions, etc.

Animations “Working with an algorithm” (193576), “Greatest common divisor” (170363), “Least common multiple” (170390) will help you remember some algorithms studied in Russian language and mathematics lessons (http://sc.edu.ru /).

Example 4. Some algorithm leads to the fact that from one chain of characters a new chain is obtained as follows:

1. The length (in characters) of the original string of characters is calculated.
2. If the length of the original chain is odd, then the number 1 is added 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. The number 2 is added to the right of the resulting chain.

The resulting chain is the result of the algorithm.

So, if the initial chain was A#B, then the result of the algorithm will be the chain #A1B2, and if the initial chain was ABC@, then the result of the algorithm will be the chain BA@B2.

2.1.2. Algorithm executor

Each algorithm is designed for a specific performer.

The performer is some object (person, animal, technical device), capable of executing a specific set of commands.

Distinguish formal and informal performers. A formal performer always performs the same command in the same way. An informal executor can carry out a command in different ways.

Let us consider in more detail the set of formal performers. Formal performers are extremely diverse, but for each of them the following characteristics can be specified: the range of tasks to be solved (purpose), environment, command system and mode of operation.

Range of tasks to be solved. Each performer is created to solve a certain range of problems - constructing chains of symbols, performing calculations, constructing drawings on a plane, etc.

Artist environment. The area, setting, conditions in which the performer operates are usually called the environment of the given performer. The source data and results of any algorithm always belong to the environment of the performer for whom the algorithm is intended.

Executor command system. An instruction to a performer to perform a separate completed action is called a command. The set of all commands that can be executed by some executor forms the system of commands for this executor (SKI). The algorithm is compiled taking into account the capabilities of a specific performer, in other words, in the system of commands 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 waits for commands from a person and immediately executes each received 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 the named modes.

Let's look at examples of performers.

Example 5. Performer The turtle moves on the computer screen, leaving a trace in the form of a line.

The Turtle command system 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 in which its head and body are facing;
2. Right m (where m is an integer) - causes a change in the direction of the Turtle's movement by t degrees clockwise.
Record 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 completes the following algorithm.
Repeat 12 [Right 45 Forward 20 Right 45]

Example 6. The system of executor commands The computer consists of two commands, which are assigned numbers:

1 - subtract 1
2 - multiply by 3

The first of them decreases the number by 1, the second increases the number by 3 times. When writing algorithms, for brevity, only command numbers 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

Using this algorithm, the number 1 will be converted to 15:

((1 3 - 1) 3 - 1) 3 = 15.

Example 7. Performer Robot operates on a checkered field, between adjacent cells there may be walls. The robot moves along the cells of the field and can perform the following commands, which are assigned numbers:

1 - up
2 - down
3 - right
4 - left

When performing each such command, the Robot moves to an adjacent cell in the indicated direction. If there is a wall in this direction between the cells, then the Robot is destroyed.

What will happen to the Robot if it executes the sequence of commands 32323 (here the numbers indicate command numbers), starting to move from cell A? What sequence of commands should the Robot execute in order to move from cell A to cell B without collapsing when it hits the walls?

When developing an algorithm:

1) the objects appearing in the problem are identified, the properties of the objects, the relationships 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, ensuring the transition from the initial data to the result;
4) the sequence of actions is recorded using commands included in the performer’s command system.

We can say that an algorithm is a model of the activity of the algorithm executor.

2.1.3. Algorithm properties

Not every instruction, sequence of instructions, or action plan can be considered an algorithm. Each algorithm necessarily has the following properties: discreteness, understandability, certainty, effectiveness and mass character.

Discrete property means that the path to solving a problem is divided into separate steps (actions). Each action has a corresponding instruction (command). Only after executing one command can the executor begin executing the next command.

Understandability property means that the algorithm consists only of commands included in the system of commands of the performer, i.e., of such commands that the performer can perceive and according to which he can perform the required actions.

Property of certainty means that the algorithm does not contain commands whose meaning can be interpreted ambiguously by the performer; Situations are unacceptable when, after executing the next command, it is unclear to the performer which command to execute next. Thanks to this, the result of the algorithm is uniquely determined by the set of initial data: if the algorithm is applied several times to the same set of initial data, then the output always produces the same result.

Performance property means that the algorithm must provide a result after a finite, possibly very large, number of steps. In this case, the result is considered not only the answer determined by the statement of the problem, but also the conclusion about the impossibility of continuing to solve this problem for any reason.

Property of mass character means that the algorithm must provide the possibility of its application to solve any problem from a certain class of problems. For example, the algorithm for finding the roots of a quadratic equation should be applicable to any quadratic equation, the algorithm for crossing the street should be applicable anywhere on the street, the algorithm for preparing medicine should be applicable to preparing any quantity of it, etc.

Example 8. Let's 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 down in a row all the natural numbers from 2 to n (2, 3, 4, ..., n);
2) frame 2 - the first prime number;
3) cross out from the list all numbers divisible by the last prime number found;
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 another prime number;
5) repeat steps 3 and 4 until there are no unmarked numbers left.

You can get a more visual idea of ​​the method of finding prime numbers using 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;
understandability- each command is understandable to an 8th grade student performing this algorithm;
certainty- each command is interpreted and executed by the performer unambiguously; there are instructions on the order of execution of commands;
effectiveness- after a certain number of steps the result is achieved;
mass character- the sequence of actions is applicable for any natural number 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 that leads from initial data to the required result, which has the properties of discreteness, understandability, certainty, effectiveness and mass character.

2.1.4. Possibility of automation of human activities

Developing an algorithm is usually a labor-intensive task that requires a person to have deep knowledge, ingenuity and a lot of time.

Solving the problem by ready-made algorithm requires the performer only to strictly follow the given instructions.

Example 9. From a pile containing any number of objects greater than three, two players take turns taking one or two objects each. The winner is the one who can pick up all the remaining items on his next move.

Let's consider an algorithm, following which the first player will certainly ensure a win.

1. If the number of objects in the pile is a multiple of 3, then give way to the opponent, otherwise start the game by taking 1 or 2 objects so that the number of objects remaining is a multiple of 3.
2. With your next move, each time add the number of objects taken by your opponent to 3 (the number of remaining objects 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 activity. For this:

1) the process of solving a problem is presented as a sequence of simple operations;
2) a machine (automatic device) is created that is capable of performing these operations in the sequence specified in the algorithm;
3) a person is freed from routine activities, the execution of the algorithm is entrusted to an automatic device.

THE MOST IMPORTANT

Executor- some object (person, animal, technical device) capable of executing a certain set of commands.

A formal performer always performs the same command in the same way. For each formal executor you can specify: range of tasks to be solved, environment, command system and operating mode.

Algorithm- a description of the sequence of actions intended for a specific performer that leads from the initial data to the required result, which has the properties of discreteness, understandability, certainty, effectiveness and mass character.

Performer's ability to act formally provides the ability to automate human activities.

Questions and tasks

1. Read the presentation materials for the paragraph contained in the electronic appendix to the textbook. Does the presentation complement the information contained in the text of the paragraph? What slides could you add to your presentation?

2. What is called an algorithm?

3. Choose synonyms for the word “prescription”.

4. Give examples of algorithms you studied 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 performed by the “computer” performer?

8. Consider as a performer word processor, available on your computer. Describe the range of tasks solved by this performer and his environment.

9. What is a team, a system of performer commands?

10. What commands should a robot perform the following functions:

a) cashier in a store;
b) a janitor;
c) a security guard?

11. List the main properties of the algorithm.

12. What can the absence of any property in an algorithm lead to? Give examples.

13. What is the importance of being able to formally execute an algorithm?

14. The sequence of numbers is constructed 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 to be 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. A certain algorithm obtains a new chain 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 that follows in the Russian alphabet after the letter that was in last place in the original chain is written. If the letter “I” is in the last place in the original 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 chain of characters was “HOUSE”, then the result of the algorithm will be the chain “DOMMODN”. The character string “COM” is given. How many letters “O” will there be in the chain of characters that will be obtained if you apply the algorithm to this chain, and then apply the algorithm again to the result of its work?

16. Find an animation of the steps of Eratosthenes’ algorithm on the Internet. Use Eratosthenes' algorithm to find all prime numbers not exceeding 50.

17. What will be the result of Turtle’s execution (see example 5) of the algorithm?

18. Write down an algorithm for the Calculator executor (see example 6), containing no more than 5 commands:

a) receiving from the number 3 the number 16;
b) receiving from the number 1 the number 25.

19. System of performer commands 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 added 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 algorithm 22212? Create an algorithm in the command system of this executor, according to which the number 1 will be converted into the number 16 (the algorithm should contain no more than 5 commands).

20. In which cell should the Robot performer (example 7) be located in order to return to it after executing algorithm 3241?

Free Software:

KuMir system - Set of educational worlds (download the program archive from the website) or visit the KuMir page ((http://www.niisi.ru/kumir/)