Algorithme d'Atlantic City

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.

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.

• Informatique théorique
• Hasard
• Générateur de nombres pseudo-aléatoires

• (en) https://brilliant.org/wiki/randomized-algorithms-overview/