Types of algorithms according to the sequence of execution of command steps. Computer Science and Information Technology

Keywords:

algorithm
properties of the algorithm
- discreteness
- clarity
- certainty
- effectiveness
- mass character
executor

performer characteristics
- range of tasks to be solved
- Wednesday
- operating mode
- command system
formal execution of the algorithm

3.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 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, the sequential implementation of which can lead to the desired result.

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

think of two numbers;
add two numbers in mind;
divide the resulting amount by 2.

Example 2. The task “Deposit money into your phone account” is divided into the following steps:

go to the payment terminal;
select a telecom operator;
enter a phone number;
check the entered number is correct;
insert a banknote into the bill acceptor;
wait for a message about money being credited to your account;
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. 3.1):

Rice. 3.1.
General scheme of the algorithm

Algorithms are the rules of addition, subtraction, multiplication and division of numbers, grammatical rules, rules of geometric constructions, etc., studied in school.

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

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

The length (in characters) of the source string of characters is calculated.
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.
The symbols are swapped in pairs (the first with the second, the third with the fourth, the fifth with the sixth, etc.).
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.

3.1.2. Algorithm executor

Each algorithm is designed for a specific performer.

There are 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 automatically. 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's command system consists of two commands:

Right m (where m is an integer) - causes the Turtle's movement direction to change by m 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 4 5 Forward 20 Right 45]

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

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:

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:

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:

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;
the initial data and the required result are determined;
the sequence of actions of the performer is determined, ensuring the transition from the initial data to the result;
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 the algorithm executor.

3.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.

The property of discreteness 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.

The property of understandability 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.

The 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 at the next step.

The efficiency property means that the algorithm must be able to obtain 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.

The property of mass production 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 n. This method is called the “sieve of Eratosthenes”, named after the ancient Greek scientist Eratosthenes 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:

write down all the integers from 2 to n in a row (2, 3, 4, ..., n);
frame 2 - the first prime number;
cross out from the list all numbers divisible by the last prime number found;
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;
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 “The Sieve of Eratosthenes” (http://school-collection.edu.ru/).

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 a 9th 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 n.

The considered properties of the algorithm allow us to give a more precise definition of the algorithm.

3.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 a problem using a ready-made algorithm only requires the performer 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.

If the number of objects in the pile is a multiple of 3, then give way to the opponent, otherwise start the game.
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:

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

The most important

An executor is an 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 performer, you can specify: the range of tasks to be solved, the environment, the command system and the operating mode.

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.

The ability of the performer to act formally provides the possibility of automating human activity.

Questions and tasks

What is an algorithm called?
Find synonyms for the word “prescription”.
Give examples of algorithms you studied in school.
Who can be the executor of the algorithm?
Give an example of a formal performer. Give an example when a person acts as a formal performer.
What commands should a robot perform the functions of: a) a cashier in a store; b) a janitor; c) a security guard?
What determines the range of tasks performed by the “computer” performer?
Consider the word processor on your computer as the executor. Describe the range of tasks solved by this performer and his environment.
What is a team, a system of performer commands?
List the main properties of the algorithm.
What can the absence of any property in an algorithm lead to? Give examples.
Why is it important to be able to formally execute an algorithm?
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.
Some 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 last place in the original chain is the letter Z, 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 DOM, 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 symbols that will be obtained if you apply the algorithm to this chain, and then apply the algorithm again to the result of its work?
Find an animation of the steps of Eratosthenes' algorithm on the Internet. Use Eratosthenes' algorithm to find all prime numbers not exceeding 50.
What will be the result of Turtle’s execution (see example 5) of the algorithm?
Write down an algorithm for the Calculator executor (example 6), containing no more than 5 commands:
The system of executor commands The constructor consists of two commands, which are assigned numbers:
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).
In which cell should the Robot performer (example 7) be located in order to return to it after executing algorithm 3241?

The concept of an algorithm. Algorithm executors.

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 an algorithm, since this concept is quite broad and is used in various fields of science, technology and everyday life.

An algorithm is a precise description of a sequence of actions intended for a specific performer aimed at solving a given problem.

Performer The 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 performer is not required to understand the essence of the problem being solved, but is required to accurately execute a sequence of commands. 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 in .

