Modelo adversário - Adversary model
Na ciência da computação , um algoritmo online mede sua competitividade em relação a diferentes modelos de adversários . Para algoritmos determinísticos, o adversário é o mesmo que o adversário offline adaptável. Para algoritmos online aleatórios, a competitividade pode depender do modelo do adversário usado.
Adversários comuns
Os três adversários comuns são o adversário inconsciente, o adversário adaptável online e o adversário adaptável offline.
O adversário alheio às vezes é chamado de adversário fraco. Este adversário conhece o código do algoritmo, mas não conhece os resultados aleatórios do algoritmo.
O adversário adaptável online é às vezes chamado de adversário médio. Este adversário deve tomar sua própria decisão antes de saber a decisão do algoritmo.
O adversário adaptável offline às vezes é chamado de adversário forte. Este adversário sabe tudo, até o gerador de números aleatórios. Esse adversário é tão forte que a randomização não ajuda contra ele.
Resultados importantes
De S. Ben-David, A. Borodin , R. Karp , G. Tardos , A. Wigderson , temos:
- Se houver um algoritmo aleatório que é α-competitivo contra qualquer adversário offline adaptativo, então também existe um algoritmo α-competitivo determinístico.
- Se G é um algoritmo aleatório c-competitivo contra qualquer adversário online adaptativo e há um algoritmo d-competitivo aleatório contra qualquer adversário esquecido, então G é um algoritmo competitivo aleatório (c * d) contra qualquer adversário offline adaptativo.
Veja também
Referências
- Borodin, A .; El-Yaniv, R. (1998). Computação online e análise competitiva . Cambridge University Press. ISBN 978-0-521-56392-5 .
- S. Ben-David; A. Borodin; R. Karp ; G. Tardos; A. Wigderson. (1994). "Sobre o poder da randomização em algoritmos on-line" (PDF) . Algorithmica . 11 : 2–14. doi : 10.1007 / BF01294260 .