Le calcul probabiliste désigne une manière de calculer dans laquelle la machine a le droit de faire des choix au hasard au cours de son exécution. Une machine ordinaire est entièrement déterministe: à partir des mêmes données, elle suit toujours exactement le même chemin et aboutit toujours au même résultat. Une machine probabiliste, au contraire, peut à certains moments tirer quelque chose à pile ou face, pour ainsi dire, et orienter la suite de son calcul selon le résultat de ce tirage. La conséquence est qu’un même problème traité deux fois peut emprunter des trajectoires différentes, et que le résultat obtenu n’est plus garanti à coup sûr mais seulement avec une certaine probabilité. On accepte alors une petite marge d’erreur en échange, souvent, d’une rapidité ou d’une simplicité bien supérieures.
L’idée d’introduire le hasard dans les calculs remonte au milieu du vingtième siècle, avec les méthodes dites de Monte-Carlo employées dès les années 1940 pour estimer des quantités difficiles en simulant un grand nombre de tirages aléatoires. Elle prit toute son ampleur théorique dans les années 1970, lorsque des chercheurs découvrirent des algorithmes probabilistes remarquablement efficaces, notamment pour tester si un très grand nombre est premier, une question cruciale pour laquelle les méthodes classiques étaient alors bien plus lentes. On comprit qu’accepter une infime chance de se tromper pouvait rendre praticables des calculs autrement hors de portée, ce qui ouvrit un vaste champ d’étude sur la puissance exacte que le hasard apporte au calcul.
Le calcul probabiliste est aujourd’hui omniprésent, souvent sans qu’on s’en aperçoive. La cryptographie qui protège les communications repose sur des nombres tirés au hasard et sur des tests probabilistes de primalité. De nombreux algorithmes rapides de tri, de recherche ou de traitement de grandes masses de données exploitent des choix aléatoires pour éviter les cas défavorables. Les méthodes de simulation en physique, en finance ou en météorologie estiment par tirages répétés des résultats impossibles à calculer exactement. Il faut toutefois distinguer ce hasard maîtrisé, dont on sait borner le risque d’erreur, des idées plus spéculatives sur le calcul quantique, qui exploite d’autres propriétés de la matière et relève d’un cadre différent.
Laisser un commentaire