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 Le terme « Atlantic City »Atlantic City est une ville touristique américaine du New Jersey réputée pour ses casinos. fut introduit pour la première fois en 1982 par J. Finn dans un manuscrit non publié intitulé Comparison of probabilistic tests for primality Richard A. Mollin (2003).
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 https://www.cs.cmu.edu/~15251/recitation/recitation11.pdf:
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écutionO est la notation de Landau, couramment utilisée en théorie de la complexité algorithmique. O(T(n)) et un écart type ε + ε′ sur la solution.
Références
Voir aussi Informatique théorique Hasard Générateur de nombres pseudo-aléatoires
Liens externes https://brilliant.org/wiki/randomized-algorithms-overview/
Atlantic City Catégorie:Méthode algorithmique