vignette|upright=1 |Les étapes successives du fonctionnement du crible d'Ératosthène, un algorithme ancien, mais toujours d'actualité, qui permet de déterminer tous les nombres premiers plus petits qu'un entier donné, ici 120.
vignette|Un diagramme d'Ada Lovelace, le premier algorithme publié.
vignette|Algorithme de découpe d'un polygone quelconque en triangles (triangulation).
Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmesLa notion de problème peut être vue dans un sens large, il peut s'agir d'une tâche à effectuer, comme trier des objets, assigner des ressources, transmettre des informations, traduire un texte L'algorithme reçoit des données (les entrées), par exemple les objets à trier, la description des ressources à assigner, des besoins à couvrir, un texte à traduire, les informations à transmettre et l'adresse du destinataire, et fournit éventuellement des données (la sortie), par exemple les objets triés, les associations ressource-besoin, un compte-rendu de transmission, la traduction du texte.
Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications informatiques, dont dans les systèmes permettant le fonctionnement des ordinateursEn particulier dans les systèmes d'exploitation et la compilation, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le traitement d'images, le traitement de textes, la bio-informatique, l'intelligence artificielle, l'automatique
L'algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.
Étymologie et histoire vignette|Muḥammad ibn Mūsā al-Ḵwārizmī. (Il figure sur un timbre commémoratif de l'Union soviétique, émis le 6 septembre 1983. Le timbre porte son nom et la mention « 1200 ans », en référence à l'anniversaire approximatif de sa naissance.) Le mot algorithme a une longue histoire.
'Al-Khwârizmî (en arabe : ).. est un mathématicien persan du , dont le nom est relatif au Khwarezm, une région située au Sud de la mer d'Aral. Le traité qu’il écrivit en arabe, au , sera traduit en latin au , sous le titre Algoritmi de numero Indorum. "Algoritmie des nombres indiens"Al-Khwarizmi: The Inventor of Algebra.Ibid., .. Algoritmie est la latinisation de son nom par les traducteurs : Alchoarismi puis Algorismi, Algorismo, Algoritmi..
Un de ses ouvrages, Abrégé du calcul par la restauration et la comparaison, a d'ailleurs donné son nom à l'algèbre. Le titre de la traduction par Gilbert de Cremone en latin est Liber Maumeti filii Moysi Alchoarismi de Algebra et Almuquabala. On y retrouve traduit son nom : Maumeti filii Moysi Alchoarismi (Muhammad Ben Musa al Kwuwarizmi), dont Alchoarismi a donné « algorithme ».
Joannes Sacrobosco, moine ayant étudié à Oxford, est reçu à l'université de la Sorbonne le et élu professeur de Quadrivium peu après. C’est vers cette date qu’il compose De Algorismo.. Il est l'un des premiers docteurs du Moyen Âge à utiliser les écrits astronomiques des Arabes, considéré d'ailleurs en Angleterre comme ayant introduit l'usage des « chiffres » (sifer) que le pape avait tenté en vain de répandre plus tôt.
En 1240, Alexandre de Villedieu écrit son Carmen de Algorismo sur la science des chiffres.
Algoritmie désigne alors aussi ce nouveau système de numération, le système de numération de position avec le zéro.
Sous l’influence de l’ancien espagnol algorismo, le mot apparaît aussi en français déjà vers 1230 sous la forme augorisme, puis algorisme au , pour désigner le calcul en chiffres, l’arithmétique. La forme moderne du terme reprend le latin médiéval algorithmus, altération influencée par arithmetica et d'autres, du grec ancien arithmos = nombre.
En 1842, Ada Lovelace écrit le premier algorithme de programmation publié de l'histoire. Elle le fait à partir de la machine analytique de Babbage et beaucoup considèrent qu'elle est devenue ainsi la première informaticienne de l'humanité.
Définition générale Un algorithme est une méthode générale pour résoudre un type 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é.
L'efficacité d'un algorithme est mesurée notamment par : sa durée de calcul (en partant du principe que chaque instruction a un temps d'exécution constant) ; sa consommation de mémoire vive ; la précision des résultats obtenus (par exemple avec l'utilisation de méthodes probabilistes) ; sa scalabilité ; sa parallélisation ; son ergonomie et en particulier sa contrôlabilité son introspectabilité ; sa robustesse, résilience ou antifragilité au bruit, aux chocs et en particulier l'émergence et le chaos ;
Les ordinateurs sur lesquels s'exécutent ces algorithmes ne sont pas infiniment rapides, car 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 de processeur, la mémoire vive et, objet de recherches récentes, la consommation électrique. L’analyse de la complexité des algorithmes permet de décrire l'évolution en temps calcul nécessaire pour amener un algorithme à son terme, lorsque la quantité de données à traiter grandit.
L'émergence des langages de niveaux supérieurs pose le problème du temps :
soit on passe du temps à programmer avec des langages de bas niveau (le programme est alors rapide) ; soit on utilise des langages de haut niveau où une instruction est déjà constituée de plusieurs instructions de base. Le temps d'utilisation de la machine augmente alors de façon importante.
L'algorithme composé de boites peut ainsi être plus ou moins détaillé, précis.
Quelques définitions connexes Donald Knuth (1938-) liste, comme prérequis d'un algorithme, cinq propriétés. : finitude : ; définition précise : ; entrées : ; sorties : ; rendement : .
George Boolos (1940-1996), philosophe et mathématicien, propose la définition suivanteBoolos and Jeffrey 1974,1999:19. :
Gérard Berry (1948-), chercheur en science informatique, en donne la définition grand public suivanteUn petit condensé d'histoire de l'informatique, web-série didactique. :
Les entrées sont généralement associées à des capteurs et les sorties à des actions, actionneurs ou opérateurs (affichage, moteur).
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 entiers. 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 thumb|The Art of Computer Programming, un livre de référence sur des 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és 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 :
Algorithmes dans la vie quotidienne thumb|Carte perforée pour le tissage, Centre de Documentació i Museu Tèxtil. On remarquera la similitude avec celles utilisées pour représenter des algorithmes informatiques. L'algorithmique intervient de plus en plus dans la vie quotidienneVoir l'article traduit en français comme La pensée informatique et le livre de Gilles Dowek, .. 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 (frire, flamber, rissoler, braiser, blanchir) dont les exécutions dans un ordre précis amènent 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écutantHervé This Cours de gastronomie moléculaire, tome 1 : Science, technologie, technique… culinaires : quelles relations? , (2009) Éditions Quae/Belin. alors qu'un algorithme non probabiliste 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. Le tricot est enseigné parfois comme éveil aux algorithmes : les machines à tricoter des années 1980 fonctionnaient avec des cartes perforées. Un casse-tête, comme 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). Voir en particulier l'article tactique (football). En soins infirmiers, le jugement clinique est assimilable à un algorithme. Le jugement clinique désigne l'ensemble des procédés 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.. Un code juridique, qui décrit un ensemble de procédures applicables à un ensemble de cas, est un algorithme. Les procédures de dépannage sont des algorithmes. Le montage / démontage d'un meuble peut être considéré comme un algorithme.
Les progrès de ce qu'on appelle l'intelligence artificielle s'appuient sur un algorithmique de plus en plus complexe qui devient l'un des rouages cachés du Web 2.0 et des grands réseaux sociaux.
Critiques Dans la vie quotidienne, un glissement de sens s'est opéré, ces dernières années, dans le concept d'« 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 des classements, 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 et touchent les domaines les plus variésColloque « Gouvernance des algorithmes » du .. Mais les libertés individuelles et collectives pourraient être finalement mises en péril., comme le montre la mathématicienne américaine Cathy O'Neil dans le livre Weapons of Math Destruction, publié en 2016 et sorti en français en 2018 sous le titre Algorithmes : la bombe à retardement (aux éditions Les Arènes).
Dans cet ouvrage, l'auteure alerte le lecteur sur les décisions majeures que nous déléguons aujourd'hui aux algorithmes dans des domaines aussi variés que l'éducation, la santé, l'emploi et la justice, sous prétexte qu'ils sont neutres et objectifs, alors que, dans les faits, ils donnent lieu à « des choix éminemment subjectifs, des opinions, voire des préjugés insérés dans des équations mathématiques »..