Navigation – Plan du site
Leçons inaugurales

L’algorithmique et les sciences

Bernard CHAZELLE
p. 4

Texte intégral

1On rapporte du grand physicien danois, Niels Bohr, cette anecdote peutêtre apocryphe :

- Professeur Bohr, je vois que vous avez un fer à cheval accroché au mur. Ne me dites pas que vous croyez à ce genre de choses ! - Rassurez-vous, je n’y crois pas du tout, mais on m’a dit que ça marche même quand on n’y croit pas.

2Ainsi en va-t-il de la révolution algorithmique. Au-delà du scepticisme ou de l’engouement du jour pour la dernière nouveauté informatique se cache un de ces changements de paradigme chers à Kuhn. Outil conceptuel subversif, l’algorithme ouvre la possibilité d’un regard nouveau sur les sciences et les technologies qui s’étend au-delà de ses applications pratiques. Ce cours se propose d’expliquer les éléments constitutifs de cette révolution intellectuelle en marche.

3L’algorithme doit son nom à Abū ‘Abdallh Muhammad ibn Mūs al‑Khwrizmī, fer de lance de la renaissance abbasside à Bagdad au ixe siècle : un pedigree épris de zèle révolutionnaire. Vous ne retrouverez guère cette ferveur chez le passant sommé de vous définir le mot algorithme. Un algorithme, vous dira-t-il, c’est cette formule péniblement apprise sur les bancs d’école qui vous permet de multiplier deux nombres en alignant des chiffres en rang d’oignons. Tout le monde sait additionner, soustraire, et multiplier, ce qui fait grimper le nombre d’algorithmes universellement connus à trois – ou à quatre, si l’on compte les rescapés de l’ère numérique sachant encore diviser. Un algorithme est une séquence d’instructions à suivre pour arriver au résultat voulu par une série d’étapes simples et ennuyeuses. Ne vous laissez pas intimider par votre calculette. Elle ne connaît pas plus l’arithmétique qu’un cheval à Longchamp ne connaît le PMU. Ses algorithmes lisent, écrivent, et effacent sans comprendre quoi que ce soit.

4Un algorithme se définit indépendamment de la taille des données. Multiplier des nombres de 10 chiffres ou de 10 milliards suit non seulement le même principe mais le même mode d’emploi mot-à-mot. Seul le temps d’exécution diffère. La multiplication de deux nombres de 10 chiffres produit une grille de 10 rangées de 10 ou 11 chiffres chacune, et requiert un nombre d’étapes élémentaires au plus proportionnel à 10 × 11. En général, multiplier deux nombres de n chiffres chacun nécessite un nombre d’étapes au plus proportionnel à n(n + 1) ≈ n2 : on dit alors que la complexité de l’algorithme est de l’ordre de n2. Que le nombre d’étapes soit égal à n2, 3n2, ou 17n2 + n n’importe guère : seul compte l’ordre de grandeur, n². On n’ignore pas ces facteurs constants par paresse mais par un sens aigu des priorités. Ceux-ci souvent reflètent des détails de mise en œuvre extrinsèques à l’algorithme en question (tels que la base numérique pour la multiplication). Une autre raison de s’en débarrasser est de rendre à César ce qui est à César. Si votre calculette multiplie si vite, est-ce le fait d’un algorithme hors pair ou d’un processeur turbochargé ? En règle général, les facteurs constants sont attribuables à la puissance de l’ordinateur et les ordres de grandeur (tels que n2) à la complexité de l’algorithme.

  • 1 . Fürer, M. Faster integer multiplication, SIAM J. Comput., 39 (2009), 979-1005.
  • 2 Ailon, N., Chazelle, B. The fast Johnson-Lindenstrauss transform and approximate nearest neighbors, (...)

5La multiplication d’école est d’une complexité d’ordre n2. Peut-on faire mieux ? La réponse, affirmative, est à même de surprendre. Un algorithme de Schönhage et Strassen atteint une complexité d’ordre légèrement supérieur à n (pour être précis, d’ordre n log n log log n). Il est utile en pratique pour la factorisation des grands entiers. La méthode, améliorée récemment par Martin Fürer1, est basée sur un vieil algorithme, la transformée de Fourier rapide (FFT), un pilier du traitement du signal présent dans tous vos gadgets électroniques. Aussi étrange que cela puisse l’être, le même algorithme qui vous permet d’écouter de la musique et d’interpréter vos examens de IRMf va vous aider à multiplier des grands nombres très vite. La polyvalence fait la grandeur de l’algorithme, et la FFT de Gauss, redécouvert par Cooley et Tukey dans les années soixante, est un des plus grands. En collaboration avec Nir Ailon, j’ai montré comment randomiser la FFT pour exploiter le principe d’incertitude, un concept central en mécanique quantique, et faire de la recherche de voisins en très haute dimension2.

6Le reste de cette leçon pourrait faire l’inventaire des algorithmes qui, peut-être à votre insu, ont changé votre vie. Mais mon ambition est plus élevée. Elle est de vous convaincre que l’algorithme n’est pas tant un objet utile, qu’une façon différente de penser.

Leçon inaugurale à paraître aux Éditions Fayard et en ligne sur : http://lecons-cdf.revues.org/​
Vidéos des cours : www.college-de-france.fr

La chaire reçoit le soutien de l’INRIA

Haut de page

Notes

1 . Fürer, M. Faster integer multiplication, SIAM J. Comput., 39 (2009), 979-1005.

2 Ailon, N., Chazelle, B. The fast Johnson-Lindenstrauss transform and approximate nearest neighbors, SIAM J. Comput. 39 (2009), 302–322.

Haut de page

Table des illustrations

URL http://lettre-cdf.revues.org/docannexe/image/2369/img-1.png
Fichier image/png, 891k
Haut de page

Pour citer cet article

Référence électronique

Bernard CHAZELLE, « L’algorithmique et les sciences », La lettre du Collège de France [En ligne], 35 | décembre 2013, mis en ligne le 01 octobre 2015, consulté le 30 avril 2017. URL : http://lettre-cdf.revues.org/2369

Haut de page

Auteur

Bernard CHAZELLE

Professeur à l’université de Princeton, chaire Eugene Higgins d’Informatique.

Articles du même auteur

Haut de page

Droits d’auteur

© Collège de France

Haut de page