Comment en sommes-nous arrivés là ? L’histoire des algorithmes.
Jusqu’à récemment, les algorithmes étaient un domaine réservé aux informaticiens. Mais maintenant, ils sont entrés dans nos vies et deviennent omniprésents. Algorithme n’est plus un mot étranger. Le trading algorithmique, les préjugés algorithmiques, l’algorithme de Facebook, et même la guerre algorithmique – tous ces termes font désormais partie de notre vocabulaire depuis quelques années. Certains vont jusqu’à prétendre que nous vivons dans une nouvelle ère : l’ère de l’algorithme. Mais les algorithmes ne sont pas si nouveaux que cela. Nous les utilisons, sciemment ou non, depuis des centaines et des milliers d’années. Les algorithmes ne sont que des descriptions spécifiques d’actions étape par étape qui doivent se produire pour obtenir un résultat particulier. Ils sont l’un des instruments les plus courants de partage des connaissances.
Pratiquement, tout processus consistant à enseigner à quelqu’un comment faire quelque chose utilise des algorithmes.
Certains aspects des algorithmes ont cependant changé au cours des dernières décennies. En particulier, l’introduction des ordinateurs signifie que de nombreux algorithmes d’aujourd’hui sont dramatiquement plus complexes que ce que nous aurions pu imaginer dans le passé. Comment les algorithmes ont-ils évolué pour devenir beaucoup plus sophistiqués aujourd’hui qu’ils ne l’étaient dans le passé ? Jetons un bref coup d’œil à leur histoire.
Algorithmes guidant les actions humaines
Le terme algorithme dérive du nom de Muhammad ibn Mūsā al’Khwārizmī, un mathématicien perse du IXe siècle. Son nom latinisé, Algoritmi, signifiait « le système de nombres décimaux » et a été utilisé dans ce sens pendant des siècles. La notion moderne d’algorithme est apparue en anglais au XIXe siècle, et est devenue plus couramment utilisée depuis les années 1950, déclenchée par l’émergence des premiers ordinateurs disponibles dans le commerce.
Bien avant que les algorithmes obtiennent leur nom moderne cependant, ils étaient couramment créés et utilisés.
Les premiers algorithmes ont été capturés sur papier dans la Grèce antique. Des savants tels que Nicomaque de Gérasa ou Euclide créaient alors les éléments constitutifs des mathématiques modernes. Pour faciliter la compréhension et l’applicabilité de leurs idées, ils ont exprimé nombre d’entre elles sous forme d’actions étape par étape.
Nicomachus de Gerasa a introduit le Tamis d’Eratosthène. Le tamis est utilisé à ce jour par les étudiants qui apprennent à écrire un code informatique efficace. Il a permis de simplifier le processus d’identification des nombres premiers. Les nombres premiers sont des nombres naturels, supérieurs à un, qui ne peuvent être formés en multipliant deux nombres naturels plus petits. Par exemple, quatre n’est pas un nombre premier car il peut être formé en multipliant deux par deux. Cinq, en revanche, est un nombre premier, car aucun nombre naturel plus petit que cinq ne peut être multiplié pour former cinq. S’il n’est pas trop difficile d’identifier les premiers nombres premiers (par exemple 2, 3, 5, 7, 11, 13, 17, 19, 23 et 29), trouver les grands nombres premiers prend beaucoup de temps. Or, les grands nombres premiers sont essentiels en cryptographie. Le crible d’Ératosthène donne des instructions étape par étape pour éliminer rapidement tous les nombres non premiers d’un ensemble défini de nombres (par exemple entre 1 et 10 000) jusqu’à ce qu’il ne reste que des nombres premiers. Aujourd’hui, il existe de nombreux algorithmes qui simplifient la tâche d’identification de ces nombres. Le tamis d’Eratosthène a lancé toute une famille d’algorithmes qui ont le même objectif et qui deviennent meilleurs (plus rapides, ou nécessitant moins d’étapes) pour détecter les nombres premiers.
Euclide, l’autre savant mentionné ci-dessus, beaucoup plus connu que Nicomaque de nos jours, a introduit un algorithme pour identifier le plus grand diviseur commun de deux nombres. Là encore, la tâche n’est pas toujours facile, mais elle est essentielle dans de nombreuses situations. L’algorithme d’Euclide a contribué à rendre ce calcul facile. Pourquoi l’algorithme d’Euclide est-il utile ? Imaginez que vous avez une pièce dont les dimensions exactes sont de 612 par 2006 centimètres et qui a besoin d’un nouveau plancher. L’algorithme d’Euclide vous aidera à trouver la taille des plus grands carreaux carrés qui couvriraient proprement le sol. La réponse, donnée par l’algorithme, est 34 cm sur 34 cm, ce qui donne une disposition de 18 carreaux sur 59. Bien sûr, tous les carreleurs vous diront que la réponse est fausse et que vous n’avez aucune idée de ce que vous faites, car l’algorithme ne tient pas compte de la largeur du joint et ne lui laisse aucun espace. N’ayez crainte : cela peut aussi être calculé, et proprement exprimé sous forme d’algorithme.
Algorithmes guidant les actions des machines
Au cours des plusieurs centaines d’années qui ont suivi, de nombreux autres algorithmes ont été créés et capturés sur papier. Ils ont ensuite été utilisés par des individus et suivis étape par étape. Le premier algorithme destiné à être exécuté sur une machine a été créé par Ada Lovelace (née Byron) et publié en 1843.
Ada était un personnage intriguant. Elle est née en 1815, seul enfant légitime du poète Lord Byron. Elle a développé de grands talents en mathématiques. Et comme l’amour de la poésie était clairement inscrit dans ses gènes, elle a réussi à développer et à équilibrer l’amour de la science et de la poésie. Ada décrivait elle-même son état d’esprit comme une « science poétique ». En tant qu’habile mathématicienne, elle a fait la connaissance de Charles Babbage, souvent appelé « le père des ordinateurs », grâce à ses inventions. Ils ont tous deux développé une relation de travail et une amitié. Ada était très intéressée par l’une des conceptions de Charles – le moteur analytique.
Le Moteur Analytique était un ordinateur mécanique – une machine qui automatisait les calculs. C’est pour le moteur analytique qu’elle a écrit le premier algorithme. Son travail était une formule montrant comment configurer la machine pour calculer une séquence complexe particulière de nombres, appelés nombres de Bernoulli. Cette formule est aujourd’hui largement reconnue comme le premier algorithme informatique de l’histoire.
Ada ne s’est pas seulement limitée aux calculs mathématiques purs. Étant donné qu’elle vivait au XIXe siècle, elle était une véritable visionnaire.
Alors que beaucoup de ses contemporains voyaient les premiers ordinateurs mécaniques principalement comme des compteurs de chiffres, elle se demandait ce qu’il y avait au-delà de l’exécution de calculs. Elle était curieuse du potentiel plus large des ordinateurs mécaniques en tant qu’outils de collaboration. Elle espérait voir des ordinateurs qui donneraient du pouvoir aux humains bien plus qu’en automatisant des calculs.
Malheureusement, la construction du moteur analytique n’a pas été achevée avant la mort d’Ada, et elle n’a donc jamais pu voir son algorithme en action. Malheureusement, le moteur analytique n’a pas été construit à ce jour. Une autre conception de Charles Babbage, le Difference Engine №2, n’a été construite par le London Science Museum qu’en 1991. Il a été démontré qu’il était fonctionnel, en utilisant les matériaux et les technologies dont disposait Charles Babbage. Il semble que Babbage n’ait pas eu de chance lorsqu’il s’agissait de faire construire ses modèles. D’autres implémentations partielles du travail de Charles existent ailleurs, mais malheureusement, nous ne pouvons pas exécuter l’algorithme d’Ada Byron sur un véritable Analytical Engine.
Le XIXe siècle est devenu l’ère des « algorithmes intégrés dans les machines ».
Ils étaient nombreux, automatisant toutes sortes d’actions humaines. Si vous aviez besoin d’un motif complexe sur une pièce de tissu, Joseph Marie Jacquard, un tisserand et marchand français, avait une solution pour vous : le métier à tisser Jacquard. Il permettait aux fabricants de tissus de produire des motifs sophistiqués à l’aide d’une série de cartes perforées qui indiquaient au métier comment tisser. De la même manière, les premiers centraux téléphoniques utilisaient des dispositifs mécaniques sophistiqués pour connecter les appels téléphoniques. Ils suivaient automatiquement des instructions étape par étape pour permettre à deux personnes de se parler. Ces machines, qu’il s’agisse de métiers à tisser ou de centraux téléphoniques, étaient révolutionnaires à leur époque et sont encore impressionnantes aujourd’hui. Il est difficile de ne pas admirer le niveau de complexité de certaines de ces machines. Cependant, tous ces dispositifs étaient encore purement mécaniques. Ils étaient constitués de leviers, d’interrupteurs, d’arbres. Ils faisaient beaucoup de bruit. Et ils étaient très loin de ce que nous appelons aujourd’hui des ordinateurs.
Algorithmes sur les ordinateurs à usage général
Il a fallu attendre les années 1930 pour voir les premières mentions d’algorithmes sur des ordinateurs électroniques (non mécaniques). Alan Turing a été parmi les premiers scientifiques à saisir formellement la façon dont les individus effectuaient des calculs. L’objectif de Turing était de saisir un processus général, plutôt qu’un processus spécifique à une tâche particulière, comme l’identification des nombres premiers ou le calcul du plus grand diviseur commun. Le processus général pouvait ensuite être utilisé pour effectuer des tâches spécifiques. Le travail conceptuel de Turing a conduit au développement de ce que l’on appelle aujourd’hui la machine de Turing. La machine de Turing, à son tour, a conduit à l’émergence des ordinateurs à usage général. Le préfixe « universel » est essentiel ici. Contrairement aux machines précédentes, les nouveaux ordinateurs pouvaient exécuter des ensembles d’instructions arbitraires. Ils pouvaient être utilisés à des fins qui n’avaient même pas été prévues par leurs créateurs. En d’autres termes : Les travaux de Turing ont conduit au développement d’ordinateurs sur lesquels nous pouvons installer et exécuter des applications.
Pas de Flappy Bird sur votre smartphone sans le concept de machine de Turing.
Des décennies plus tard, les algorithmes sont devenus extrêmement sophistiqués. Si sophistiqués, en fait, qu’il nous est souvent impossible d’expliquer leur fonctionnement. Au vingtième siècle, beaucoup préféraient considérer les algorithmes informatiques comme des boîtes noires. Il n’était pas nécessaire de comprendre comment ils fonctionnaient exactement. Tout ce qui comptait, c’était les entrées – ce qui entrait dans la boîte noire – et les sorties – ce qui en sortait. Cette simplification était un choix. Au XXIe siècle, pour certains algorithmes, ce n’est plus un choix : les humains ne peuvent pas expliquer exactement comment les algorithmes atteignent des résultats particuliers, et nous sommes donc obligés de considérer ces algorithmes comme des boîtes noires, voire magiques. Certains algorithmes d’intelligence artificielle font partie de ce groupe. Nous pouvons expliquer leurs principes. Par exemple, nous pouvons dire qu’un algorithme utilise un réseau neuronal artificiel. Nous pouvons également expliquer comment le réseau a été créé, et comment l’entrée a donné lieu à une sortie particulière. Ce que nous ne pouvons pas expliquer, en revanche, c’est pourquoi ce résultat particulier est la sortie de l’algorithme, au-delà d’une explication purement mécanique. Eric L. Loomis, dont la durée d’incarcération dépendait d’un algorithme, a essayé de comprendre pourquoi l’algorithme COMPAS l’avait évalué comme un criminel à haut risque. C’était tout simplement impossible. La sophistication des algorithmes est souvent écrasante. Et ce n’est que le début.
Nous vivons dans un monde où les algorithmes sont partout – pas seulement sur le papier ou dans nos esprits, mais contrôlant les machines, les ordinateurs et les robots.
Ils sont petits, omniprésents et – au moins dans certains cas – inexplicables.
Une définition plus formelle d’un algorithme est « une spécification non ambiguë de la façon de résoudre une classe de problèmes » ou « un ensemble autonome, étape par étape, d’opérations à effectuer »
www.oed.com/view/Entry/4959
En octobre 2018, le plus grand nombre premier connu est 277 232 917- 1, un nombre de 23 249 425 chiffres. Le simple fait de vérifier si ce seul nombre est premier a nécessité six jours de calcul non-stop sur un ordinateur domestique contemporain. (https://www.mersenne.org/primes/press/M77232917.html)