Algorithmes randomisés

Les algorithmes randomisés effectuent des choix aléatoires au cours de leur exécution afin d'améliorer l'efficacité, la simplicité ou la robustesse, leurs performances et leur exactitude étant exprimées sous forme de garanties probabilistes plutôt que de certitudes dans le pire des cas.

Definition

Un algorithme randomisé est un algorithme qui utilise une source de bits aléatoires pour prendre certaines de ses décisions, de sorte que son temps d'exécution, sa sortie, ou les deux, sont des variables aléatoires analysées par leur espérance ou leur distribution de probabilité.

Scope

Ce sujet couvre les algorithmes qui utilisent l'aléatoire comme ressource computationnelle : le modèle de Las Vegas (toujours correct, temps d'exécution randomisé) et le modèle de Monte Carlo (temps d'exécution fixe, probabilité d'erreur bornée), des exemples canoniques tels que le tri rapide randomisé (randomized quicksort), la sélection randomisée (randomized selection), le test de primalité, et les structures de données randomisées comme les listes à sauts (skip lists), ainsi que les outils d'analyse probabiliste (espérance, variance, inégalités de queue et de concentration) utilisés pour les étudier.

Core questions

• Comment l'introduction de l'aléatoire peut-elle rendre un algorithme plus rapide ou plus simple que tout algorithme déterministe connu ?
• Quelle est la distinction entre les algorithmes de Las Vegas et de Monte Carlo ?
• Comment le temps d'exécution attendu ou la probabilité d'erreur sont-ils analysés ?
• Comment les inégalités de concentration bornent-elles la probabilité de résultats indésirables ?
• Comment l'erreur d'un algorithme de Monte Carlo peut-elle être réduite par répétition ?

Key concepts

• bits aléatoires comme ressource
• algorithme de Las Vegas
• algorithme de Monte Carlo
• temps d'exécution attendu
• probabilité d'erreur et amplification
• inégalités de concentration
• tri rapide randomisé
• listes à sauts

Key theories

Las Vegas contre Monte Carlo

Les algorithmes de Las Vegas produisent toujours un résultat correct mais ont un temps d'exécution randomisé (analysé en espérance), tandis que les algorithmes de Monte Carlo s'exécutent en un temps fixe mais peuvent produire un résultat incorrect avec une probabilité bornée, que la répétition peut réduire.

Test de primalité probabiliste

Les tests randomisés tels que Miller-Rabin certifient la primalité avec une grande confiance en temps polynomial en vérifiant des témoins aléatoires ; un nombre composé est révélé par la plupart des témoins, de sorte que des essais répétés rendent la probabilité d'erreur négligeable.

Clinical relevance

Les algorithmes randomisés sont largement déployés : le test de primalité de Miller-Rabin est à la base de la cryptographie à clé publique, le hachage randomisé (randomized hashing) et l'équilibrage de charge (load balancing) maintiennent l'efficacité des systèmes distribués, le tri rapide randomisé (randomized quicksort) et la sélection rapide randomisée (randomized quickselect) offrent des performances attendues robustes, et l'échantillonnage et l'esquisse randomisés (randomized sampling and sketching) permettent le traitement de flux de données massifs.

History

Les algorithmes probabilistes ont gagné en importance dans les années 1970 avec les tests de primalité de Solovay-Strassen et Miller-Rabin, qui ont fait de l'aléatoire un outil computationnel respectable. Les années 1980 et 1990 ont vu l'émergence des structures de données randomisées (listes à sauts (skip lists), treaps), des algorithmes randomisés de graphes et géométriques, et de la théorie systématique codifiée dans le manuel de Motwani et Raghavan de 1995.

Key figures

• Michael Rabin
• Robert Solovay
• Volker Strassen
• Rajeev Motwani
• Prabhakar Raghavan

Seminal works

• motwani1995
• rabin1980
• cormen2009

Frequently asked questions

Comment un algorithme de Monte Carlo peut-il être fiable s'il peut être erroné ?

Sa probabilité d'erreur est bornée et connue, et pour les algorithmes à erreur unilatérale, elle peut être rendue arbitrairement petite en exécutant l'algorithme plusieurs fois avec un aléa indépendant. Après suffisamment de répétitions, la probabilité d'une mauvaise réponse est bien inférieure à celle d'une défaillance matérielle.

Pourquoi le tri rapide randomisé est-il préféré au tri rapide déterministe ?

Le tri rapide déterministe peut atteindre son pire cas en O(n carré) sur des entrées adverses ou déjà triées en raison de mauvais choix de pivots. Le choix aléatoire des pivots rend ce pire cas extrêmement improbable quelle que soit l'entrée, offrant une performance attendue de O(n log n) sur chaque entrée.