C17 : Un peu d'histoire

L'algorithmique

Les premières traces d’algorithmes ont été retrouvées chez les Babyloniens (l’actuel Irak) au deuxième millénaire avant notre ère et étaient principalement des méthodes de calcul pour le commerce et les impôts. Il faut attendre le troisième siècle avant J.-C. en Grèce pour l’apparition du fameux algorithme d’Euclide pour le calcul du PGCD (Plus Petit Diviseur Commeun) : on peut considérer qu’il s’agit du premier algorithme « moderne » et il est tout à fait remarquable qu’il soit toujours utilisé de nos jours.

Mille ans plus tard, au IX^e siècle ap. J.-C., Al Khuwarizmi, un mathématicien perse (actuel Iran), publie un ouvrage consacré aux algorithmes : l’étymologie du terme « algorithme » vient du nom de ce mathématicien. On commence en effet à étudier les algorithmes en tant que tels, mais il faudra encore 800 ans avant que l’Occident continue cette étude.

Aux XVII^e et au XVIII^e siècles, des savants comme Pascal ou Leibniz construisent des machines à calculer mécaniques (la Pascaline en 1642) ou des automates, ouvrant ainsi la voie à l’automatisation du calcul et à la recherche d’algorithmes efficaces. En 1837, Wantzel résout le problème de savoir quelles longueurs il est possible de construire à la règle et au compas : il s’agit de connaître la capacité des algorithmes dont les opérations de bases sont celles de la règle et du compas. Ce sont les prémices de la calculabilité.

Sylvain Sperifel - 2014 - Complexité algorithmique

Petite histoire illustrée de l'informatique