1 - Overview of an algorithm
An algorithm is a finite and unambiguous sequence of operations or instructions to solve a problem or obtain a result.
The word algorithm comes from the Arabic name الخوارزمي of the 9 th century Persian mathematician Al-Khwārizmî. The domain that studies algorithms is called algorithmics. Today we find algorithms in many applications such as computer operation, cryptography, information routing, planning and optimal use of resources, image processing, word processing, bio -informatic, etc.
2 - General definition of an algorithm
An algorithm is a general method for solving a type of problem. It is correct when, for each instance of the problem, it ends by producing the correct output, that is, it solves the problem. The effectiveness of an algorithm is measured notably by its computation time, by its consumption of RAM memory (assuming that each instruction has a constant execution time), by the precision of the results obtained (for example with use of probabilistic methods, like the Monte-Carlo method), its scalability (its ability to be effectively parallelized), etc. The computers on which these algorithms run are not infinitely fast: machine time remains a limited resource, despite a steady increase in computer performance. An algorithm will therefore be said to perform well if it uses sparingly the resources available to it, that is to say the CPU time, RAM memory and (aspect object of recent research) the power consumption. The analysis of the algorithmic complexity makes it possible to predict the evolution in computation time necessary to bring an algorithm to completion, according to the quantity of data to be processed.
3 - Some related definitions
George Boolos -1940-1996-, philosopher and mathematician, proposed the following definition "Explicit instructions for determining the nth member of a set, for n an arbitrarily large integer. Such instructions are given in a very explicit manner, in a form that can be used by a calculating machine or by a human who is able to transpose very elementary operations into symbols. "
Donald Knuth (1938-) listed the following five properties as the prerequisites of an algorithm:
finitude: "An algorithm must always end after a finite number of steps. "
precise definition: "Each step of an algorithm must be precisely defined, the actions to be transposed must be specified rigorously and unambiguously for each case. "
entries: "uantities given to it before an algorithm starts. These entries are taken from a specified set of objects. "
outputs: "... quantities having a specified relationship with the inputs. "
performance: "... all the operations that the algorithm must perform must be sufficiently basic to be able to be carried out in finite time by a man using a paper and a pencil. "
Gérard Berry -1948-, a researcher in computer science, gives the following general definition:
"An algorithm is simply a way of describing in great detail how to do something." It turns out that many mechanical actions, all probably, lend themselves to such decortication. The goal is to evacuate the thought of the calculation, in order to make it executable by a digital machine (computer ...). We only work with a digital reflection of the real system with which the algorithm interacts.
4 - Practical approaches for solving algorithmic problems
The algorithmic has developed some strategies to solve the problems:
greedy algorithm: a first algorithm can often be proposed by studying the problem very gradually: we solve each sub-problem locally hoping that all of their results will compose a solution of the global problem. We are talking about a greedy algorithm. The greedy algorithm is often only a first step in writing a more efficient algorithm;
divide and conquer: to improve the performance of algorithms, a common technique is to divide the data of a problem into subsets of smaller sizes, to obtain data that the algorithm can handle on a case by case basis. A second step in these algorithms is to "merge" the partial results to obtain a global solution. These algorithms are often associated with recursion;
exhaustive search (or combinatorial): a method using the huge computing power of computers is to look at all possible cases. This is only possible in certain particular cases (the combinatorics are often stronger than the huge power of computers, however huge);
top-down / bottom-up decomposition: (top-down decomposition, upward decomposition) top-down decompositions consist of trying to break down the problem into sub-problems to be solved successively, the decomposition going as far as trivial problems that are easy to solve. The global algorithm is then given by the compound of the algorithms defined during the decomposition. The bottom-up approach is the opposite approach, it consists of simple algorithms, solving only one stage of the problem, to try to compose them to obtain a global algorithm;
pre-processing / post-processing: sometimes, some algorithms have one or two phases identified as pre-treatments (to be done before the main algorithm), or post-processing (to be done after the main algorithm), to simplify the process. writing of the general algorithm;
dynamic programming: it applies when the optimization problem is composed of several sub-problems of the same nature, and an optimal solution of the global problem is obtained from optimal solutions of the sub-problems.
5 - Formal study
Many formal or theoretical tools have been developed to describe the algorithms, to study them, to express their qualities, to be able to compare them:
Thus, to describe the algorithms, algorithmic structures have been highlighted: control structures and data structures.
To justify the quality of the algorithms, the notions of correction, completeness and termination were put in place.
Finally, to compare the algorithms, a theory of the complexity of the algorithms has been defined.
6 - Algorithmic structures
The concepts implemented in algorithmic, for example according to the approach of N. Wirth for the most widespread languages (Pascal, C, etc.), are in small numbers. They belong to two classes:
Control structures
-sequences
-conditional
-loops
Data structures
-constants
-variables
-arrays
-recursive structures (lists, trees, graphs)
This division is sometimes difficult to perceive for some languages (Lisp, Prolog ...) more based on the notion of recursion where certain control structures are implicit and, therefore, seem to disappear.
