L’HISTORIQUE D’ALGORITHME

L’histoire des algorithmes est fascinante et s’étend sur plusieurs

1
millénaires 📜🔢. Voici un aperçu chronologique de leur évolution :

Antiquité

 Euclide (env. -300) : Formalise l’algorithme du plus grand commun

diviseur (PGCD), encore utilisé aujourd’hui.
 Ératosthène : Crée le célèbre crible d’Ératosthène pour identifier
les nombres premiers.
 Archimède : Utilise un algorithme pour approximer la valeur de π.

🧮 Moyen Âge

 Al-Khwârizmî (IXe siècle) : Mathématicien perse dont le nom a

donné naissance au mot "algorithme". Il rédige un traité sur les
calculs avec les chiffres indo-arabes, qui sera traduit en latin sous le
nom Algoritmi de numero Indorum3.
 Adelard de Bath (XIIe siècle) : Introduit le mot algorismus en
Europe, dérivé du nom d’Al-Khwârizmî.

📐 Époque moderne

 Leibniz (XVIIe siècle) : Imagine une machine à calculer et

développe l’idée d’un calcul ratiocinateur, une forme primitive
d’algèbre logique.
 George Boole (1847) : Crée l’algèbre booléenne, base de la
logique informatique moderne.
 Frege, Peano, Russell, Whitehead : Formalisent les
mathématiques avec des langages symboliques.

🧠 XXe siècle – naissance de l’informatique

  Alan Turing (1936) : Propose le concept de machine de Turing,
une abstraction fondamentale pour comprendre les algorithmes et la
computation.
2
 Kurt Gödel (1931) : Travaille sur les limites de la logique formelle,
influençant la théorie des algorithmes.

🤖 Aujourd’hui

Les algorithmes sont omniprésents : intelligence artificielle, cryptographie,

traitement d’images, moteurs de recherche, réseaux sociaux… Ils sont au
cœur de notre monde numérique.

L'algorithme a une longue histoire qui remonte aux civilisations

antiques, avec des méthodes de calcul découvertes en
Mésopotamie et les travaux d'Euclide. Le terme "algorithme"
dérive du nom du mathématicien persan Al-Khwarizmi, dont
l'ouvrage sur l'arithmétique a été traduit en latin au XIIe
siècle. Bien que le concept soit ancien, le développement de
l'informatique a élargi la définition de l'algorithme à une
procédure systématique pour résoudre des problèmes, tandis
qu'Ada Lovelace est souvent citée comme la conceptrice du
premier algorithme informatisé.

Un algorithme est une suite finie et non ambiguë d'instructions et

d’opérations permettant de résoudre une classe de problèmes 1. [ ]

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 ordinateurs2,[ ]
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, etc.
L'algorithme peut être mis en
un algorigramme ou organigramme de programmation.
forme de façon graphique dans
3
Étymologie et histoire
[modifier | modifier le code]

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 : ‫)الخوارزمي‬3,4 est [ ] [ ]

un mathématicien persan du IXe siècle, 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 IXe siècle, sera traduit
en latin au XIIe siècle, sous le titre Algoritmi de numero Indorum.
"Algoritmie des nombres indiens" 5,6. Algoritmie est la latinisation de son
[ ] [ ]

nom par les traducteurs : Alchoarismi puis Algorismi, Algorismo, Algoritmi 7. [ ]

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) et le
fameux Alchoarismi.

Joannes Sacrobosco, moine ayant étudié à Oxford, est reçu à l'université

de la Sorbonne le 5 juin 1221 et élu professeur de Quadrivium peu après.
C’est vers cette date qu’il compose De Algorismo8. 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 Sylvestre II 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

4
système de numération de position avec le zéro7. [ ]

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 XIIIe siècle, 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 de

l'histoire. Elle le fait à partir de la machine analytique de Babbage et
devient la première informaticienne de l'humanité 9. [ ]

Définition générale
[modifier | modifier le code]

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
particulier l'émergence et le chaos ;
bruit, aux chocs

Les ordinateurs sur lesquels s'exécutent ces algorithmes ne sont pas

et en
5
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

[modifier | modifier le code]

Donald Knuth (1938-) liste, comme prérequis d'un algorithme, cinq

propriétés10 :
[ ]

 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
rigoureusement et sans ambiguïté pour chaque cas » ;
doivent être spécifiées 6
 entrées : « 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 : « 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, propose la

définition suivante11 :
[ ]

 « 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 12 : [ ]

 « Un algorithme, c’est tout simplement une façon de décrire dans ses

moindres détails comment procéder pour faire quelque chose 13. 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. »

Les entrées sont généralement associées à des capteurs et les sorties à

des actions, actionneurs ou opérateurs (affichage, moteur, etc.).

Algorithmes numériques
[modifier | modifier le code]

Les algorithmes sont des objets historiquement dédiés à la résolution de

problèmes arithmétiques, comme la multiplication de deux nombres. Ils
7
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

[modifier | modifier le code]

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 : Liste de sujets généraux sur les algorithmes (en)