Intervention de Cédric Villani

– C'est justement toute la beauté de la science informatique, qu'il convient de bien différencier de l'informatique en tant qu'industrie. La science de l'informatique est la science de la complexité. Peu lui importe avec quels moyens physiques on réalise des opérations. Elle s'interroge sur le nombre d'opérations, sur leur degré de complexité, les instructions à utiliser, etc. Elle se demande, par exemple, combien d'opérations seront nécessaires pour multiplier deux nombres de mille chiffres chacun. Si le temps requis pour une multiplication élémentaire d'un chiffre par un autre chiffre est connu, est-il possible d'en extrapoler le temps total nécessaire ?

Cet exemple n'est pas anodin. On a cru pendant longtemps que multiplier un nombre à n chiffres par un autre nombre à n chiffres demanderait, en gros, n opérations au carré (n2), parce que chacun des chiffres sera multiplié par tous les chiffres de l'autre nombre. On s'est rendu compte, probablement voici quelques décennies, que cela pouvait être réalisé beaucoup plus vite, en n puissance 1,1 ou 1,2 opérations (n1,1 ou n1,2). Des algorithmes de multiplication rapide sont aussi apparus, avec des techniques basées sur les transformations de Fourier, permettant de réduire considérablement le nombre d'opérations nécessaires. Il s'agit d'informatique au sens de théories de la complexité, qui ne s'intéresse pas au dispositif physique, mais à la complexité de l'ensemble de l'opération.