The word algorithm is derived from the appellative “al-Khuwārizmī («native of Khwarazm») of the 9th-century mathematician Muḥammad ibn Mūsa. It designates a sequence of well-defined mathematical operations and rules that can be used to solve a problem.
In computer science, an algorithm is usually a sequence of computer instructions (written in a programming language) that executed by a computer starting from an initial set of data (the input) produce an answer (the output). The answer can be a simple Yes/No or another set of data (e.g a numeric value).
In informal language the words instructions, rules, steps, operations are often used as synonyms.
There are three important aspects of an algorithm:
- the instructions of an algorithm should be unambiguous: they can be expressed using natural language, or formulas, or they can be part of a programming language, but their meaning should be clear and fixed;
- also the sequence in which the instructions must be performed should be unambiguous;
- they should lead to the solution in a finite number of steps (in finite time).
Though the operations are unambiguous, sometimes it can be useful to use random values given as input or generated by some specific instructions.
An algorithm is
- deterministic if no randomness is used: on the same input it will always produce the same output;
- randomized if some kind of randomness is used; for example a specific instruction could produce a random value; in this case if we apply the algorithm to the same input we could obtain different results.
A simple example of algorithm that can be used to escape from a maze:
- turn yourself until you have a wall of the maze on your right side
- lay your right hand on that wall
- keep walking forward along the wall touched by your right hand
- never detach the right hand from the wall
… soon or later your right hand will “touch” the exit. This simple “algorithm” works well for mazes that don’t contain isolated parts or sections.