programming language

To create an algorithm (program), you need to know:

a complete set of initial task data (initial state of the object);

the purpose of creating the algorithm (the final state of the object);

the system of commands of the performer (that is, a set of commands that the performer understands and can execute).

The resulting algorithm (program) must have the following set of properties: discreteness

(the algorithm is divided into separate steps - commands); unambiguity

(each command determines the only possible action of the performer); clarity

(all algorithm commands are included in the system of executor commands); effectiveness

(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 similar problems).

Ways to describe algorithms It was noted above that the same algorithm can be written in different ways. You can write down the algorithm natural language. This is how we use recipes, instructions, etc. To record algorithms intended for formal performers, special programming languages . Any algorithm can be described

graphically in the form of a block diagram	.	A special notation system has been developed for this purpose:
	Designation
	Description	Notes
	Start and end of the algorithm	Data input and output.
	Data output is sometimes referred to differently:	Action
	In computing algorithms this is used to denote assignment
	Fork	Fork - a component necessary to implement branches and loops
	Starting a loop with a parameter

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 visual and understandable to humans. Therefore, algorithms of formal executors are usually developed first in the form of a flowchart, and only then create a program on one ofprogramming languages .

Typical algorithmic structures

The programmer has the opportunity to design and use atypical algorithmic structures, however, this is not necessary. Any algorithm, no matter how complex, can be developed based on three typical structures: following, branching and repetition. In this case, the structures can be located sequentially one after another or nested within 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 recorded.

Branching

IN full branching There are two options for the performer'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. This structure is called incomplete branching or bypass.

From several branches you can construct a structure “ choice”(multiple branching), which will choose not from two, but from a larger number of options for the performer’s actions, depending on several conditions. It is important 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 one from the top.

Cycle (repetition)

Cycleallows you to organize multiple repetitions of the same sequence of commands- it is called the body of the cycle. In various types of cyclic algorithms, the number of repetitions can depend on the value of a logical expression (condition) or can be hard-coded in the structure itself. There are cycles: “ before», « Bye», loops with a counter. In “before” and “while” loops, a logical expression (condition) can precede the body of the loop ( loop with precondition) or end the loop ( loop with postcondition).

Cycles« before» - repetition of the loop body until the condition is met:

Cycles « Bye» - repetition of the loop body as long as the condition is met(true):

Loops with a counter(with parameter)– repeating the body of the loop a specified number of times:

Auxiliary algorithm (subroutine, procedure)

