Algorithm
The solution to any complex problem is carried out in several stages. All stages performed sequentially one after another and ultimately leading to the achievement of the goal constitute an algorithm. For example, to withdraw money from an ATM, you need to perform a sequence of actions: insert a card, enter a PIN code, select the “Cash Withdrawal” command in the software menu, enter the required amount, print a receipt, return to the main menu or finish servicing the card.
An algorithm is a basic concept in computer science. It is a set of instructions, the implementation of which will lead to solving a given problem in a finite number of steps.
The term “Algorithm” got its name from the famous Eastern mathematician Muhammad al-Khwarizmi, who lived in Baghdad in the eighth century. Al-Khwarizmi's treatises made a great contribution to the development of medieval science.
Rice. 1. Muhammad al-Khwarizmi.
Computational complexity
The computational complexity of an algorithm is a measure of the amount of computing resources (time and space) that a particular sequence of operations consumes when run. Scientists then use a mathematical measure of complexity as a test, which allows them to predict, before writing code, how fast the algorithm will run and how much memory it will require. Such predictions are considered important guidelines for programmers implementing and selecting algorithms for real-world applications.
Computational complexity is a continuum. Because some sequences of actions require linear time (that is, the time taken increases directly with the number of elements or nodes that make up the list, graph, or network being processed), while others require a quadratic or even exponential amount of time to complete (that is, the time required increases with an increase in the number of objects squared or exponentially from their number).
At the far end of this continuum lie the murky seas of intractable problems—those whose solutions cannot be effectively implemented by linear methods. Therefore, computer scientists strive to find heuristic types of algorithms that can solve such problems in optimal time. Even further away are those algorithmic problems that can be posed, but cannot be solved in principle; that is, for them it can be proven that no program can be written to solve the problem.
A classic example of an undecidable algorithmic problem is the stopping problem, which states that no program can be written to predict whether any other program will stop after a finite number of steps. The undecidability of stopping has immediate practical implications for software development. For example, it would be frivolous to try to develop a software tool that predicts whether another program being developed has an infinite loop (although having such a tool is extremely useful).
In computer programming, as in algebra, there are many different ways to solve a given problem. At the same time, you need to understand that any algorithm has its advantages and disadvantages in different situations.
And the efficiency of its work on a specific task directly depends on the choice of the optimal set of sequences of actions for a computer.
Algorithm properties
An algorithm, as a basic concept of computer science, has a number of properties:
- Mass availability presupposes the suitability of the algorithm for various source data.
- Discreteness means that each stage of the algorithm represents a complete action.
- Unambiguousness means that the order of execution of the algorithm stages should be the same for all possible data sets.
- Finiteness means that the algorithm consists of a strictly defined number of steps.
Lesson summary and presentation on computer science “Information Processing” (with additional material)
Lesson objectives:
give students an idea of the information processing ,
introduce two types of information processing .
Lesson objectives:
Educational:
consolidating students' understanding of types of information and information processes ;
expanding the idea of a computer as a tool for processing numerical information.
Educational:
development of logical thinking, memory, attention, cognitive interest, research skills;
formation of information culture
Educational:
nurturing the desire to organize independent work, the ability to work in a group, and a culture of communication.
During the classes.
1. Organizational part.
The teacher checks the class's readiness for the lesson.
Hello guys, sit down.
2. Updating basic knowledge. Formulation of the problem.
We will start the lesson by reviewing theoretical material.
Tell me please,
1) What is information ?
2) How does a person receive information?
3) What types of information in the form of presentation do you know?
4) How does a person receive information?
Fine! What did you do to answer the questions I asked? (They thought and reasoned). What do you call what happens to information in a person’s head during reasoning? You will now find out by solving the rebus (Information Processing).
- "Data processing"
And today in class, what do you think we will do?
(Children express their opinions)
Right.
Now let's formulate the purpose of the lesson:
On the board you see pictures and what can you say about them?
Purpose of the lesson: Today in the lesson we must get an idea of how information is processed, find out in what ways information is processed.
Get acquainted with various methods of information processing through practical work.
In addition, we will analyze, compare, and draw conclusions.
Introduction to the information processing process.
The human brain is constantly busy processing information, even during sleep.
1. We hear the alarm ringing - we understand that it’s time to get up.
2. Before going outside, we look out the window and see that it is raining - we conclude that we need to take an umbrella.
3. We try the soup and realize that there is not enough salt.
4. We watch the film and empathize with the characters.
Give your examples of human information processing.
5. Information is also processed by technical devices, for example, a TV receives signals using an antenna, and we see the image and hear the sound. Give your examples of information processing by technical devices.
You are familiar with math problems. Let's consider one of them.
Example 1. 5th grade students planted 20 trees, and 6th grade students planted 5 trees more. How many trees did the children plant? Show task
When solving this problem, special attention should be paid to finding the initial data, the principle of solution and the result. We note that the condition specified numerical information. And the result was a number.
Now let's look at another example.
Example 2. There is a text: Muscovites love pets. According to surveys, 57% of city residents own dogs, 38% have cats, and 25% take care of parrots. Exotic animals have become quite common lately: iguanas (5%) and spiders (3%).
Let's change the way information is presented, present the text in tabular and graphical form.
Look how interesting it is in the second example: the source data was text, and the result was a diagram. Show chart
What happened?
Information processing has occurred, or rather, a change in the form of information presentation has occurred. The content of the information remains the same.
What can you say about the first example?
(It is important that the children themselves conclude that in the first example we simply received a result - new information, without changing its content).
Thus, there are two ways to process information:
Information processing associated with obtaining new information
Information processing associated with the transformation of information to a new form.
Question: Give examples of different ways of processing information. Indicate the input data and the result. (We listen and discuss 2-3 examples).
All material is in the archive.
Ways to write algorithms
Algorithms can be represented in different ways. There are the following ways to write algorithms:
- formulaic-verbal – the algorithm is specified using natural spoken language using special signs and formulas;
- graphic – the algorithm is reproduced using graphic objects arranged in the form of a flowchart;
- algorithmic language – the algorithm is implemented using keywords of a special algorithmic language.
Rice. 2. An algorithm written in an algorithmic language.
The most visual algorithm is an algorithm specified in the form of a flowchart, where each step is represented by a certain geometric figure: a rectangle replaces the computational process, a diamond represents a condition, a hexagon is used to denote a cycle with a known number of repetitions.
Rice. 3. Algorithm block diagram.
When developing flowcharts of algorithms, you should use the rules regulated in a special standard. On the territory of the Russian Federation there is a state standard - GOST 19.701-90 “Schemes of algorithms for programs, data and systems”.
Using Arrays
An array can be used to record and store a list of names. Efficient methods are needed to efficiently search and retrieve a specific name from an array. For example, sorting a list alphabetically allows you to use what is called a binary search method, in which the remainder of the list to be searched at each step is cut in half. This search method is similar to searching the phone book for a specific name. Knowing that the book is in alphabetical order, you can quickly jump to the page that is close to the page containing the desired name.
Many algorithms have been developed to process, sort, and search lists of data. Although elements are stored sequentially in memory, they can be linked to each other by pointers (essentially memory addresses stored with an element to indicate where the next element or elements in the structure are located), so that data can be organized in ways similar to those in which they will be available.
The simplest and most commonly used structure is called a linked list, in which contiguously stored elements can be accessed in a predetermined order by following pointers from one element in the list to the next.
The list can be circular, with the last element pointing to the first, or each element can have pointers in both directions to form a doubly linked list. Algorithm developments in this direction serve to effectively manage lists using the functions of searching, inserting and deleting elements.
