Les algorithmes

Un algorithme est une suite d'actions précises, permettant de réaliser une tâche. Il ne permet pas la moindre ambiguité dans sa formulation, il faut donc être précis quand on le formule. Cette tâche peut être un nombre absurde de choses : faire le café, résoudre une équation, afficher de la 3D sur ordinateur... En effet, bien que beaucoup de gens le pensent, les algorithmes ne se restreignent pas à l'informatique ou aux mathématiques. Cependant, son fonctionnement peut nécessité une bonne connaissance de ces deux domaines, pour ne pas faire n'importe quoi.

Quand on voit cette définition, on peut penser qu'il s'agit de la même chose que d'autres mots plus courant de la vie quotidienne, comme un protocole ou une recette. Pour qu'un protocole ou une recette soit un algorithme, il faut qu'il soit précis et sans ambiguité. Si c'est le cas, il peut être qualifié d'algorithme. Sinon, ce n'en est pas un (c'est le cas en général, car une certaine liberté est laissée pour faciliter la tâche à la personne qui le fait). De plus, il doit adopter une certain structure, spécifique aux algorithmes (ce qui est, dans un certain sens, généralement le cas).

La complexité d'un algorithme est une valeur mathématique, correspondant au nombre d'instructions que l'algorithme demande. Plus il y a d'instructions nécessaires, plus l'algorithme prend du temps. En général, la complexité dépend du nombre de données à traiter. Cependant, elle peut représenter le carré, le cube, voir plus de ce nombre, le rendant presque insolube à partir d'une certaine quantité de valeurs. Il faut donc toujours prendre l'algorithme ayant la complexité la plus petite.

Pour représenter un algorithme, il faut pouvoir représenter les tâches qui le compose de manière précise. Pour cela, le format texte peut être utilisé, pour rendre l'algorithme le plus accessible possible. Cette représentation s'appelle "pseudo-code". Elle doit cependant garder certaines façons de faire que en vrai code. En général, cette représentation permet de convertir un algorithme pensé par quelqu'un qui ne sait pas coder, dans un langage permettant d'être facilement reproduit par un codeur en langage de programmation.

Bien que le pseudo-code ne soit soumit à aucune norme international, il est conseillé de faire quelque chose d'assez lisible et reconnaissable. L'institut Blaise Pascal en partage quelques une, ici. Il est d'ailleurs à noter que chaque personne a son propre type de pseudo-code, différant plus ou moins de celui de l'institut. Bien qu'il s'agit de quelques conventions informelles, le plus important est de se faire comprendre avec votre pseudo code.

Une des familles d'algorithmes les plus importantes au monde sont les algorithmes de tri. Le principe de ces algorithmes est de prendre un ensemble de données, et de les ranger selon certains critères (ceux que l'on veut). Les algorithmes de tri servent à de très nombreuses choses, comme à un classement, un rangement...

L'algorithme de tri le plus simple qu'il existe est l'algorithme de tri par sélection. L'idée de cet algorithme est de trouver le premier élément à ranger en comparant tous les éléments un à un. Après toutes les comparaisons, on ajoute cette élément à l'ensemble rangé, et on continue jusqu'à ce que tous les éléments est étés testés. Le problème est qu'il faut tester tous les éléments non rangés un à un, représentant une énorme quantité d'éléments à tester, rendant l'algorithme lent.

Un autre algorithme de tri très simple est l'algorithme de tri par insertion. Dans l'idée, cette algorithme est très similaire au tri par sélection. L'idée est de prendre le premier élément à ranger accessible des données non-rangées, quel que soit sa valeur. Il est en suite comparé aux éléments déjà rangés, pour trouver sa place précise parmis eux. On ré-itère la manoeuvre jusqu'à ce que tous les éléments non-rangés y soit passés. Le problème est qu'il faut tester le prochain élément à tous les éléments rangés un à un, pouvant représenter une énorme quantité d'éléments à tester, rendant l'algorithme lent. Cependant, il est en général plus rapide que le tri par sélection.