Auxiliary algorithm is a module that can be accessed repeatedly 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 task detailing(“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. Solutions to individual subproblems are then combined into a single algorithm for solving the original problem. The method is widely used because it allows several programmers to simultaneously develop a general algorithm and solve local subproblems. This is a necessary condition for rapid software development. Assembly method(“bottom-up”) consists in creating a variety of software modules that implement the solution of typical problems. 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 significantly simplifies and speeds up the creation of a complex algorithm. - Algorithms and control processes

Control

purposeful interaction of objects, some of which are managers, others - managed. In the simplest case, there are two such objects: From a computer science point of view control actions can be considered as control information. Information can 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:.

Management processes are studied in more detail and discussed cybernetics.

This science claims that the most diverse management processes in society, nature and technology occur in a similar way and are subject to the same principles.

To the beginning of the topic

>> 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<действия 1>THAT<действия 2>

OTHERWISE

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.<действия 2>In some cases

The decision logic can be described as follows:<условие>IF<действия 1>

may be absent;:

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?

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 folk tales’ heroes make choices that determine their fate.
9. Out of 9 coins of the same denomination, one is counterfeit (lighter). 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 training programs methodological recommendations

Please suspend AdBlock on this site.

In this lesson we will look at 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 begin with, I suggest you play a little with the following children's toy. Complete 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 several basic concepts:

executor;
performer command system;
algorithm.

In the toy we control a red bird. The goal 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 carry out some commands is called an executor. In this toy, obviously, the performer is a bird. The set of commands that the performer understands and can execute is called system of executor commands.

The sequence of commands that a performer must execute to solve a problem is called an algorithm.

It is necessary to focus on several points.

The executor can execute only those commands that are included in his command system.

This means, for example, that you cannot write to the bird performer: “Go to the pig!” You can write it down more precisely, but nothing will happen, because... the performer of such commands does not know.

You can write down the available commands in any order that you consider correct. Your task as a programmer is to divide a large complex task into small individual steps, each of which will be understandable to the performer. The principle of “divide and conquer” is at work again.

The performer does exactly what the algorithm tells him to do.

The bird performer is very trusting. She doesn't question what you write in the program. If, for example, you forget to turn the bird, it will crash into the wall. Therefore, you must monitor everything yourself.

Your future programs will often not work as you intended. Mistakes happen to everyone. Here it is important to understand that it is not the computer that is stupid, but you made a mistake in the algorithm. Don't be like bad programmers, for whom the program is always to blame for everything.

Now, from the illustrative example, let’s move on to computer realities. We write programs for the computer, which means that the computer in our case is the performer. The command system is standard functions and constructs of the C language.

What is the main goal of your teaching the basics of programming? Master the skill of algorithmic thinking. That is, learn to write down the solution to various problems in the form of an algorithm for a specific performer (in our case, a computer).

So, to summarize:

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 a performer 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.

TOPIC 8. BASICS OF ALGORITHMIZATION AND PROGRAMMING

8.1. The concept of an algorithm and an algorithm executor. Properties of algorithms

"Algorithm" is a fundamental concept in computer science. An understanding of it is necessary for the effective use of computer technology to solve practical problems. An algorithm is an instruction to a performer (human or automatic) to perform a precisely defined sequence of actions aimed at achieving a given goal. An algorithm is a rule formulated in a certain language, indicating actions, the sequential execution of which leads from the initial data to the desired result. Meaning of the word algorithm very similar to the meaning of the words recipe, process, method, method. However, any algorithm, unlike a recipe or method, necessarily has the following properties.
Properties of the algorithm (distinguishing it from any other prescriptions): (each command determines the only possible action of the performer);(for a specific performer); The resulting algorithm (program) must have the following set of properties:(commands are sequential, with precise recording of the moments of the beginning and end of command execution); accuracy(after each command is executed, it is known exactly whether the execution of the algorithm is completed or which command should be executed next); (all algorithm commands are included in the system of executor commands);(after a finite number of steps the problem is solved or it becomes clear that the solution process cannot be continued): mass character(the algorithm applies uniformly to any specific problem formulation for which it is designed).
1. Discreteness - dividing the algorithm into a number of separate completed actions - steps. The execution of the algorithm is divided into a sequence of completed actions - steps. Each action must be completed by the algorithm executor before he begins the next action.
2. Accuracy - clear instructions. At each step, the transformation of objects in the executor’s environment obtained in the previous steps of the algorithm is uniquely determined. If an algorithm is applied repeatedly to the same set of input data, it produces the same result each time. The algorithm must be written in such a way that at each step of its execution it is known which command should be executed next.
3. Understandability - unambiguous understanding and execution of each step of the algorithm by its performer. The algorithm must be written in a language understandable to the performer.
4. Effectiveness - obligatory achievement of a result in a finite number of steps. Each step (and the algorithm as a whole), upon completion, produces an environment in which all objects are uniquely defined. If for some reason this is impossible, then the algorithm must report that a solution to the problem does not exist. The algorithm must be completed in a finite number of steps. Computer science operates only with finite objects and finite processes, so the question of considering infinite algorithms remains outside the scope of the theory of algorithms. 5. Massiveness - application of the algorithm to solve a whole class of similar problems.
The system of commands of the performer is a precisely described situation, including the formulation of the problem to be solved, a list of objects involved in the condition of the task and in its solution, and the capabilities of the performer: the properties of objects that he can recognize and the actions that he can perform. The formal execution of the algorithm is performed by a compiler or interpreter, checking the semantics.

8.2. Ways to write an algorithm

In practice, the most common forms of writing algorithms are:
1) graphical recording (block diagrams);
2) verbal recording (pseudocodes);
3) programming language.
The verbal form of writing an algorithm is a description in natural language of the successive stages of data processing. The verbal method is not widespread, since such descriptions are not strictly formalized and allow for ambiguity in the interpretation of individual instructions. An algorithm written using pseudocode is a semi-formalized description in a conditional algorithmic language, including both the basic elements of a programming language and natural language phrases, generally accepted mathematical notations, and others.
A graphical form of recording, also called an algorithm diagram, is an image of an algorithm in the form of a sequence of interconnected functional blocks, each of which corresponds to the execution of one or more actions. Graphic recording is more compact and visual compared to verbal recording. In the algorithm diagram, each type of action corresponds to a geometric figure. The figures are connected by transition lines that determine the order of actions.
A graphical form of recording, also called a block diagram or flowchart of an algorithm, is an image of an algorithm in the form of a sequence of interconnected functional blocks, each of which corresponds to the execution of one or more actions.
In what follows we will use algorithm flowcharts V. They allow you to present algorithms in a more visual form, this makes it possible to analyze their work, look for errors in their implementation, etc. In flowcharts there is always Start And end, denoted by ellipses, between them is a sequence steps algorithm connected arrows.

