Algorithme d'Atlantic City

Algorithme d'Atlantic City

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

modifier - modifier le code - modifier Wikidata

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

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/

• Portail de l'informatique théorique