The 1st theme: Introduction to the design of algorithms. Evaluation of algorithms in terms of volume and time. Horner's scheme for calculating the value of polynomials

The history of the term "algorithm"

• The rules in the books of al-Khwarizmi in Latin translation began with the words "Algorithmi said." In other Latin translations, the author was referred to as Algoritmus. Over time, it was forgotten that Algorism (Algorithm) is the author of the rules, and these rules began to be called algorithms. For many centuries, algorithms have been developed to solve more and more new classes of problems, but the very concept of an algorithm did not have an exact mathematical definition.

What is an algorithm?

• An algorithm is a clear and precise instruction to the performer to perform a sequence of actions aimed at achieving the goal.
• An algorithm is the idea behind any reasonable computer program.
• To be interesting, an algorithm must solve a general, well-specified problem. An algorithmic problem is specified by describing the complete set of instances it must work on and of its output after running on one of these instances. This distinction, between a problem and an instance of a problem, is fundamental.

Basic properties of the algorithm

• Any algorithm must have the following properties:
• certainty - in a finite number of steps, either a result must be obtained, or its absence is proved;
• performance - the obligatory receipt of some result (number, table, text, sound, image, etc.) or a signal that this algorithm is not applicable to solve the problem;
• mass character - the possibility of obtaining a result with different initial data for a certain class of similar tasks;
• formality - distraction from the content of the task and the strict implementation of a certain rule, instruction;
• discreteness - the possibility of dividing the algorithm into separate elementary actions.

Ways of representing the algorithm

• There are the following forms of representation of the algorithm:
• Verbal in informal language.
• In programming languages.
• Graphic.