Modelo Adversary

En ciencias informáticas, un algoritmo en línea mide su espíritu competitivo contra modelos del adversario diferentes. Para algoritmos deterministas, el adversario es lo mismo, el adversario autónomo adaptable. Para algoritmos en línea aleatorios el espíritu competitivo puede depender del modelo del adversario usado.

Adversarios comunes

Los tres adversarios comunes son el adversario inconsciente, el adversario en línea adaptable y el adversario autónomo adaptable.

El adversario inconsciente a veces se refiere como el adversario débil. Este adversario sabe el código del algoritmo, pero no llega a conocer los resultados aleatorios del algoritmo.

Llaman a veces al adversario en línea adaptable el adversario medio. Este adversario debe tomar su propia decisión antes de que se permita saber la decisión del algoritmo.

Llaman a veces al adversario autónomo adaptable el adversario fuerte. Este adversario sabe todo, hasta el generador de número arbitrario. Este adversario es tan fuerte que la randomización no ayuda contra él.

Resultados importantes

De S. Ben-David, A. Borodin, R. Karp, G. Tardos, A. Wigderson tenemos:

Véase también

Enlaces externos



Buscar