Algorithme d'Atlantic City
| Date de découverte |
1982[1] |
|---|---|
| Problème lié |
L'algorithme d'Atlantic City est un algorithme probabiliste en temps polynomial, qui répond correctement au moins 75% du temps (ou, dans certaines versions, une valeur > 50%).
Description[modifier | modifier le code]
Le terme « Atlantic City »[2] fut introduit pour la première fois en 1982 par J. Finn dans un manuscrit non publié intitulé Comparison of probabilistic tests for primality[3].
Deux autres classes courantes d'algorithmes probabilistes sont les algorithmes de Monte Carlo et les algorithmes de Las Vegas. Les algorithmes de Monte Carlo sont toujours rapides, mais seulement probablement corrects. D'autre part, les algorithmes de Las Vegas sont toujours corrects, mais seulement probablement rapides.
Inversement, les algorithmes d'Atlantic City, qui sont des algorithmes probabilistes en temps polynomial borné, sont probablement corrects et probablement rapides.
Problème[modifier | modifier le code]
Un problème classique, des premières années d'enseignement spécialisé en informatique dans l’enseignement supérieur, consiste à comparer le fonctionnement d'un algorithme « Atlantic City » à celui d'un algorithme de « Monte Carlo », comme suit[4]:
- Supposons que l'on vous donne un algorithme aléatoire qui résout f : Σ∗ → Σ∗ en un temps moyen polynomial T (n) et avec un écart type de l'erreur ε (c'est-à-dire que l'algorithme produit une approximation aléatoire, évaluée par ε, de la valeur de f, en un temps d'exécution aléatoire).
- Montrer que pour toute constante ε′ > 0, il existe un algorithme de Monte Carlo calculant f avec un temps d'exécution[5] O(T (n)) et un écart type ε + ε′ sur la solution.
Références[modifier | modifier le code]
- (en) Richard A. Mollin, RSA and Public Key Cryptography (Technical Report), Chapman & Hall/CRC, .
- Atlantic City est une ville touristique américaine du New Jersey réputée pour ses casinos.
- (en) Richard A. Mollin (2003)
- (en) https://www.cs.cmu.edu/~15251/recitation/recitation11.pdf
- O est la notation de Landau, couramment utilisée en théorie de la complexité algorithmique.
