Accueil🇫🇷Chercher

Algorithme d'Atlantic City

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%).

Algorithme d'Atlantic City
Date de découverte
1982[1]
Problème lié

Description

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

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

  1. (en) Richard A. Mollin, RSA and Public Key Cryptography (Technical Report), Chapman & Hall/CRC, .
  2. Atlantic City est une ville touristique américaine du New Jersey réputée pour ses casinos.
  3. (en) Richard A. Mollin (2003)
  4. (en) https://www.cs.cmu.edu/~15251/recitation/recitation11.pdf
  5. O est la notation de Landau, couramment utilisée en théorie de la complexité algorithmique.

Voir aussi

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.