There are steps unconditional(represented by rectangles, parallelograms) and conditional(depicted as diamonds). Two arrows always come out of the diamond - one means the further path if the condition is met (usually indicated by the word “yes” or “+”), the other means non-fulfillment (by the word “no” or “-”). Entering from the keyboard or displaying the value of an expression is represented by a parallelogram. The command that performs the action processing (assignment command) is depicted in a rectangle.

If the solution to the problem is complex and long enough, then the algorithm can turn out to be very large. This can be avoided by replacing a certain complete sequence of algorithm steps with blocks that will be auxiliary algorithms. A block is usually not elementary; its dimensions are chosen depending on the need, but if it is correctly composed, it has all the necessary characteristics of an algorithmic step: it has an entry point (a clearly defined beginning) and can be conditional or unconditional. Different blocks of the algorithm are connected to each other only through entry and exit points, so if a block correctly solves its problem, then its internal structure is unimportant for the rest of the algorithm. This block representation is especially convenient at the first stages of solving complex problems, when the blocks are detailed later and, possibly, by other developers.
A programming language is a language used to formally write algorithms. Most programming languages are algorithmic languages. Recording an algorithm in an algorithmic language is called a program.
The language used to formally write algorithms is called algorithmic language. When describing any language (including natural language, for example, Russian, English, etc.), the following concepts are used: alphabet, syntax And semantics.
Alphabet language is a set of simple signs that can be used in the texts of this language. A sequence of alphabet characters is called in a word. The rules according to which words are formed from the alphabet are called grammar. Himself language is the set of all words written in a given alphabet according to a given grammar.
Syntax- this is a set of rules that determine possible combinations (constructions) of letters of the alphabet. To describe the syntax of a language, as a rule, another language (metalanguage) or syntactic diagrams are used.
Semantics- this is a set of rules that determine the meaning (meaning) of individual language constructs.
One of the most common algorithmic languages is Pascal, which is useful for both beginners and experienced programmers. Programming training is most often based on this language.

8.3. Basic algorithmic constructions

