In this computer and digital age, programs are present in all areas of life. They are nothing more than a sequence of instructions and contain many algorithms whose ultimate role is to provide an answer to a specific problem. Algorithm design is an essential procedure in programming. It is for this reason that algorithmics, which studies the production of rules involved in the design of algorithms, was born. Here is everything you need to know about algorithms.
What is an algorithm?
An algorithm is a set of instructions designed to solve a given problem. The notion of algorithm is omnipresent in everyday life. Algorithms are used in a wide range of situations: recommending books to customers, recognising 3D images by comparison...
The origins of the algorithm
The term algorithm comes from the field of mathematics and is taken from the name of a Persian mathematician Muhammad ibn Moussa Al-Khuwarizmi born in 780, more commonly known as Al-Khwârismî. This scholar is notably the author of The Compendium of Calculation by Restoration and Comparison, the work that marks the genesis of algebra. Euclid's algorithm is probably one of the oldest algorithms known to date.
The computer algorithm
Computer science is undoubtedly the field of choice for algorithms. Computer programs are now written on a computer to perform a specific task. It mechanically executes different instructions to achieve the user's desired objective. To communicate these instructions to the user, it is necessary to use a computer programming language such as Python.
Acomputer algorithm is used when a computer is told how to perform a task. In programming, the possibilities of writing an algorithm to solve a given problem are infinite. At any given moment, it is the algorithms in the program code that allow computers and smartphones to function by making decisions. They ensure, among other things, the input of data, the calculation and display of results...
In computer science, not all algorithms are alike. One category of algorithm that is currently very popular is self-learning algorithms. Mainly used in the field of artificial intelligence or machine learning, these algorithms are able to learn and refine their accuracy over time. They are used, for example, for traffic prediction or medical image analysis.
In computing, an array is an ordered list of n values of the same type. The name n designates the size of the array and the internal values represent its elements. The elements are identified in the array by their index (usually between 0 and n-1). Each element is thus characterised by a unique index.
Example of an algorithm to browse an array
The following code represents an example of a basic algorithm for browsing an array:
- Algorithm DisplayTable (t: table)
- {displays all elements of an array}
- Variable i: integer
- Start
- For i ← 1 to size (t) do
- Write (t [i])
- End For
- End
This code is therefore very useful in computing. It is a function that can be learned from the beginning.
Example of an algorithm to find the smallest and largest elements of an array
To find the smallest and largest elements of an array, the following algorithm must be performed:
- Maximum algorithm (t: array of integers)
- {search for the largest element of an array of size n not zero}
- Variables i, max: integer
- Start
- max ← t [1]
- For i ← 2 at size (t) do
- If (t[i] > max)
- Then max ← t [i]
- End if
- End For
- Write (max)
- End
This code will make the search faster for a data scientist.
How to build a computer algorithm?
An algorithm is a statement in a well-defined programming language of a sequence of operations that solve a problem. To build a good computer algorithm, it is essential to know the characteristics of a good algorithm.
A good computer algorithm must be readable, i.e. understandable to people who are not computer literate. It must also be high-level, which means that it can be translated into any programming language. An algorithm must also be precise. No part of its code should be confusing. All ambiguities must be removed. The best algorithm for a given problem is the most concise, i.e. the least lengthy. Finally, a good algorithm must be well structured, i.e. broken down into easily identifiable parts.
In order to build an algorithm that scrupulously respects these characteristics, it is important to follow a strict methodology in several steps.
Clearly define the problem to be solved by the algorithm
An algorithm is used to solve a problem. It is therefore quite normal at the beginning to clearly state the problem before thinking about writing the algorithm. A clear understanding of the problem makes it possible to know exactly what the computer algorithm code has to do. It also makes it easier to determine the different steps the algorithm must go through to solve the problem.
After defining the problem, it is recommended to check whether there is not already a standard computer algorithm capable of solving it. After all, it would be counterproductive to write an algorithm if the task to be solved can be done by an already existing algorithm.
Interface definition
In order to maintain readability, it is advisable to copy the style of standard algorithms as much as possible when writing an algorithm. For the definition of the interface of the computer algorithm, the determination of the function name and arguments, the identification of the type of the output value should be carried out. This definition ends with the determination of the contracts of the interface, i.e. the requirements on the values of the arguments and the result.
Writing tests
Many programmers skip this step in the design of an algorithm, but it is nonetheless important. Tests are used to ensure that the algorithm works. Various tests can be written and the most important is probably the one that verifies that the algorithm does what it is supposed to do.
Writing the computer algorithm and its optimisation
At this stage, the work to be done is to write the code for the algorithm. As the problem is sequenced into different parts, the code for each part must be written. We then proceed to the optimisation of the algorithm. This includes checking the inputs to the computer algorithm and the results it produces. The accuracy of the results must be guaranteed at all times.
In the end, the algorithm must respect the following tripartite structure:
- A header: placed at the beginning, it is used to give a name to the algorithm,
- The declarative part of the algorithm: declaration of the different objects used by the computer algorithm: constants, variables, declaration of functions and procedures,
- The body of the algorithm: list of instructions to be executed by the computer algorithm.
To learn more about algorithms, it is important to take courses in this field.
Different types of algorithms
Existing computer algorithms can be classified into different types. For example, a distinction is made between sorting algorithms and recursive algorithms. These different types of algorithms can be learned in the framework of a certification course such as the one organised by Jedha in Data Science, Data Analysis, Data Engineering and Cyber Security.
Sorting algorithm
In computer programming, a sorting algorithm is an algorithm capable of organising a collection of objects according to a given order relation. Most often, the objects to be sorted are all elements of a finite set often given in the form of an array. To sort, an algorithm of this type will most often proceed by successive comparisons or will make restrictive hypotheses on the structure of the data to be sorted.
Different sorting methods are used by the algorithms. The complexity of these depends on the method used. These include selection sorting, bubble sorting, insertion sorting, quick sorting, etc.
For a better understanding of the different types of sorting algorithms, we suppose that we have at our disposal an array t of n integers numbered from 1 to n. We try to sort these different elements with index from 1 to n in an increasing order. We want to sort these different elements with indexes from 1 to n in an ascending order.
.jpg)
Sorting by selection
An algorithm of this type first looks for the smallest element of the array, i.e. an integer min such that t [k] >= t [min] for all k. The elements of the array of index 1 and min are then exchanged and the procedure resumes for the elements of index 2 to n.
The tri bull
With bull sorting, the algorithm traverses the array t from beginning to end and permutes all pairs of consecutive unordered elements. In other words, if the elements of index k and k+1 of the array are not ordered, this type of algorithm will swap them. After a first iteration, the largest element of the array is found in the last cell, i.e. the cell with index n. The procedure is then repeated for all the elements of index 1 to n-1 of the array.
Sorting by insertion
An algorithm of this type takes the element of index 1 from the beginning of the array, then the element of index 2 which it places according to the first element. It then inserts the index 3 element of the array in its place according to the first two. The general principle is thus to consider that the elements of index 1 and i-1 are sorted, then to place the element of index i of the table in its place among the i-1 supposedly sorted.
The Quiscksort
Invented by Sir Charles Antony Richard Hoare in 1960, it is the most widely used sorting method today. It applies the principle of "divide and conquer". An element of any index p in the table is considered and partitioned into two zones: elements with an index less than or equal to p and elements greater than or equal to p. The final place of the element p is found by putting the smallest elements in the top of the array and the largest in the bottom. The procedure is repeated on each partition created until it is reduced to a single element.
Recursive algorithm
In computer programming, a recursive algorithm is a type of algorithm that calls itself repeatedly until it has solved the problem. This type of algorithm is based on recursion, i.e. solving a problem by dividing it into sub-problems of the same type.
The recursive algorithm is the simplest type to design in computer programming since it does not require specific thought for each sub-problem. This type of computer algorithm most often uses one or more loops to speed up problem solving.
Other types of algorithms
Many other types of algorithms exist in programming. These include the greedy algorithm and the dynamic programming algorithm.
The greedy algorithm is used in the solution of optimisation problems. With this type of algorithm, the solution is constructed part by part. A decision is made when it is good at this stage without any consideration of the future. This type chooses the best local solution and considers it as optimal.
A dynamic programming algorithm attempts to solve each sub-problem once and stores its answer in an array. This saves it from having to recalculate the solution each time it solves one sub-problem below another. In simple terms, a dynamic programming algorithm solves complex problems by dividing them into several simple sub-problems. Each of these is solved and then stored in an array for later use.
Ultimately, algorithms are basic elements in programming. They provide problem solving in many areas. Algorithms often use data structures such as arrays, which further enhances their conciseness.
