Hispanopedia Wiki
Articulo de referencia

Algoritmo de Atlantic City

En informática, un algoritmo de Atlantic City es un algoritmo aleatorio que responde correctamente al menos el 75 % de las veces [ 1 ] . En algunas definiciones variantes, el um...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática, un algoritmo de Atlantic City es un algoritmo aleatorio que responde correctamente al menos el 75 % de las veces [ 1 ] . En algunas definiciones variantes, el umbral de corrección puede ser cualquier valor superior al 50 % [ 2 ] . En cualquier caso, los algoritmos de Atlantic City son tipos de algoritmos de Monte Carlo .

Existe un algoritmo de Atlantic City de tiempo polinomial para cualquier problema perteneciente a la clase BPP de problemas probabilísticos acotados de tiempo polinomial [ 1 ] .

Los algoritmos de Las Vegas , que nunca devuelven una respuesta incorrecta, son el dual de los algoritmos de Monte Carlo y, por lo tanto, de los algoritmos de Atlantic City.

El nombre hace referencia a Atlantic City, en el estado estadounidense de Nueva Jersey . Al igual que Montecarlo y Las Vegas , Atlantic City está ampliamente asociada con los casinos y la cultura del juego.

Véase también

Referencias

  1. 1 2 Bach, Eric; Shallit, Jeffrey (1996). Teoría algorítmica de números, Volumen 1: Algoritmos eficientes . Cambridge: MIT Press. págs.  51-52. ISBN 0-262-02405-5.
  2. ↑ Mollin, Richard (2003). RSA y criptografía de clave pública . Boca Raton: Chapman & Hall/CRC. pág. 80. ISBN  1-58488-338-3.
Lecturas relacionadas
6 articulos
{\displaystyle \lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}Algoritmo aleatorioUn algoritmo aleatorio es un algoritmo que emplea un grado de aleatoriedad como parte de su lógica o procedimiento. El algoritmo normalmente utiliz...Algoritmo de Monte CarloAlgoritmo de Monte CarloEn informática , un algoritmo de Monte Carlo es un algoritmo aleatorio cuyo resultado puede ser incorrecto con una probabilidad determinada (normal...{\displaystyle M(x,y)=1}BPP (complejidad)En la teoría de la complejidad computacional , una rama de la informática, el tiempo polinomial probabilístico de error acotado ( BPP ) es la clase...{\displaystyle T(n)=T(0)+T(n-1)+\Theta (n)}Algoritmo de Las VegasEn informática , un algoritmo de Las Vegas es un algoritmo aleatorio que siempre da resultados correctos ; es decir, siempre produce el resultado c...Dualidad (matemáticas)Dualidad (matemáticas)En matemáticas , una dualidad traduce conceptos, teoremas o estructuras matemáticas en otros conceptos, teoremas o estructuras de manera biunívoca ...Atlantic City, Nueva JerseyAtlantic City, Nueva JerseyAtlantic City , a veces conocida por sus iniciales AC , es una ciudad turística costera de Jersey Shore en el condado de Atlantic , en el estado es...