The structure of the algorithm can be most clearly represented using a block diagram, which uses geometric shapes (blocks) connected to each other by arrows indicating the sequence of actions. Certain standards for graphic representations of blocks have been adopted. For example, an information processing command is placed in a block shaped like a rectangle, condition checking is placed in a rhombus, input or output commands are placed in a parallelogram, and an oval indicates the beginning and end of the algorithm.
The structural elementary unit of the algorithm is a simple command, denoting one elementary step of processing or displaying information. A simple command in circuit language is represented as a function block.

	This block has one entrance And one exit. From simple commands and checking conditions, compound commands are formed that have a more complex structure and also one entrance and one exit. The structural approach to the development of algorithms determines the use of only basic algorithmic structures (constructions): following, branching, repetition, which must be designed in a standard way.
	Let's look at the basic structure of the algorithm. Team following consists only of simple commands. In the figure, simple commands are symbolized S1 And S2. Linear algorithms are formed from following commands. An example of a linear algorithm would be finding the sum of two numbers entered from the keyboard.
	Team branching- this is a compound command of the algorithm, in which, depending on condition P, either one is executed S1, or other S2 action. Branching algorithms (branching algorithms) are composed of follow commands and branch commands. An example of a branching algorithm would be to find the larger of two numbers entered from the keyboard.
	A branch command can be in full or incomplete form. The incomplete form of a branch command is used when an action needs to be performed S only if the condition is met P. If the condition P is not followed, the branch command terminates without executing the action. An example of an incomplete form branch command would be to halve only an even number.
	Team repetitions is a compound command of the algorithm, in which, depending on the condition R it is possible to perform the action multiple times S. Cyclic algorithms (repetition algorithms) are composed of follow commands and repeat commands. The figure shows a repeat command with a precondition. It is called that because the condition is checked first, and only then the action is performed. Moreover, the action is performed as long as the condition is met. An example of a cyclic algorithm could be the following. While positive numbers are entered from the keyboard, the algorithm finds their sum. The repeat command with precondition is not the only possible one. A variation of the repeat command with a precondition is the repeat command with a parameter. It is used when the number of repetitions of an action is known. In the block diagram of the repeat command with a parameter, the condition is written not in a diamond, but in a hexagon. An example of a cyclic algorithm with a parameter would be finding the sum of the first 20 natural numbers.
	In a repeat command with a postcondition, the action is performed first S and only then the condition is checked P. Moreover, the action is repeated until the condition is met. An example of a repeat command with a postcondition would be to decrease a positive number until it is non-negative. As soon as the number becomes negative, the repeat command ends its work. By connecting only these elementary structures (sequentially or by nesting), you can “assemble” an algorithm of any degree of complexity.

Each specified construction can be implemented without changes in structure in any programming language, for example, in Pascal and BASIC. Therefore, it is necessary to correctly compose an algorithm using a flowchart, and only then, knowing how commands are written in a specific programming language, type the program on a computer and get the result by running it for execution.

8.4. Linear algorithm

Let's give an example of writing the algorithm in the form of a block diagram, pseudocodes and in Pascal. Manual testing and selection of a test system are performed similarly to the previous task.

8.5. Branching algorithm

Let's give an example of writing a branching algorithm for finding the largest of two numbers.

8.6. Round robin algorithm

Let's consider an algorithm for finding the sum of the first natural odd numbers up to n. Let's present the algorithm in three ways: in the form of a flowchart, a school algorithmic language, and in the Pascal programming language.

The block diagram consists of the following basic structures: two compound commands (follow command and repeat command with precondition), then a simple command. All commands are connected in series. The constructs are formatted in a standard way, so they are easy to recognize and translate into a programming language. Each structure has one entrance and one exit.
The dotted arrows in the table reflect the sequence of execution of the technological chain. After recording the algorithm in the form of a flowchart, each command is translated into a school algorithmic language, and only then into a programming language.
Let's write down an algorithm for calculating the sum of the first n natural numbers. To do this, we will use a loop with a parameter, since we know in advance how many times the command to find the sum will be executed. In all links of the chain, we will change the “while” loop to the “for” loop and give an example of translating the algorithm from the flowchart language into the school algorithmic language and into the Pascal programming language.

Let's consider finding the number of natural numbers whose sum is not greater than a given one. To do this, we will use the repeat command with a postcondition.

Questions for self-control

The concept of an algorithm. Properties of the algorithm. Algorithm example. The concept of "variable".
Assignment operator. Examples.
Programming styles (logical, functional).
The concept of subroutine, module and object
What is a variable? Rules for naming variables in Pascal. Examples.
Assignment operator. Writing expressions in Pascal. Examples. Explain how the operator x:=x+1;
Input and output operators in Pascal. Examples. Formatted output.
Conditional operator ( if). Example. Compare with operator case.
Selection operator. Example. Compare with operator if.
Logical expressions. Operations or, and And not. Examples. Truth table.
Numeric types of variables in the Pascal language. Type conversion rules. Examples.
Boolean data type. Example of use in the program. Character data type. Example. Functions chr And ord, succ And pred.
Arrays. Definition. Array indexes. Array declarations. Accessing array elements. One-dimensional and two-dimensional arrays. Examples. Similarities and differences between arrays and strings.
Procedures. Definition. Why are procedures needed? Examples. Rules for describing procedures. Compare procedures and functions.