Quatre jalons#
D'où vient le mot « algorithme » ?#
Vers l'an 820, à Bagdad, le savant Muhammad ibn Musa al-Khwarizmi travaille à la Maison de la Sagesse. Il écrit des manuels de calcul si clairs qu'on les recopie pendant des siècles. Quand ses livres arrivent en Europe, son nom est latinisé en « Algoritmi » - et finit par désigner toute méthode de calcul pas à pas.
Bonus : le titre d'un de ses ouvrages, al-jabr, nous a aussi donné le mot « algèbre ». Un seul savant, deux mots que tu utilises encore en classe.
Le plus vieux : l'algorithme d'Euclide#
Plus de 2000 ans avant le premier ordinateur, le mathématicien grec Euclide décrit une recette pour trouver le plus grand commun diviseur (PGCD) de deux nombres. Elle est si efficace qu'on l'utilise encore aujourd'hui, telle quelle, dans les calculatrices et la cryptographie.
L'idée : le PGCD de deux nombres est aussi le PGCD du plus petit et du reste de leur division. On répète jusqu'à ce que le reste tombe à zéro - le dernier nombre non nul est la réponse.
def pgcd(grand, petit): while petit != 0: grand, petit = petit, grand % petit return grandDéroule l'algorithme d'Euclide toi-même
Chaque ligne remplace le couple par (le plus petit, le reste). En quelques étapes seulement, même pour de très grands nombres : c'est un algorithme remarquablement rapide.
Ada Lovelace : le premier programme#
Ada Lovelace (1815-1852), mathématicienne anglaise, collabore avec Charles Babbage autour de sa machine analytique - un ordinateur mécanique jamais achevé. En 1843, dans ses notes, elle écrit une suite d'instructions pour lui faire calculer les nombres de Bernoulli. C'est considéré comme le tout premier programme informatique de l'histoire, écrit pour une machine qui n'existait pas encore.
Surtout, Ada comprend une chose que Babbage lui-même n'avait pas vue : une telle machine ne sert pas qu'à calculer des nombres. Si l'on sait traduire d'autres choses - des notes de musique, par exemple - en symboles, alors la machine peut les manipuler aussi.
Près d'un siècle avant le premier ordinateur, elle avait déjà entrevu l'informatique créative : musique, images, art générés par une machine. Exactement le monde dans lequel tu codes aujourd'hui. 🎵
Turing : ce qu'est un algorithme, au fond#
En 1936, le mathématicien Alan Turing imagine une machine abstraite très simple - un ruban, des symboles, des règles - et démontre qu'elle peut exécuter n'importe quel algorithme imaginable. Cette « machine de Turing » donne enfin une définition précise du mot algorithme et fonde l'informatique théorique.
Au passage, Turing prouve aussi qu'il existe des problèmes qu'aucun algorithme ne pourra jamais résoudre. Trier, chercher, calculer un PGCD : faciles. Mais certaines questions n'ont pas de recette - une frontière fascinante que tu croiseras plus tard.