When studying computer science, a lot of attention is paid to the study of algorithms and their types. Without knowing the basic information about them, you cannot write a program or analyze its work. The study of algorithms begins in the school computer science course. Today we will consider the concept of an algorithm, properties of the algorithm, types.
Concept
An algorithm is a certain sequence of actions that leads to the achievement of a particular result. When composing an algorithm, each action of the performer is prescribed in detail, which in the future will lead him to the solution of the task.
Quite often, algorithms are used in mathematics to solve certain problems. So, many people know the algorithm for solving quadratic equations with the search for the discriminant.
Properties
Before being considered in computer science, it is necessary to find out their basic properties.
Among the main properties of algorithms, it is necessary to highlight the following:
- Determinism, that is, certainty. It lies in the fact that any algorithm presupposes obtaining a certain result given the initial ones.
- Effectiveness. Means that in the presence of a number of initial data, after completing a series of steps, a certain, expected result will be achieved.
- Mass character. An algorithm written once can be used to solve all problems of a given type.
- Discreteness. It implies that any algorithm can be broken down into several stages, each of which has its own purpose.
Recording methods
Regardless of what types of algorithms in computer science you are considering, there are several ways to write them.
- Verbal.
- Formula-verbal.
- Graphic.
- Algorithm language.
Most often, the algorithm is depicted in the form of a block diagram, using special designations fixed by GOSTs.
Main types
There are three main schemes:
- Linear algorithm.
- Branching algorithm, or branched.
- Cyclical.
Linear
The simplest in computer science is considered It involves a sequence of actions. Let us give the simplest example of an algorithm of this kind. Let's call it “Gathering for School”.
1. Get up when the alarm rings.
2. We wash.
3. We brush our teeth.
4. Doing exercises.
5. Getting dressed.
6. We eat.
7. We put on our shoes and go to school.
8. End of the algorithm.
Forking algorithm
Considering the types of algorithms in computer science, one cannot but recall the branching structure. This type assumes the presence of a condition under which, in the case of its execution, the actions are performed in one order, and in the case of non-fulfillment, in another.
For example, let's take the following situation - a pedestrian crossing a road.
1. We approach the traffic light.
2. We look at the traffic signal.
3. It must be green (this is a condition).
4. If the condition is met, we cross the road.
4.1 If not, wait until green lights up.
4.2 We cross the road.
5. End of the algorithm.
Cyclic algorithm
Studying the types of algorithms in computer science, one should dwell in detail on this algorithm assumes a section of calculations or actions that is performed until a certain condition is met.
Let's take a simple example. If the range of numbers is from 1 to 100. We need to find everything that is, those that are divisible by one and themselves. Let's call the algorithm "Prime numbers".
1. Take the number 1.
2. Check if it is less than 100.
3. If yes, check if this number is prime.
4. If the condition is met, write it down.
5. Take the number 2.
6. Check if it is less than 100.
7. Check if it is simple.
…. We take the number 8.
Check if it is less than 100.
Check if the number is prime.
No, let's skip it.
We take the number 9.
Thus, we iterate over all the numbers, up to 100.
As you can see, steps 1 - 4 will be repeated a number of times.
Algorithms with a precondition, when the condition is checked at the beginning of the loop, or with a postcondition, when the check is at the end of the loop, are distinguished among the cyclic ones.
Other options
The algorithm can be mixed. So, it can be cyclic and branched at the same time. In this case, different conditions are used on different segments of the algorithm. Such complex structures come in handy when writing complex programs and games.
Legend in the block diagram
We have considered what types of algorithms are in computer science. But we did not talk about what designations are used for their graphical recording.
- The beginning and end of the algorithm are written in an oval frame.
- Each team is captured in a rectangle.
- The condition is written in a diamond.
- All parts of the algorithm are connected using arrows.
conclusions
We have considered the topic "Algorithms, types, properties". Computer science spends a lot of time studying algorithms. They are used when writing various programs both for solving mathematical problems and for creating games and various kinds of applications.
Annotation: Algorithm is a basic concept for anyone who wants to start programming in any programming language. Any task can be formalized algorithmically. To understand where to start, let's look at the main types of algorithms. The purpose of this lecture is to familiarize students with the concept of an algorithm; show that such an abstract thing as an algorithm surrounds us in everyday life.
Example pseudocode:
alg Finding quotient of two numbers start output ("set dividend and divisor") input (dividend, divisor) if divisor ≠ 0 then quotient = dividend / divisor output (quotient) otherwise output ("no solution") con alg Finding quotient of two numbers
This example uses three variables: dividend, divisor, and quotient. The dividend and the divisor are set by the executor with arbitrary numbers. The quotient is considered only if the divisor is not zero.
The graphical implementation of the algorithm is a block diagram. The block diagram consists of blocks of a certain shape, connected by arrows. The answer is received by the person who executes the commands according to the flowchart. More details about block diagrams will be discussed in Lecture 2.
A software implementation of an algorithm is a computer program written in any algorithmic programming language, for example: C ++, Pascal, Basic, etc. A program consists of commands from a specific programming language. Note that the same block diagram can be implemented in different programming languages. The answer is received by a computer, not a person. For more information about writing programs in the C ++ programming language, see Lecture 3.
There are three main types of algorithms:
- linear algorithm,
- forking algorithm,
- cyclical algorithm.
Linear Algorithm Is an algorithm in which actions are performed once and strictly sequentially.
The simplest example of a linear algorithm implementation is the way home from university.
Verbal way of writing this algorithm:
- leave the university for a bus stop;
- wait for the desired bus;
- take the desired bus;
- pay for travel;
- get off at the required stop;
- walk home.
Obviously, this example refers to a linear algorithm, since all actions follow one after another, without conditions and repetitions.
Forking algorithm Is an algorithm in which, depending on the condition, either one or another sequence of actions is performed.
The simplest example of a branching algorithm implementation is that if it is raining outside, you must take an umbrella, otherwise you should not take the umbrella with you.
The above pseudocode example for finding the quotient of two numbers also applies to the branching algorithm.
Cyclic algorithm Is an algorithm whose commands are repeated a certain number of times in a row.
The simplest example of implementing a cyclic algorithm - while reading a book, the same actions will be repeated: read a page, turn over, etc.
For more information on linear, branching and cyclic algorithms see Lecture 2.
CONCEPT OF THE ALGORITHM. PROPERTIES OF THE ALGORITHM. TYPES OF ALGORITHMS. METHODS FOR DESCRIPTION OF ALGORITHMS
An algorithm is an exact and understandable instruction to the performer to perform a sequence of actions aimed at solving the problem. The word "algorithm" comes from the name of the mathematician Al Khorezmi, who formulated the rules for performing arithmetic operations. Initially, an algorithm was understood only as the rules for performing four arithmetic operations on numbers. In the future, this concept began to be used in general to denote a sequence of actions leading to the solution of any task. Speaking about the algorithm of the computational process, it is necessary to understand that the objects to which the algorithm was applied are data. The algorithm for solving a computational problem is a set of rules for transforming the initial data into the result ones.
The main properties algorithm are:
- determinism (certainty). Assumes obtaining an unambiguous result of the computational process with the given initial data. Due to this property, the process of executing the algorithm is mechanical in nature;
- effectiveness. Indicates the presence of such initial data for which the computational process implemented according to a given algorithm must stop after a finite number of steps and return the desired result;
- mass character. This property assumes that the algorithm should be suitable for solving all problems of this type;
- discreteness. It means the dismemberment of the computational process determined by the algorithm into separate stages, the possibility of which the executor (computer) can perform is beyond doubt.
The algorithm must be formalized according to certain rules by means of specific visual means. These include the following methods of writing algorithms: verbal, formula-verbal, graphical, operator scheme language, algorithmic language.
Due to its clarity, the most widespread is the graphical (block-diagram) method of writing algorithms.
Block diagram a graphic image of the logical structure of an algorithm is called, in which each stage of the information processing process is represented in the form of geometric symbols (blocks) having a certain configuration depending on the nature of the operations performed. The list of symbols, their name, functions displayed by them, shape and size are determined by GOSTs.
With all the variety of algorithms for solving problems, three main types of computational processes can be distinguished in them:
- linear;
- branching;
- cyclical.
Linear is called a computational process in which all stages of solving a problem are performed in the natural order of the recording of these stages.
Branching such a computational process is called in which the choice of the direction of information processing depends on the initial or intermediate data (on the results of checking the fulfillment of some logical condition).
A cycle is a repeatedly repeated section of calculations. A computational process containing one or more cycles is called cyclical ... According to the number of executions, the cycles are divided into cycles with a certain (predetermined) number of repetitions and cycles with an indefinite number of repetitions. The number of repetitions of the latter depends on the observance of a certain condition that specifies the need for a cycle. In this case, the condition can be checked at the beginning of the cycle - then we are talking about a cycle with a precondition, or at the end - then this is a cycle with a postcondition.
Target : To acquaint students with the basics of algorithmization.
Study questions:
1. Algorithm and its properties. Methods for writing algorithms.
2. The main types of algorithms. Block diagrams of typical algorithms.
Having studied this topic, the student must:
Know:
· Properties of the algorithm;
· Blocks for building circuits;
· Basic types of algorithms;
Be able to :
· Build algorithms according to the condition of the problem;
Algorithm concept
The concept of an algorithm is one of the fundamental concepts of computer science, which historically took shape in an independent discipline "theory of algorithms", close to another discipline "mathematical logic". On the other hand, the discipline "theory of algorithms" can be considered intermediate between two disciplines: mathematics and computer science, related to the programming section.
Algorithmization refers to the general methods of informatics, is of great importance in solving complex problems. Before writing a program for solving a problem on a computer, it is necessary to review the sequence of actions that must be performed to correctly solve the problem under consideration.
An algorithm is a sequence of arithmetic, logical and other operations required to be performed on a computer.
To obtain the correct result, the algorithm must be designed so that when it is executed, all commands are interpreted unambiguously. Therefore, there are mandatory requirements that must be taken into account when compiling algorithms. Requirements are formulated as properties.
The algorithm must always be effective, have the property of repeatability and must be designed for a specific performer. In technology, such a performer is a computer. To ensure the possibility of implementation on a computer, the algorithm must be described in the language of a computer that is understandable, that is, in a machine language. However, before presenting an algorithm in a computer-understandable language (machine language), it is necessary to write a program using an algorithmic programming language.
The algorithm can be represented in various ways, in particular:
1) verbally (verbal description);
2) tabularly;
3) in the form of a block diagram;
4) in algorithmic language.
A fairly common way to represent an algorithm is to write it in an algorithmic language, which, in the general case, is a system of notation and rules for a uniform and accurate writing of algorithms and their execution. This way of representing the algorithm involves writing it in the form of a program.
Program Is a record of an algorithm in a programming language that leads to the final result in a finite number of steps.
It is preferable to present the algorithm in the form of a block diagram before writing in an algorithmic language. To build an algorithm in the form of a block diagram, you need to know the purpose of each of the blocks. Table 13. lists the types of blocks and their purpose.
Table 13
Block purpose | A comment (the block corresponds to the operator) |
||
Beginning or end block diagrams | |||
Data input or output | input / output |
||
Process (in particular computing) | assignments |
||
| |||
| Cycle modifier |
5.2. Basic types of algorithms
Algorithmization acts as a set of certain practical techniques, special specific skills of rational thinking within the framework of given linguistic means. Algorithmization of computations involves solving a problem in the form of a sequence of actions, that is, a solution presented in the form of a flowchart. Typical algorithms can be distinguished. These include: linear algorithms, branching algorithms, cyclic algorithms.
Linear Algorithms
The linear algorithm is the simplest. It assumes sequential execution of operations. There are no conditional or repetition checks in this algorithm.
Example : Calculate function z = (x-y) / x + y2.
Draw up a flowchart for calculating a function using a linear algorithm. Variable values X, at there can be any, except zero, to enter them from the keyboard.
Solution: The linear algorithm for calculating the function is given in the form of a block diagram in Fig. 8. When executing a linear algorithm, the values of variables are entered from the keyboard, substituted into a given function, the result is calculated, and then the result is displayed.
Fig. 8. Linear Algorithm
The purpose of the blocks in the diagram in Fig. 8:
· Block 1 in the diagram serves as a logical beginning.
· Block 3 represents the arithmetic operation.
· Block 4 outputs the result.
· Block 5 in the circuit serves as the logical termination of the circuit.
Branching algorithms
The branching algorithm involves checking the conditions for choosing a solution. Accordingly, the algorithm will have two branches for each condition.
In the example, a branching algorithm is considered, where, depending on the condition, one of the possible solutions is selected. The algorithm is presented in the form of a block diagram.
Example : When the condition is met x>0 the function is calculated: z= ln x+ y, otherwise, namely, when x = 0 or x<0 , the function is calculated: z= x+ y2 .
Draw up a flowchart for calculating a function using the branching algorithm. Variable values X, at can be any, enter them from the keyboard.
Solution : Figure 9 shows a branching algorithm, where, depending on the condition, one of the branches is executed. A new block 3 has appeared in the flowchart, which checks the condition of the problem. The rest of the blocks are familiar from the linear algorithm.
https://pandia.ru/text/78/136/images/image008_57.gif "width =" 300 "height =" 360 src = ">
Fig. 9. Branching Algorithm
Example : Find the maximum value of three different integers entered from the keyboard. Draw up a flowchart for solving the problem.
Solution : This algorithm assumes checking the condition. For this, any of the three variables is selected and compared with the other two. If it is greater, then the search for the maximum number is over. If the condition is not met, then the two remaining variables are compared. One of them will be maximum. The block diagram for this task is shown in Fig. 10.
https://pandia.ru/text/78/136/images/image010_48.gif "width =" 492 "height =" 456 src = ">
Rice. 10. Block diagram of the search for the maximum
Cyclic algorithms
The cyclic algorithm provides for the repetition of one operation or several operations, depending on the condition of the problem.
Cyclic algorithms are of two types:
1) with a given number of cycles or with a cycle counter;
2) the number of cycles is unknown.
Example : In a loop, calculate the value of the function z = x * y provided that one of the variables x changes in each cycle by one, and the other variable at does not change and can be any integer. As a result of the loop execution at the initial value of the variable x = 1 you can get the multiplication table. The number of cycles can be any. Draw up a flowchart for solving the problem.
Solution : In the example, the number of cycles is set. Accordingly, the first type of loop algorithm is selected. The algorithm for this problem is shown in Fig. eleven.
In the second block, the number of cycles is entered n and any integers X, y .
A new block 3 has appeared in the block diagram, in which the variable i counts the number of cycles, increasing by one after each cycle until the counter is equal to i = n ... At i = n the last cycle will be executed.
The third block indicates the range of change of the cycle counter (from i = 1 before i = n).
In the fourth block, the values of the variables are changed: z, x.
The fifth block displays the result. The fourth and fifth blocks are repeated in every cycle.
Fig. 11. Cyclic algorithm with cycle counter
This type of looping algorithms is preferred when given by the number of loops.
If the number of cycles is unknown, then the block diagrams of cyclic algorithms can be presented in the form of Figures 12, 13.
Example : Calculate y = y-x bye y> x, if y=30 , x=4. Count the number of cycles executed, the final value of a variable at ... In a loop, output the value of a variable at, the number of cycles performed. Draw up a flowchart for solving the problem.
Solution : In the example, the number of cycles is unknown. Accordingly, the second type of loop algorithm is selected. The algorithm for this problem is shown in Fig. 12.
The condition is checked at the entrance to the loop. Two blocks are executed in the body of the loop:
1) y = y-x;i= i+1 ;
2) output of values of variables i, y.
The cycle is executed as long as the condition is met y> x... Provided that these variables are equal y = x or y
The algorithm shown in Figure 12 is called cyclic precondition algorithm, since the condition is checked at the beginning of the loop or at the entrance to the loop. > x at the entrance to the loop. If the condition is met, then go to block 4, otherwise to block 6.
The fourth block calculates the value of the variable at i= i+1 .
The fifth block displays the result:
Variable value at,
i.
Example : Draw up an example flowchart (Figure 12), checking the loop exit condition. In this example, the task condition does not change, and the output is the same, but the flowchart will be different.
Solution : In this case, the condition for exiting the loop is checked: y<=x ... Under this condition, the loop is not executed. The condition in the block diagram should be transferred to the end of the cycle, after being printed. The cycle is executed as long as the condition is met y> x.
The algorithm, if the condition is transferred to the end of the cycle, is called loop algorithm with postcondition... The algorithm for this problem is shown in Fig. thirteen.
The second block introduces y=30 , x=4 .
The third block calculates the value of the variable at , the number of completed cycles is counted i= i+1 .
The fourth block displays the result:
Variable value at,
Number of cycles performed i.
The fifth block checks the condition y <= x to exit the loop. If the condition is met, then go to block 6, otherwise, to block 3 and the cycle repeats.
Fig. 13. Loop Algorithm with Postcondition
Control questions
1. The concept of an algorithm.
2. Types of algorithms.
3. Basic algorithmic structures.
4. The main blocks of the graphic algorithm.
5. Linear algorithmic structure. Example.
6. Branching. Example.
7. Cyclic algorithmic structures. Example.
Timing:2 5 .09.201 4 G.Class:9 D Teacher:Mamedov A.
Lesson topic: « TYPES ALGORITHMS.»
Lesson type: mixed.
Lesson objectives:to give the concept of teams, structures of algorithms and teach the stages of solving problems in Pascal.
STRUCTURE OF ALGORITHMS
Linear algorithms. They consist of sequential simple commands, block diagrams - from blocks located on one line. Linear algorithm is called an algorithm in which all actions (operations) are performed once and sequentially one after another. Now let's give some examples: alg write homework start
take the diary open the page you want to do your homework put the diary back in place
Linear algorithm commands consist of commands (blocks) that are executed in the specified sequence. Such execution of operations one after another will be called the natural order.
Forking algorithms. In everyday life, algo rhythms are mainly divided into groups, in which, depending on the fulfillment or non-fulfillment of a certain condition, the sequence of commands is divided into several branches.
V the branching algorithm mainly tests a logical condition given as an arithmetic inequality.
Checking conditions is called the branching command. When writing it, the algorithm uses keywords if, then, otherwise, everything. According to the branching method, the branching command is divided into two types: the selection command (complete) and the branch command (incomplete). The complete forking command is as follows:
if condition
then 1-th series otherwise 2nd series
To execute the algorithms in the branching command, conditions are first checked. If the conditions are met, then the commands are executed 1 -th series enclosed between keywords if and otherwise. If the conditions are not met, then the commands of the 2nd series are executed, enclosed between the keywords otherwise and all. The scheme of this kind of branching algorithm necessarily includes a block for checking the condition. It is depicted as a diamond and communicates with other blocks using one entry line and two exit lines.
In full branching algorithm selects only one series out of two . If the statement is true then 1 -th series, then the transition to the next operations is carried out. If the statement is false, then the 2nd series is executed, only then the following actions of the algorithm are performed. So, depending on the truth or falsity of the statement, 1 -th or 2nd series.
If the algorithm consists of an incomplete form of the branching command, then if the condition is fulfilled, the "series" is executed and then the execution of the algorithm continues. If the condition is not met, then none of the command from the "series" is executed, the transition action is performed
Complex branches. Quite often, the tasks check the conditions corresponding to three or more outputs. For example, if the conditions X 0, x = 0, X requires three different actions, then the branching structure can be as shown in Fig.
Cyclic algorithms... In many algorithms, a certain sequence of actions is repeated several times. The computation process, when a certain part of the algorithm is repeated many times, is called cyclicalaboutcessom. An algorithm with a repeating part is called cyclical
questions to consolidate:
What are the similarities and differences between the program and the algorithm?
List the properties of the algorithms that run on the computer.
What ways of describing algorithms do you know?
What can be the stages of solving problems on a computer?
List the types of blocks in the algorithm diagram, their images and connections.
What do you know about linear, branching, and looping algorithms?
What are the iteration loops and their features?