En général, aucun de ces deux algorithmes n'est utilisé en pratique, car ils sont trop lents. L'algorithme de tri le plus efficace à ce jour est l'algorithme de tri par fusion. Il s'appuie sur la logique de "diviser pour mieux régner". L'idée est de diviser les données à trier en 2 parts plus petites, et donc moins longues à trier. On doit en suite trier les données plus petites, puis fusionner les données divisées (et donc, déjà triées), tout en effectuant un simple tri lors de la fusion. L'efficacité de cet algorithme réside dans la réduction du nombre de données à trier, grâce à la division. De ce fait, trier les données divisées est beaucoup plus rapide, et le tri pendant la fusion s'effectue sur des données déjà triées, rendant le tout très efficace. En général, les données divisées subissent elles aussi un tri par fusion. En effet, cette algorithme est récursif (il s'utilise lui même, ici pour trier les données divisées). La récursion n'est pas infini, puis ce qu'elle s'arrête lorsque que le nombre de données à trier est de 2, où la division n'est plus utile. Il est très important de comprendre (ou, au moins, de connaître) cette algorithme car, si vous voulez être développeur, il est fortement probable que vous l'utilisiez dans votre carrière.

Dans un ensemble de données, la recherche d'un élément spécifique est aussi une étape très importante. Dans ce domaine, plusieurs familles d'algorithmes sont possibles. Si vous utilisez une structure de données spéciale pour la recherche, utiliser ses propriétés peut vous faire gagner beaucoup de temps. Par exemple, si elle est triée, l'algorithme adéquat est une recherche dichotomique, où vous devez découper la structure en 2 jusqu'à obtenir la valeur nécessaire (comme dans le tri par fusion). Si elle n'est pas triée, mais que vous avez d'autres informations sur le rangement des données, il faut adapter par vous même l'algorithme, selon le contexte (même si c'est, en général, assez complexe). Si vous n'avez aucune information sur le rangement des données, il faut toutes les essayer une par une, pour trouver la bonne (cette technique est appelée la force brute).

On pourrait passer des siècles à énumérer tous les algorithmes existants, mais ce n'est pas le plus intéressant à faire. À la place, nous allons voir un moyen de savoir si une suite d'instruction peut être considérée comme un algorithme ou pas. Une façon de faire est de représenter l'algorithme sous forme de machine de Turing. La machine de Turing est (à contrario de ce que son nom de "machine" laisse paraître) un concept purement mathématique. Il s'agit d'un ensemble de règles, qu'un algorithme doit respecter pour pouvoir être utilisé sans problèmes. Ces règles sont assez simples. La première dit que la machine est composé d'un ruban horizontal infini coupé en cases, pouvant comporter une données, sur lequel l'algorithme va travailler. La deuxième règle consiste à dire que ce ruban est modifiable via une tête de lecture, qui peut aller n'importe où sur le ruban. En gros, ces deux règles signifient que l'algorithme doit pouvoir travailler (lire et modifier) de la mémoire. La troisième règle dit que, à un moment T de son exécution, la machine se trouve dans un état (position / comportement de la tête de lecture) parfaitement défini parmi une liste d'états fini. À chaque mouvement de la tête de lecture, l'état change vers un autre. Il y a cependant deux états spéciaux : un état de commencement et un état final, qui arrête la machine. Finalement, la dernière règle oblige la machine à définir un comportement pour chaque état de la machine : modification de la mémoire, de la tête de lecture et de l'état actuelle. Ces 2 règles assurent que l'algorithme est une suite successif d'étapes, permettant son évolution dans le temps tant que la machine n'est pas arrêtée. Si une machine de Turing peut être réalisée via votre idée, alors elle peut être considérée comme un algorithme.

Si une simple machine de Turing pouvait décrire tous les algorithmes, le monde serait génial. Cependant, une simple machine de Turing ne suffit pas pour faire, par exemple, un jeu vidéo 3D. Pour cela, il faut une machine plus complexe, qui peut simuler le comportement de toutes les machines de Turing possible : une machine de Turing universelle. Par exemple, bien qu'il n'égale pas la perfection d'une machine de Turing universelle, un ordinateur s'en rapproche fortement, puis ce qu'il peut exécuter un très grand nombre d'algorithmes. Ce concept reste l'un des meilleurs pour exprimer mathématiquement le fonctionnement précis des algorithmes.