Қарсылас моделі - Adversary model
Жылы Информатика, an желідегі алгоритм оны өлшейді бәсекеге қабілеттілік әр түрлі қарсы қарсылас модельдер. Детерминирленген алгоритмдер үшін қарсылас адаптивті оффлайн қарсыласпен бірдей. Кездейсоқ онлайн алгоритмдер үшін бәсекеге қабілеттілік тәуелді болады қарсылас моделі қолданылған.
Жалпы қарсыластар
Үш қарапайым қарсылас - бұл ұмытшақ қарсылас, бейімделгіш онлайн және бейімделетін оффлайн қарсылас.
The ұмытшақ қарсылас кейде әлсіз қарсылас деп аталады. Бұл қарсылас алгоритмнің кодын біледі, бірақ алгоритмнің кездейсоқ нәтижелерімен таныса алмайды.
The бейімделетін онлайн-қарсылас кейде орташа қарсылас деп аталады. Бұл қарсылас алгоритм шешімін білуге рұқсат етпес бұрын өз шешімін қабылдауы керек.
The адаптивті оффлайндық қарсылас кейде күшті қарсылас деп аталады. Бұл қарсылас бәрін біледі, тіпті кездейсоқ сандардың генераторы. Бұл қарсыластың күшті болғаны соншалық, рандомизация оған қарсы тұра алмайды.
Маңызды нәтижелер
С.Бен-Дэвидтен, А.Бородин, Р. Карп, Г.Тардос, А.Вигдерсон Бізде бар:
- Егер кез-келген адаптивті оффлайн қарсыласқа қарсы α-бәсекеге қабілетті рандомизацияланған алгоритм болса, онда α-бәсекелі детерминирленген алгоритм де бар.
- Егер G - кез-келген бейімделгіш онлайн-қарсыласқа қарсы с-бәсекелі рандомизацияланған алгоритм болса, ал кез-келген ұмытшақ қарсыласқа қарсы рандомизацияланған d-бәсекелік алгоритм болса, онда G кез-келген адаптивті оффлайн қарсыласқа қарсы рандомизацияланған (c * d)-бәсекелес алгоритм болып табылады.
Сондай-ақ қараңыз
Әдебиеттер тізімі
- Бородин, А.; Эль-Янив, Р. (1998). Интернеттегі есептеу және бәсекелестік талдау. Кембридж университетінің баспасы. ISBN 978-0-521-56392-5.
- С.Бен-Дэвид; А.Бородин; Р. Карп; Г.Тардос; А.Вигдерсон. (1994). «On-line алгоритмдердегі рандомизация күші туралы» (PDF). Алгоритмика. 11: 2–14. дои:10.1007 / BF01294260.