Les algorithmes : des boîtes noires, vraiment ?

Le mot « algorithme », jadis employé exclusivement dans certaines disciplines scientifiques, est maintenant partout. Parfois parés de vertus quasi magiques, parfois vilipendés, les algorithmes sont évoqués dans les débats sociaux et politiques. Pourtant, ils sont globalement mal connus, et le mot a fini par avoir des connotations bien éloignées de son sens scientifique.

Un algorithme est une méthode de calcul. On employait déjà le mot « algorithme » dans ce sens au début du XVIIe siècle, ou plus généralement dans le sens d’art calculatoire. Un algorithme a un but : par exemple, l’algorithme de multiplication qu’on apprend à l’école primaire a pour but… de multiplier deux nombres.

Un algorithme met en œuvre des opérations mécaniques, qui ne nécessitent pas de faire intervenir l’intuition ou l’intelligence de la personne qui calcule. Plusieurs algorithmes peuvent parvenir au même but, mais en nécessitant plus ou moins d’opérations, plus ou moins de place mémoire. Bien évidemment, en l’absence d’autres facteurs à prendre en compte, on essaye de minimiser ce temps de calcul et cet espace mémoire nécessaires.

Par exemple, il y a bien plus rapide que l’algorithme appris à l’école primaire si l’on veut multiplier des nombres avec beaucoup de chiffres. Cela peut paraître surprenant, tant cet algorithme nous est familier et ne semble pas faire de travail inutile ! Le grand mathématicien soviétique Andreï Kolmogorov avait conjecturé en 1956 qu’il n’existait pas d’algorithme de multiplication fondamentalement plus rapide, et avait été très surpris quand, en 1960, un jeune étudiant qui assistait à son séminaire, Anatoli Karatsouba, lui en avait proposé un. Les idées de Karatsouba ont ouvert une ligne de…