☰ Contents · Computing

The concept of an algorithm and its properties

Lessons 9 · 1 lessons · M. R. Fayziyeva, D. M. Sayfurov, N. S. Xaytullayeva. Informatics and Information Technologies, Grade 9. “Nashriyot uyi Tasvir”, Tashkent, 2020
9

The concept of an algorithm and its properties

Textbook: pp. 27–30
GoalKnows the ideas of an algorithm and an executor and the five properties of an algorithm (discreteness, definiteness, clarity, generality, finiteness of result) and spots them in examples.
New words
algorithm: a finite sequence of exact and understandable instructions for an executor to solve a problem · algoritmexecutor: a person, machine or program that carries out the instructions · ijrochiexecutor’s instruction set: the full set of commands the executor can carry out · ijrochining ko‘rsatmalar tizimifiniteness of result: after a finite number of steps the algorithm gives a result · natijaviylik
Explanation

The word “algorithm” comes from the Latinised reading of the name of the great scholar Muhammad ibn Musa al-Khwarizmi (c. 780–850), who lived in the 9th century and wrote works on the decimal system and algebra. An algorithm is a finite sequence of exact and understandable instructions that leads an executor to solve a problem. The executor may be a person, a robot, a computer or a program; the set of commands it can carry out is its instruction set, and an algorithm may use only commands from that set. The properties of an algorithm: discreteness – it splits into a finite number of simple steps; definiteness – each instruction has one meaning (for example “wait a bit” is vague); clarity – the executor can carry it out; generality – it works for all problems of the same kind; finiteness of result – it gives a result after a finite number of steps (the answer that the problem has no solution is also a result). One problem can have several correct algorithms.

Worked examples
A robot stands in the bottom-left cell of a grid; the battery is in the top-right cell (two cells right and two cells up). Instruction set: {right; up; down}. Algorithm: right, right, up, up. Another correct one: up, up, right, right – the solution is not unique.
For triangle sides 2, 3, 7 the existence check gives 2 + 3 = 5 ≤ 7, so the triangle does not exist and no area is computed. The algorithm ends with this “does not exist” answer – which still satisfies finiteness of result.
Class activity

“Robot executor”: one student is the robot, another the programmer. Using only the allowed commands the programmer guides the robot across a grid drawn on the floor to the “battery”.

Practice
1
List the five properties of an algorithm.
2
Which property does the instruction “salt the pilaf to taste” break?
3
Find the greatest common divisor of 48 and 18 by subtraction: keep subtracting the smaller from the larger until the numbers are equal.
4
Why is the property of generality useful?