Düşman modeli - Adversary model
İçinde bilgisayar Bilimi, bir çevrimiçi algoritma ölçer rekabet gücü farklı karşı rakip modeller. Belirleyici algoritmalar için rakip, uyarlanabilir çevrimdışı rakiple aynıdır. Rastgele çevrimiçi algoritmalar için rekabet gücü, rakip model Kullanılmış.
Yaygın düşmanlar
Üç ortak düşman, habersiz düşman, uyarlanabilir çevrimiçi düşman ve uyarlanabilir çevrimdışı rakiptir.
habersiz düşman bazen zayıf düşman olarak anılır. Bu rakip, algoritmanın kodunu bilir, ancak algoritmanın rastgele hale getirilmiş sonuçlarını bilemez.
uyarlanabilir çevrimiçi düşman bazen orta düşman olarak adlandırılır. Bu düşman, algoritmanın kararını bilmesine izin verilmeden önce kendi kararını vermelidir.
uyarlanabilir çevrimdışı düşman bazen güçlü düşman olarak adlandırılır. Bu düşman her şeyi bilir, rastgele sayı üreteci bile. Bu düşman o kadar güçlü ki rastgele hale getirme ona karşı yardımcı olmuyor.
Önemli sonuçlar
S. Ben-David'den, A. Borodin, R. Karp, G. Tardos, A. Wigderson sahibiz:
- Herhangi bir uyarlanabilir çevrimdışı düşmana karşı α-rekabetçi olan rastgele bir algoritma varsa, o zaman bir α-rekabetçi deterministik algoritma da vardır.
- G, herhangi bir uyarlanabilir çevrimiçi düşmana karşı c-rekabetçi bir rasgele algoritma ise ve herhangi bir unutkan rakibe karşı rasgele bir d-rekabetçi algoritma varsa, o zaman G, herhangi bir uyarlanabilir çevrimdışı rakibe karşı rastgele (c * d)-rekabetçi bir algoritmadır.
Ayrıca bakınız
Referanslar
- Borodin, A.; El-Yaniv, R. (1998). Çevrimiçi Hesaplama ve Rekabet Analizi. Cambridge University Press. ISBN 978-0-521-56392-5.
- S. Ben-David; A. Borodin; R. Karp; G. Tardos; A. Wigderson. (1994). "Çevrimiçi Algoritmalarda Randomizasyonun Gücü Üzerine" (PDF). Algoritma. 11: 2–14. doi:10.1007 / BF01294260.