Algorithme

Algorithme

Un algorithme est une suite finie et non ambiguë d’opérations ou d'instructions permettant de résoudre un problème ou d'obtenir un résultat.

Le mot algorithme vient du mot arabe الخوارزمي, nom du mathématicien du ix^e siècle Al-Khwârizmî. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs , la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le traitement d'images, le traitement de texte, la bio-informatique, etc.

Un algorithme est une méthode générale pour résoudre un ensemble de problèmes. Il est dit correct lorsque, pour chaque instance du problème, il se termine en produisant la bonne sortie, c'est-à-dire qu'il résout le problème posé. On mesure l'efficacité d'un algorithme notamment par sa durée de calcul, par sa consommation de mémoire RAM (en partant du principe que chaque instruction a un temps d'exécution constant), par la précision des résultats obtenus (par exemple avec l'utilisation de méthodes probabilistes, comme la méthode de Monte-Carlo), sa scalabilité (son aptitude à être efficacement parallélisé), etc. 

Les ordinateurs sur lesquels s'exécutent ces algorithmes ne sont pas infiniment rapides : le temps de machine reste une ressource limitée, malgré une augmentation constante des performances des ordinateurs. Un algorithme sera donc dit performant s'il utilise avec parcimonie les ressources dont il dispose, c'est-à-dire le temps CPU, la mémoire RAM et (aspect objet de recherches récentes) la consommation électrique. L’analyse de la complexité algorithmique permet de prédire l'évolution en temps calcul nécessaire pour amener un algorithme à son terme, en fonction de la quantité de données à traiter.

Quelques définitions connexes

Donald Knuth (1938‒) lista les cinq propriétés suivantes comme étant les prérequis d'un algorithme :

• finitude : « Un algorithme doit toujours se terminer après un nombre fini d’étapes. »
• définition précise : « Chaque étape d'un algorithme doit être définie précisément, les actions à transposer doivent être spécifiées rigoureusement et sans ambiguïté pour chaque cas. »
• entrées : « […] des quantités qui lui sont données avant qu'un algorithme ne commence. Ces entrées sont prises dans un ensemble d'objets spécifié. »
• sorties : « […] des quantités ayant une relation spécifiée avec les entrées. »
• rendement : « […] toutes les opérations que l'algorithme doit accomplir doivent être suffisamment basiques pour pouvoir être en principe réalisées dans une durée finie par un homme utilisant un papier et un crayon. »

George Boolos (1940‒1996), philosophe et mathématicien, proposa la définition suivante :

• « Des instructions explicites pour déterminer le nième membre d'un ensemble, pour n un entier arbitrairement grand. De telles instructions sont données de façon bien explicite, sous une forme qui puisse être utilisée par une machine à calculer ou par un humain qui est capable de transposer des opérations très élémentaires en symboles. »

Gérard Berry (1948‒), chercheur en science informatique en donne la définition grand public suivante:

• « Un algorithme, c’est tout simplement une façon de décrire dans ses moindres détails comment procéder pour faire quelque chose. Il se trouve que beaucoup d’actions mécaniques, toutes probablement, se prêtent bien à une telle décortication. Le but est d’évacuer la pensée du calcul, afin de le rendre exécutable par une machine numérique (ordinateur…). On ne travaille donc qu’avec un reflet numérique du système réel avec qui l’algorithme interagit. »

Algorithmes numériques

Les algorithmes sont des objets historiquement dédiés à la résolution de problèmes arithmétiques, comme la multiplication de deux nombres. Ils ont été formalisés bien plus tard avec l'avènement de la logique mathématique et l'émergence des machines qui permettaient de les mettre en œuvre, à savoir les ordinateurs.

Algorithmes non numériques

La plupart des algorithmes ne sont pas numériques.

On peut distinguer :

• des algorithmes généralistes qui s'appliquent à toute donnée numérique ou non numérique : par exemple les algorithmes liées au chiffrement, ou qui permettent de les mémoriser ou de les transmettre ;
• des algorithmes dédiés à un type de données particulier (par exemple ceux liés au traitement d'images).

Voir aussi : Liste de sujets généraux sur les algorithmes 

Algorithmes dans la vie quotidienne

L'algorithmique intervient dans la vie de tous les jours.

• Une recette de cuisine peut être réduite à un algorithme, si on peut réduire sa spécification aux éléments constitutifs :
• des entrées (les ingrédients, le matériel utilisé) ;
• des instructions élémentaires simples, dont l'exécution amène au résultat voulu ;
• un résultat : le plat préparé.

Cependant, les recettes de cuisine ne sont en général pas présentées rigoureusement sous forme non ambiguë : il est d'usage d'y employer des termes vagues laissant une liberté d'appréciation à l'exécutan alors qu'un algorithme stricto sensu doit être précis et sans ambiguïté.

• Le tissage, surtout tel qu'il a été automatisé par le métier Jacquard est une activité que l'on peut dire algorithmique.

• Un casse-tête, tel le Rubik's Cube, peut être résolu de façon systématique par un algorithme qui mécanise sa résolution.
• En sport, l'exécution de séquences répondant à des finalités d'attaque, de défense, de progression, correspond à des algorithmes (dans un sens assez lâche du terme).
• En soins infirmiers, le jugement clinique est un algorithme. Le jugement clinique désigne l'ensemble des processus cognitifs et métacognitifs qui aboutissent au diagnostic infirmier. Il met en jeu des processus de pensée et de prise de décision dans le but d’améliorer l’état de santé et le bien-être des personnes que les soignants accompagnent.

Article détaillé : Algorithme (sport).

Dans la vie quotidienne, un glissement de sens s'est opéré, ces dernières années, dans la notion « algorithme » qui devient à la fois plus réducteur, puisque ce sont pour l'essentiel des algorithmes de gestion du big data et d'autre part plus universel en ce sens qu'il intervient dans tous les domaines du comportement quotidien. La famille des algorithmes dont il est question effectue des calculs à partir de grandes masses de données (les big data). Ils réalisent de classement, sélectionnent des informations, et en déduisent un profil, en général de consommation, qui est ensuite utilisé ou exploité commercialement. Les implications sont nombreuses, dans les domaines les plus variés